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

[문제]

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

2146번: 다리 만들기

[문제를 보자마자 든 생각]

• 보자마자 일단 bfs로 단지나누기를 해야겠다고 생각했다.
• 단지를 나눈 다음, 한 단지에서 이동하다가 다른단지를 만날때까지의 거리를 구한다음
• 그 거리의 최솟값을 구하면 될것이라고 생각했다.

[문제풀이]

• 이중for문 돌면서 육지라면 좌표를 bfs(int x, int y)에 전달.
• bfs() 에서 너비탐색하면서 바다이면 true, 육지이면 false를 반환하게 함
• ==>매개변수로 전달된 x,y 주변이 육지(false)라면 탈락, 바다라면 가장자리라는 것이니까 계속 진행
• bfs2(int x, int y)에 전달되는 x,y는 한 그룹 내에서 가장자리를 차지하고 있는 육지임
• ==> 한 그룹내에 있는 육지는 bfs2를 돌면서 방문하면 안되기때문에 첫번째 while문에서 방문체크를 true로 바꿔준다.
• 두번째while문에서는 A그룹 -> B그룹까지의 거리를 알아보기 위해 cnt를 카운팅 시킨다.
• result값들 중 가장 min값을 구하도록 한다.
•  

[전체코드]

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
struct Pos {
    int x, y, cnt;
};
 
int n;
int arr[101][101];
bool visited[101][101];
 
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
int result = 123456789;
 
bool bfs(int a, int b) {
    for (int k = 0; k < 4; k++) {
        int na = a + dx[k];
        int nb = b + dy[k];
 
        if (na >= 0 && nb >= 0 && na < n && nb < n) {
            if (arr[na][nb] == 0) return true;
        }
    }
    return false;
}
 
void bfs2(int x, int y) {
    queue<Pos> q;
    q.push({ x,y,0 });
    visited[x][y] = true;
 
    while (!q.empty()) {
        int cx = q.front().x;
        int cy = q.front().y;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = cx + dx[k];
            int ny = cy + dy[k];
 
            if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                if (arr[nx][ny] == 1 && visited[nx][ny] == false) {
                    visited[nx][ny] = true;
                    q.push({ nx,ny,0 });
                }
            }
        }
    }
 
    q.push({ x,y,0 });//while문을 빠져나왔다면x,y는 육지그룹 내에서 가장자리일것이다.
 
    while (!q.empty()) {
        int cx = q.front().x;
        int cy = q.front().y;
        int cnt = q.front().cnt;
        q.pop();
 
        if ((x != cx || y != cy) && arr[cx][cy] == 1) {
            if (result > cnt) result = cnt;
            break;
        }
 
        for (int k = 0; k < 4; k++) {
            int nx = cx + dx[k];
            int ny = cy + dy[k];
 
            if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                if (visited[nx][ny] == false) {
                    visited[nx][ny] = true;
                    q.push({ nx,ny, cnt + 1 });
                }
            }
        }
    }
}
 
int main() {
    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) {//육지이고
                if (bfs(i, j)) {//육지옆에 또 육지라면
                    memset(visited, false, sizeof(visited));//방문체크 리셋
                    bfs2(i, j);//가장자리들 추려서 다른 육지로 이동하는 최소거리 구하도록 한다.
                }
            }
        }
    }
 
    cout << result -1 << "\n";
 
    return 0;
    }