[C++] Boj 2146 다리 만들기

문제 링크

[2146 다리 만들기]

접근

1. 섬을 찾는다. (섬들은 각각 구별한다.)
   1. BFS
   2. 내부 count를 지정해서 섬을 1, 2, 3… 등으로 매긴다.
2. 한 섬에서, 다른 섬과 이어지는 가장 가까운 장소를 찾는다.
   1. 각 좌표마다 BFS
   2. 가장 가까이 있는 섬 좌표까지의 거리를 저장한다.
3. 각각 거리를 계산해 최소값을 출력한다.
   1. 섬 간 거리들을 저장한 배열을 정렬해서 최소값을 출력한다.

코드 (O(N^4))

/*
 * 1. 섬을 찾는다.
 * 2. 다른 섬과 이어지는 가장 가까운 장소를 찾고, 거리를 저장한다.
 * 3. 그 거리들 간의 최소값을 출력한다.
 */

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

int map[101][101];
int visited[101][101];
vector<int> dist;

int n;

bool IsInBoundary(int x, int y)
{
    if (x >= 0 && x < n && y >= 0 && y < n) return true;
    return false;
}

void FindIsland(int x, int y, int count)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;
    map[x][y] = count;
    
    while (!q.empty())
    {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (!IsInBoundary(nx, ny) || visited[nx][ny] > 0 || map[nx][ny] == 0) continue;

            map[nx][ny] = count;
            visited[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
}

void FindShortestDistance(int x, int y)
{
    // 방문 배열 초기화
    memset(visited, 0, sizeof(visited));

    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;

    while (!q.empty())
    {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            // 섬 바깥으로 거리 측정
            if (!IsInBoundary(nx, ny) || visited[nx][ny] > 0 || map[nx][ny] == map[x][y]) continue;

            // 다른 섬을 만나면 거리 저장하고 종료
            if (map[nx][ny] != 0)
                return dist.push_back(visited[cx][cy] - 1);
            
            visited[nx][ny] = visited[cx][cy] + 1;
            q.push({nx, ny});
        }
    }
}

int main()
{
    iostream::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];

    int count = 1;

    // 섬들을 찾아 각각 번호를 붙여줌
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (map[i][j] == 1 && visited[i][j] == 0)
                FindIsland(i, j, count++);

    // 각각의 좌표마다 다음 섬까지의 최단 거리 찾음 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (map[i][j] > 0)
                FindShortestDistance(i, j);

    sort(dist.begin(), dist.end());
    cout << dist[0];

    
    return 0;
}

결과

시간 내에, 한 번만에 맞힌 경우는 처음이다. 그래서 너무 기뻤다. ~~~~~~~~~~

알고리즘 강의를 듣고 문제를 차근차근 쪼개서 생각하며, 연습장에 스케치한 것이 정말 많은 도움이 되는구나를 느꼈다.

바킹독의 해설

/*
가장 직관적으로 떠올릴 수 있는 풀이. 이 풀이는 bfs를 육지의 개수(=최대 O(n^2)개)만큼
진행하고 bfs 1번은 O(n^2)의 시간복잡도이기 때문에 O(n^4)에 동작한다.

이 때 실제로 어떤 입력이 들어오면 O(n^4)에 동작할지 고민을 해볼 필요가 있는데,

1 1 1 1 1 1 1 1 1 1 1 ... 1 1 
1 0 1 0 1 0 1 0 1 0 1 ... 0 1
1 0 1 0 1 0 1 0 1 0 1 ... 0 1
.
.
.
1 0 1 0 1 0 1 0 1 0 1 ... 0 1
0 0 0 0 0 0 0 0 0 0 0 ... 0 0
.
.
.
0 0 0 0 0 0 0 0 0 0 0 ... 0 0
1 0 1 0 1 0 1 0 1 0 1 ... 0 1
.
.
.
1 0 1 0 1 0 1 0 1 0 1 ... 0 1
1 1 1 1 1 1 1 1 1 1 1 ... 1 1 

과 같은, 마치 빗 2개가 적당한 거리를 두고 있는 괴상한 형태로 설계를 해야 O(n^4)이 걸리는 데이터를 만들 수 있다.

단순히
1 1 1 1 1 1 1 1 1 1 1 ... 1 1
.
.
.
1 1 1 1 1 1 1 1 1 1 1 ... 1 1
0 0 0 0 0 0 0 0 0 0 0 ... 0 0
.
.
.
0 0 0 0 0 0 0 0 0 0 0 ... 0 0
1 1 1 1 1 1 1 1 1 1 1 ... 1 1
.
.
.
1 1 1 1 1 1 1 1 1 1 1 ... 1 1

과 같이 데이터를 만들면 O(n^4) 대신 O(n^3)이 걸리는데, 왜 위와 같은 괴상한 형태로 만들어야 O(n^4)이고
이 데이터는 O(n^3)인지 고민을 해보면 앞으로 bfs에서의 시간복잡도 분석에 도움이 될 것으로 보인다.

다행히 n = 100이어서 O(n^4)로도 통과에는 문제가 없다. 비록 문제를 풀 때 실제로 O(n^4)를
필요로 하는 데이터가 있는지 고민을 해보는건 시간복잡도를 제대로 따져보기 위해서는
진행되어야 하는 과정이었지만 이 문제의 경우 그러한 데이터를 구성하는게 꽤 어려웠기 때문에
이 과정을 생략했더라도 그럴 수 있으나 풀이를 생각한 후 풀이의 시간복잡도를 아예
고민해보지 않았거나, O(n^2) 혹은 O(n^3)으로 시간복잡도를 잘못 인지했다면 시간복잡도에
대해 항상 신경을 써야하는 점을 기억하도록 하자.

또한 이 문제는 bfs를 2번만 사용해 O(n^2) 문제를 풀어내는 풀이가 존재한다. 해당 풀이는
별해에 등록할 예정이니 코드를 확인해보는 것을 권장하고 자세한 설명글은

<https://infossm.github.io/blog/2019/03/07/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%8C%80%EB%B9%84-%ED%8A%B9%EA%B0%95/>

의 52p부터 확인하면 된다.
*/

개선법

결론은, 같은 섬에 속한 육지에 대해, 각 육지를 따로 BFS를 돌리는 것 보다는 동시에 BFS를 돌리는 것이 더 효율적이라는 것이다.

개선된 코드 O(N^2)

코딩테스트 대비 특강

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// <http://boj.kr/9d843ab1d6ce444a91717842520d1df3>
#include 
using namespace std;
#define X first
#define Y second
int board[101][101];
bool vis[101][101]; // 섬을 분류하는 첫 번째 bfs에서 사용
int dist[101][101]; // 다리의 길이를 구하는 두 번째 bfs에서 사용
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int n;
bool OOB(int a, int b){ // Out Of Bounds인지 체크하는 함수
  return a < 0 or a >= n or b < 0 or b >= n;
}

// 섬을 분류하는 첫 번째 bfs
void island(){
  int idx = 1; // 섬의 번호. board를 이 섬의 번호로 갱신할 예정
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(vis[i][j] || board[i][j] == 0) continue;
      // 아직 방문하지 않은 육지에 도달
      queue<pair<int,int> > Q;
      Q.push({i,j});
      vis[i][j] = true;
      while(!Q.empty()){
        auto cur = Q.front(); Q.pop();
        board[cur.X][cur.Y] = idx;
        for(int dir = 0; dir < 4; dir++){
          int nx = cur.X+dx[dir];
          int ny = cur.Y+dy[dir];
          if(OOB(nx,ny) || vis[nx][ny] || board[nx][ny] == 0) continue;
          Q.push({nx,ny});
          vis[nx][ny] = true;
        }
      }
      idx++; // 번호를 1 증가시켜 다음 섬에는 1 증가된 값이 기록될 수 있게끔 한다.
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      cin >> board[i][j];
  island();
  for(int i = 0; i < n; i++)
    fill(dist[i],dist[i]+n,-1);
  queue<pair<int,int>> Q;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(board[i][j] != 0){
        dist[i][j] = 0;
        Q.push({i,j});
      }
    }
  }
  int ans = 999999;
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X+dx[dir];
      int ny = cur.Y+dy[dir];
      if(OOB(nx,ny) || board[nx][ny] == board[cur.X][cur.Y]) // OOB거나 인접한 곳이 같은 섬일 경우
        continue;
      if(board[nx][ny] != 0){ // 인접한 곳이 다른 섬일 경우
        ans = min(ans,dist[nx][ny]+dist[cur.X][cur.Y]); // cur와 (nx, ny) 각각이 육지로부터 떨어진 거리를 합하면 된다.
      }
      else{ // 바다일 경우
        board[nx][ny] = board[cur.X][cur.Y];
        dist[nx][ny] = dist[cur.X][cur.Y]+1;
        Q.push({nx,ny});
      }
    }
  }
  cout << ans;
}

/*
bfs를 2번만 사용해 O(n^2) 문제를 풀어내는 풀이. 자세한 설명글은

<https://infossm.github.io/blog/2019/03/07/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%8C%80%EB%B9%84-%ED%8A%B9%EA%B0%95/>

의 52p부터 확인하면 된다.
*/
</pair<int,int></pair<int,int>

수정한 나의 코드

/*
 * 1. 섬을 찾는다.
 * 2. 다른 섬과 이어지는 가장 가까운 장소를 찾고, 거리를 저장한다.
 * 3. 그 거리들 간의 최소값을 출력한다.
 */

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

int map[101][101];
int visited[101][101];
int dist = 987654321;

int n;

bool IsInBoundary(int x, int y)
{
    if (x >= 0 && x < n && y >= 0 && y < n) return true;
    return false;
}

void FindIsland(int x, int y, int count)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;
    map[x][y] = count;
    
    while (!q.empty())
    {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (!IsInBoundary(nx, ny) || visited[nx][ny] > 0 || map[nx][ny] == 0) continue;

            map[nx][ny] = count;
            visited[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
}

void FindShortestDistance(queue<pair<int, int>>& q)
{
    // 방문 배열 초기화
    memset(visited, 0, sizeof(visited));
    
    while (!q.empty())
    {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            // 섬 바깥으로 거리 측정
            if (!IsInBoundary(nx, ny) || map[nx][ny] == map[cx][cy]) continue;

            // 다른 섬을 만나면 거리 출력하고 종료
            if (map[nx][ny] != 0)
            {
                dist = min(dist, visited[nx][ny] + visited[cx][cy]);
            }
            else
            {
                map[nx][ny] = map[cx][cy];
                visited[nx][ny] = visited[cx][cy] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main()
{
    iostream::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];

    int count = 1;
    
    // 섬들을 찾아 각각 번호를 붙여줌
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (map[i][j] == 1 && visited[i][j] == 0)
                FindIsland(i, j, count++);
            
    queue<pair<int, int>> q;
    // 각각의 좌표마다 다음 섬까지의 최단 거리 찾음 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (map[i][j] > 0)
            {
                q.push({i, j});
            }

    
    FindShortestDistance(q);

    cout << dist;

    
    return 0;
}

bfs에 출발점을 모두 다 넣는 방식으로 코드를 수정하면서 많은 시행착오가 있었지만 결국 해냈다.

내가 간과한 점은 현재 어떤 섬에 있는지 정보를 넘겨줬어야 하는데 그것을 잡아내지 못했다.

사실 알고는 있었는데 map 원본을 수정하는 방법이 싫어 어떤 조건을 줘야 할지 고민하다가 안 풀려서 그냥 map을 수정하는 방법으로 그 정보를 넘겨주었다. ..

그 결과 시간을 줄일 수 있었다!

헷갈렸던 부분

dist = min(dist, visited[nx][ny] + visited[cx][cy]);

최소 거리인데 왜 더하는 건지 이해가 되지 않았는데, 밑의 그림으로 이해했다!