백준 2146 다리만들기 - bfs 2번 활용 (C++)

-백준의 다리만들기 문제.

각각의 메소드에 대해서 설명하자면

input() : 그냥 주어진 N과 숫자들을 가지고 맵을 만드는 메소드.

이때 넣어줄때 섬을 1이아닌 -1로 넣어주는데 이는 넘버가 마킹되지 않은 섬을 뜻한다. 1부터 섬을 마킹하는데 1로 맵에 넣을 경우 겹치므로 -1로 넣어주었다.

 

landlabel(a,b,L) a,b에 있는 섬을 L로 마킹해 주는 메소드.

bfs를 통해서 탐색을 안한 섬들을 순차적으로 큐에 넣어 탐색 후, 아직 넘버링이 안된 섬의 경우에 L로 넘버링을 해준다.

 

bfs(i) : 섬 넘버 i에 대해서, 다음 섬으로 가기까지 최소 다리수를 구하는 메소드. 정답을 1씩 증가시키면서 가능한 모든 경우의 수를 bfs로 탐색한 후에, 다음 섬으로 도착 하자마자 리턴하고 종료.

 

main() : 답을 구하는 메소드

**주의할 점: 한번 런타임 에러가 난적이 있었는데, 탐색을 할때, 

 for(int i=1; i<land_label; i++){

에서 i <=land_label로 설정을 했었다. 하지만 main에서 라벨링을 할때는 label의 숫자가 하나 큰 상태로 저장이 되니까, 런타임 에러가 난것이다.ㅠㅠ

(예시1의 경우 land_label은 4로 끝나게 된다.)

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
 
const int MAX = 100;
int N,Answer;
int map[MAX][MAX];
bool visited[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<int, int>> V;
 
int min(int a, int b){return a<b?a:b;}
 
void input()
{
    Answer = 999999;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 1)
            {
                map[i][j] = -1;
                V.push_back(make_pair(i, j));
            }
        }
    }
}
 
void landlabel(int a, int b, int L){
    queue<pair<int,int>> q;
    q.push(make_pair(a,b));
    visited[a][b] = true;
    map[a][b]=L;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx>=0 && nx<N && ny>=0 && ny<N){
                if(visited[nx][ny]==false && map[nx][ny]==-1){
                    visited[nx][ny]=true;
                    map[nx][ny]=L;
                    q.push(make_pair(nx,ny));
                }
            }
        }
    }
}
 
int bfs(int Num)
{
    int Result = 0;
    queue<pair<int, int>> Q;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] == Num)
            {
                visited[i][j] = true;
                Q.push(make_pair(i, j));
            }
        }
    }
 
    while (Q.empty() == 0)
    {
        int S = Q.size();
        for (int i = 0; i < S; i++)
        {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();
 
            for (int j = 0; j < 4; j++)
            {
                int nx = x + dx[j];
                int ny = y + dy[j];
 
                if (nx >= 0 && ny >= 0 && nx < N && ny < N)
                {
                    if (map[nx][ny] != 0 && map[nx][ny] != Num) return Result;
                    else if (map[nx][ny] == 0 && visited[nx][ny] == false)
                    {
                        visited[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                    }
                }
            }
        }
        Result++;
    }
}
 
int main(void){
    input();
    int land_label=1;
    for(int i=0; i<V.size(); i++){
        int x = V[i].first;
        int y = V[i].second;
        if(!visited[x][y]){
            landlabel(x,y,land_label);
            land_label++;
        }
    }
 
    for(int i=1; i<land_label; i++){
        Answer = min(Answer,bfs(i));
        //visited를 전부 false로 초기화. memset이용하기,
        memset(visited,false, sizeof(visited));
    }
    cout<<Answer;
 
}