백준 2146 다리 만들기(dfs, bfs)

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

2146번: 다리 만들기

#include <iostream>
#include <queue>

using namespace std;
const int MAX = 100;
int N;
int graph[MAX][MAX];
bool visited[MAX][MAX];
int island;
typedef struct
{
    int x, y;
} Dir;

Dir dirMove[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

void dfs(int x, int y, int num)
{
    visited[x][y] = true;
    graph[x][y] = num;
    for (int i = 0; i < 4; i++)
    {
        int nextX = x + dirMove[i].x;
        int nextY = y + dirMove[i].y;
        if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N && !visited[nextX][nextY] && graph[nextX][nextY])
            dfs(nextX, nextY, num);
    }
}

int bfs(int num)
{
    queue<pair<int, int>> q;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (graph[i][j] == num){
                visited[i][j] = true;
            q.push(make_pair(i, j));
            }
                
        }
    }
    int cnt = 0;
    while (!q.empty())
    {
        int curSize = q.size();
        for (int z = 0; z < curSize; z++)
        {
            int curX = q.front().first;
            int curY = q.front().second;

            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int nextX = curX + dirMove[i].x;
                int nextY = curY + dirMove[i].y;
                if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N && !visited[nextX][nextY] && graph[nextX][nextY] != num && graph[nextX][nextY])
                {
                    return cnt;
                }
                else if (!visited[nextX][nextY]&&0 <= nextX && nextX < N && 0 <= nextY && nextY < N )
                {
                    visited[nextX][nextY] = true;
                    q.push(make_pair(nextX, nextY));
                }
            }
        }
        cnt++;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> graph[i][j];
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (!visited[i][j] && graph[i][j])
                dfs(i, j, ++island);
        }
    }
    int result = 987654321;

    for (int i = 1; i < island; i++)
    {
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                visited[j][k] = false;
        result = min(result, bfs(i));
    }
    cout << result;
}

어떤 방향으로 풀어나가야할지 감이 잡히지 않아서 또

https://jaimemin.tistory.com/search/2146

'2146'의 검색결과

이 블로그의 코드를 보고 말았다....

 

이 코드의 핵심은 dfs 순회를 통해 붙어있는 친구들끼리 같은 번호를 지니게하고 bfs(너비우선탐색)를 통해 그 사이의 공간의 최솟값을 도출해낸다는.... 지금의 나는 상상도 못할 기가막힌 방법이다..... 코드를 짤 때 가독성이 좋은(물론 다른 사람한테 가독성이 높지 않은 코드여도 된다. 나한테만 이해가 잘되면 됨.) 선호하는 나로서는 이 블로그의 코드들이 참으로 대단하다.

 

워낙 가독성이 좋기 때문에 코드만 쭉 읽어보면 대충 방향이 파악되지만 bfs에 대해서는 나의 공부를 위해 조금 더 자세하게 살펴볼 필요가 있다.

 

 

int bfs(int num)
{
    queue<pair<int, int>> q;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (graph[i][j] == num){
                visited[i][j] = true;
            q.push(make_pair(i, j));
            }
                
        }
    }
    int cnt = 0;
    while (!q.empty())
    {
        int curSize = q.size();
        for (int z = 0; z < curSize; z++)
        {
            int curX = q.front().first;
            int curY = q.front().second;

            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int nextX = curX + dirMove[i].x;
                int nextY = curY + dirMove[i].y;
                if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N && !visited[nextX][nextY] && graph[nextX][nextY] != num && graph[nextX][nextY])
                {
                    return cnt;
                }
                else if (!visited[nextX][nextY]&&0 <= nextX && nextX < N && 0 <= nextY && nextY < N )
                {
                    visited[nextX][nextY] = true;
                    q.push(make_pair(nextX, nextY));
                }
            }
        }
        cnt++;
    }
}

dfs를 통해 설정해놓은 num을 받아 num에 해당하는 모두를 queue에 넣는다.

 

이 queue를 바탕으로 bfs 순회를 하는데 다른 섬에 도달하면 return 그렇지 않다면 다시 queue에 담는 식이다.

 

내가 계속 놓치던 부분이 있었는데 바로

 

int curSize = q.size();
        for (int z = 0; z < curSize; z++)
        {
        }

이 부분이었다!!!!

 

반드시 처음 queue에 들어간 만큼만 for loop를 돌려야 한다. 그만큼이 그 섬에서 거리가 1칸 늘어나는 지점들이기 때문이다. 

 

이 속성을 이용하기 위해 queue를 쓰는 bfs를 이용하지 않았나 싶다.

 

어려웠지만 재미있는 문제다. 왜 bfs에서 queue를 쓰는지 확실히 알고 있어야지 접근할 수 있는 문제라 생각한다. 보다 더 관점을 키울 필요가 있겠다.