제목 백준 2146. 다리 만들기 [실패]

1.실패 원인

최근 그래프 문제는 모두 실패했다.. 응용하는 부분이 여전히 잘 안된다. 이번 문제는 섬들간의 최소 거리를 찾는 것이라 판단해 bfs라고 생각하고 코드를 작성했지만.. 코드 작성을 하던중 섬에서 바다로 나갈 때 바다에서 계속 자신의 섬으로 돌아오는 것을 확인했다. 문제는 bfs를 돌다가 섬의 일부분이 방문되지 않는 상태에서 바다로 나갈 때 해당하는 육지도 다른 섬으로 판단한다는 것이었다. 결론은 분리.. 섬에서 다른 섬으로 나가기 전에 섬에 포함된 육지들이 서로 같은 섬에 속한다는 것을 확인할 필요가 있었다. 여기까지 생각을하고 타임아웃이 걸려 리타이어했다.. 여기까지 오는데도 한시간이 걸렸다.. 답이없다 ㅠ

 

해당 문제는 dfs + bfs로 푸는 문제였다. 저번 문제에서 bfs는 최단 거리와 관련있다고 했었는데 dfs는 같은 연결 요소를 찾아 내는 문제와 관련이 있다. 따라서 dfs를 통해 같은 섬인지를 먼저 파악한 후 바다로 나갈 준비를 해야하는 것이다.

 

2.작성 코드

#include <iostream>

#include <queue>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int INF = 987654321;

const int MAX = 100;

 

typedef struct

{

        int y, x;

}Dir;

 

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

 

int N;

int graph[MAX][MAX];

bool visited[MAX][MAX];

 

void DFS(int y, int x, int cnt)

{

        visited[y][x] = true;

        graph[y][x] = cnt; //몇번 섬인지 표시

 

        for (int i = 0; i < 4; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if (0 <= nextY && nextY < N && 0 <= nextX && nextX < N)

                         if (graph[nextY][nextX] && !visited[nextY][nextX])

                                 DFS(nextY, nextX, cnt);

        }

}

 

int BFS(int cnt)

{

        queue<pair<int, int>> q;

        //우선 해당 섬의 좌표를 다 큐에 넣는다

        for(int i=0; i<N; i++)

                 for(int j=0; j<N; j++)

                         if (graph[i][j] == cnt)

                         {

                                 visited[i][j] = true;

                                 q.push(make_pair(i, j));

                         }

 

        int result = 0;

        while (!q.empty())

        {

                 int curSize = q.size();

                 //현재 큐에 있는 칸으로부터 한칸씩 전진해본다

                 for (int i = 0; i < curSize; i++)

                 {

                         int y = q.front().first;

                         int x = q.front().second;

                         q.pop();

 

                         for (int i = 0; i < 4; i++)

                         {

                                 int nextY = y + moveDir[i].y;

                                 int nextX = x + moveDir[i].x;

 

                                 //범위 내에 있고

                                 if (0 <= nextY && nextY < N && 0 <= nextX && nextX < N)

                                 {

                                          //다른 섬에 도착할 경우 반환

                                          if (graph[nextY][nextX] && graph[nextY][nextX] != cnt)

                                                  return result;

                                          //아직 방문하지 않은 바다칸이면 방문했다고 표시 후 큐에 넣는다

                                          else if (!graph[nextY][nextX] && !visited[nextY][nextX])

                                          {

                                                  visited[nextY][nextX] = true;

                                                  q.push(make_pair(nextY, nextX));

                                          }

                                 }

                         }

                 }

                 result++;

        }

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         cin >> graph[i][j];

 

        int cnt = 1;

        //DFS를 통해 섬 표시

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         if (graph[i][j] && !visited[i][j])

                                 DFS(i, j, cnt++);

 

        int result = INF;

        //각 섬에서 제일 가까운 섬까지 다리 놓을 때 최소 길이 구한다

        for (int i = 1; i < cnt; i++)

        {

                 memset(visited, false, sizeof(visited));

                 result = min(result, BFS(i));

        }

 

        cout << result << endl;

        return 0;

}



//출처: https://jaimemin.tistory.com/655 [꾸준함]

3.참고 코드

https://jaimemin.tistory.com/655

백준 2146번 다리 만들기

 

4. 해결 방안

dfs - 연결 요소 (서로 공통적인 부분을 찾아낼 때)

bfs - 최단 거리 (특정 위치에서 또 다른 특정 위치까지의 거리가 최소가 될 때)