[C++] BOJ 2146 / BFS (다리 만들기)

문제 분석

 

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

solved.ac 기준으로 골드3 문제에 처음 도전해봤다. 지도에 섬이 주어지며, 섬 간에 최소 거리를 구하는 문제이다.

 

해결 방법

문제를 보자마자, 3가지 절차를 정리했다.

1. 섬 좌표 입력을 받은 후, BFS를 돌면서 섬마다 번호를 다르게 부여한다. (본인 코드에서는 "island"변수 활용)

2. 또 다른 큐에 들어가는 것은 주변에 "0"이 있는 육지이다. (본 코드에서는 "q2" 활용)

3. 또 다른 큐(q2)를 pop 해가며 다른 섬에 닿을 때 까지 BFS를 동작시킨다.

4. 1번부터 3번까지 반복 진행하며 최솟값을 출력한다.

 

코드

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>

#define X first
#define Y second
int board[101][101];
int dist[101][101];
int vis[101][101];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main() {
    int n;
    queue<pair<int,int>> q;
    int min = 300;
    int island=2;
    int isZero=0;
    cin >> n;
    for(int i=0;i<n;i++) {  // 바다 육지 좌표 입력
        for(int j=0;j<n;j++) {
            cin >> board[i][j];
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            queue<pair<int,int>> q2;
            if(board[i][j] == 0 || vis[i][j] != 0) continue;
            q.push({i,j});
            vis[i][j] = 1;
            board[i][j] = island;
            while(!q.empty()) {
                pair<int,int> 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(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                    if(board[nx][ny] == 0){
                        isZero=1;
                        continue;
                    }
                    if(vis[nx][ny] != 0) continue;
                    q.push({nx,ny});
                    board[nx][ny] = island;
                    vis[nx][ny] = 1;
                }
                if(isZero) {    // 섬의 가장 바까의 좌표 저장
                    q2.push({cur.X, cur.Y});
                    dist[cur.X][cur.Y]=1;
                    isZero = 0;
                }
            }

            while(!q2.empty()) {
                pair<int,int> cur = q2.front();
                q2.pop();
                if(board[cur.X][cur.Y] != 0 && board[cur.X][cur.Y] != island) {
                    min = dist[cur.X][cur.Y] < min ? dist[cur.X][cur.Y] : min;
                    break;
                }
                for(int dir=0;dir<4;dir++) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                    if(((board[nx][ny] == board[cur.X][cur.Y]) && board[nx][ny] != 0) || dist[nx][ny] != 0) continue;
                    q2.push({nx,ny});
                    dist[nx][ny] = dist[cur.X][cur.Y] + 1;
                }            
            }
            for(int k=0;k<n;k++)    // dist 초기화
                fill(dist[k], dist[k] + n, 0);
            island++;
        }
    }
    cout << min-2;
}

 

코드 분석

문제 특성 상, 최종에 거리를 출력함에 있어서 dist에서 2를 빼줘야 한다.( 출발점의 dist값이 1이고, 도착한 곳의 dist값이 기 때문에 2를 빼준다.)

island 라는 변수를 선언해서, 첫 BFS에 섬마다 번호를 다르게 부여하였다.

isZero 라는 변수를 선언해서, 섬의 외곽 지점인 육지(주변에 0이 있는)를 q2 에 push 하였다.