[ 백준 2146 ] 다리 만들기 (C++)

[문제보기]

 

[해결과정]

 

 1. 입력 받기 (n, arr[][])

 2. 섬 번호 메기기

   -> group 변수 선언 (섬 번호 Count)

   -> arr 배열을 돌면서, 1이면서 방문하지 않은 곳이라면 q(큐)에 좌표 넣기

   -> 해당 좌표에 map배열에 gNum 입력과 방문체크 후 BFS() 실행

 

 ★★★ 여기서 섬들의 좌표가 잘 찍혔는지 map을 print 해서 디버깅 한번 해보기!!!

 

 3. 반복문을 사용해 섬번호 1번부터 끝번호까지 탐색

   -> check배열 초기화

   -> func(섬번호) 함수 실행

 

 4. func(섬번호) 함수

   -> arr 맵을 돌며 섬번호와 같은 좌표는 q2( y좌표, x좌표, cnt(초기값0) ) 삽입

   -> q2에 대한 bfs 실시

      -> 만약 다음 노드가 방문하지 않은 곳이고, 맵에서 0 이라면, 방문체크 후 BFS 계속 진행

      -> ★만약 다음 노드가 맵에서 0이 아니고, 맵에서 섬번호와 같지 않다면!!!

         -> ans와 cnt를 비교하여 ans보다 작으면 ans = cnt; 후 return...

 

 5. 3번 부분에서 func 까지 수행했다면, q2 비워주기. <<< while(!q2.empty()) q2.pop() >>>

 6. ans 출력

 

[소스코드]

/*
    BOJ 2146 - 다리 만들기
    Created by haejun on 2020/02/26
*/
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
#include<algorithm>
using namespace std;
const int MAX = 102;
 
int n;
int arr[MAX][MAX];
bool check[MAX][MAX];
int map[MAX][MAX];
 
int group = 0;
 
struct coor {
    int y;
    int x;
};
 
struct coor2 {
    int y;
    int x;
    int cnt;
};
 
queue <coor> q;
queue <coor2> q2;
 
int ans = 987987987;
 
 
// inside check
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < n;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void bfs() {
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (inside(ny, nx) && arr[ny][nx] == 1 && check[ny][nx] == 0) {
                check[ny][nx] = 1;
                map[ny][nx] = group;
                q.push({ ny,nx });
            }
        }
    }
}
 
void func(int g) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == g) {
                q2.push({ i,j,0 });
            }
        }
    }
 
    while (!q2.empty()) {
        int y = q2.front().y;
        int x = q2.front().x;
        int cnt = q2.front().cnt;
        q2.pop();
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (inside(ny, nx) && check[ny][nx] == 0 && map[ny][nx] == 0) {
                check[ny][nx] = 1;
                q2.push({ ny,nx,cnt + 1 });
            }
            else if (inside(ny, nx) && map[ny][nx] != 0 && map[ny][nx] != g) {
                if (cnt < ans) ans = cnt;
                return;
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> arr[i][j];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1 && check[i][j] == 0) {
                group++;
                check[i][j] = 1;
                map[i][j] = group;
                q.push({ i,j });
                bfs();
            }
        }
    }
 
 
    for (int g = 1; g <= group; g++) {
        memset(check, 0, sizeof(check));
        func(g);
        while (!q2.empty()) q2.pop();
    }
 
    cout << ans << endl;
 
    //디버깅
    /*
    cout << endl << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    */
    
    
 
    return 0;
}

 

[해결 과정 중 실수한 부분]

 중간에 다리를 연결 할 때, 고민을 많이 했다.. 전체적으로 섬 테두리를 큐에 넣어서 해결하려 했는데, 처음 부터 겹칠 경우도 있었고,... 이래저래 예외처리할 사안이 많았다..

 

 그래서 고민을 계속 하다, 그냥 섬 한개 씩 기준점 잡고, 모든 섬에 대해서 탐색 하는 것으로 했다. 시간도 2초이고, 충분히 수행가능해보여서 했더니.. 솔브드했다!

 

 

[관련 문제 혹은 비슷한 문제]

 삼성 역량테스트 - 다리 만들기2