[17472] 다리만들기2

다리만들기2 (문제 _ 17472)

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다.

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

출력
모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

제한

• 1 ≤ N, M ≤ 10
  • 3 ≤ N×M ≤ 100
  • 2 ≤ 섬의 개수 ≤ 6

예제

7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

< answer >
9

풀이

섬의 개수와 맵의 크기가 작기 때문에 모든 섬의 좌표를 hashset에 저장하는 방식을 선택했다.

1. 섬을 모두 탐색하며 섬을 나누고 좌표를 저장한다.

• dfs를 이용해 바다와 섬을 나눈다

ArrayList<HashSet>() 에 섬의 좌표를 섬마다 나눠서 저장한다.

  dfs(int i, int j) {
      hs.get(iCnt).add(new Pair(i, j));
      visited[i][j] = true;

      for (int dir = 0; dir < dx.length; dir++) {
          int nx = dx[dir] + i;
          int ny = dy[dir] + j;

          if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
              continue;
          }

          if (map[nx][ny] == 1 && !visited[nx][ny])
              dfs(nx, ny);
      }
  }

 

2. 모든 섬이 연결되어야 하기 때문에 섬의 모든 좌표에서 다리를 4가지 방향으로 놔본다.

 for (int i = 0; i < iCnt; i++) {
     // 섬의 모든 좌표에서 시작
     for (Pair p : hs.get(i)) {
         for (int dir = 0; dir < 4; dir++) { // 상하좌우
             Pair result = go(p.x, p.y, dir); // 길이, 도착 섬

             // 다리의 길이가 2보다 작거나 같은섬끼리 연결한 경우
             if (result.x < 2 || result.y == i) {
                 continue;
             }

             // i번째 섬에서 도착 섬으로, x의 길이만큼의 다리 생성
             pq.add(new Pair(i, result.y, result.x));
         }
     }
 }

섬의 해당 좌표에서 놓을 수 있는 다리의 길이가 2이상이고 자기 자신의 섬으로 다리를 놓은 경우가 아니라면 나중에 모든 섬들을 연결하는 다리를 선택할 때 예비 선택지가 될 수 있기 때문에 queue에 저장한다.

3. 크루스칼이나 프림 알고리즘을 선택해 MST를 만들고 최소 비용을 출력한다.

코드

코드의 길이가 길어 생략한다

https://github.com/yu-ri-kim/Algorithm/blob/master/202006%20~%20202008/%EB%8B%A4%EB%A6%AC%EB%A7%8C%EB%93%A4%EA%B8%B02/Main_17472.java.