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

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

dfs 와 bfs, 두 방법을 사용하여 문제를 해결하였습니다.

• dfs 를 사용하여 각 섬을 구분지어주었습니다.

  1110000222
  1111000022
  1011000022
  0011100002
  0001000002
  0000000002
  0000000000
  0000330000
  0000333000
  0000000000
  

  다음과 같이 첫 번째 섬은 1로, 두 번째 섬은 2로, n 번째 섬은 n으로 나누었습니다.

• 그 후에는 각 섬마다 아래의 과정을 반복합니다.

• 섬의 좌표를 모두 queue 에 담아줍니다.

• 각 좌표에 대해서 bfs 를 진행합니다.

  • 다른 땅을 밟았을 경우에는 다리가 완성된 것이므로 그 다리의 길이를 return 해줍니다.
  • 바다인 경우에는 해당 바다를 다시 queue 에 넣어줍니다.

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

using namespace std;

int board[101][101];
int visited[101][101];

int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0};

void dfs(int r,int c,int n, int count){
    board[r][c] = count;
    visited[r][c] = 1;
    
    for (int i=0;i<4;i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if (0<=nr && nr<n && 0<=nc && nr<n){
            if (board[nr][nc] && !visited[nr][nc]){
                dfs(nr,nc,n,count);
            }
        }
    }
}

int bfs(int count, int n){
    queue<pair <int,int>> q;
    for (int r=0;r<n;r++){
        for (int c=0;c<n;c++){
            if (board[r][c] == count){
                visited[r][c] = 1;
                q.push(make_pair(r, c));
            }
        }
    }
    
    int distance = 0;
    
    while (!q.empty()){
        int q_size = q.size();
        for (int i=0;i<q_size;i++){
            int r = q.front().first;
            int c = q.front().second;
            q.pop();
            
            for (int j=0;j<4;j++){
                int nr = r + dr[j];
                int nc = c + dc[j];
                if (0<=nr && nr<n && 0<=nc && nc<n){
                    if (board[nr][nc] && board[nr][nc] != count)
                        return distance;
                    
                    else if (!board[nr][nc] && !visited[nr][nc]){
                        visited[nr][nc] = 1;
                        q.push(make_pair(nr,nc));
                    }         
                }
            }
        }
        distance++;
    }
    return 0;
}

int main(int argc, const char * argv[]) {

    int n;
    cin >> n;

    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            cin >> board[i][j];
        }
    }
    
    int count = 1;
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (board[i][j] && !visited[i][j]){
                dfs(i,j,n,count++);
            }
        }
    }
    
    int result = 987654321;
    
    for (int i=1;i<count;i++){
        memset(visited, 0, sizeof(visited));
        result = min(result ,bfs(i,n));
    }
    
    cout << result << "\n";
    return 0;
}