[파이썬 | BOJ | 17472] 다리 만들기 2

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

17472번: 다리 만들기 2

 

문제

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

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

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

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

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

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다리의 총 길이: 13D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

다음은 올바르지 않은 3가지 방법이다

C의 방향이 중간에 바뀌었다	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

A의 길이는 4이고, B의 길이도 4이다.총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2)다리 B: 3과 4를 연결 (길이 3)다리 C: 2와 5를 연결 (길이 5)다리 D: 1과 2를 연결 (길이 2)총 길이: 12

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

입력

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

출력

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

제한

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

풀이

여러 구현해야 할 것이 많으므로 나눠서 생각해본다.

 

일단 지도에서 나라들을 구분해야한다.

BFS로 탐색하면서, 나라들을 구분한 배열인 visited를 만든다.

 

또한 각 나라에서 다른 나라로 다리를 건설해야 하는데, 각 다리들은 직선이여야 한다.

따라서 각 나라에서 상, 하, 좌, 우로 일직선으로 탐색해 나가면서, 0이 2개 이상으로 연속하고, 다른 나라와 만날 때 다리를 건설 할 수 있다고 한다. 따라서 현재 r, c 에서 상 하 좌 우 방향으로 탐색해 나가면서, 0의 개수를 세고, 0의 개수가 연속으로 2개 이상일때의 다리 길이를 bridgeLens배열로 전달한다. 다리길이는 최대 30이상일 수 없으니까 30을 최대값으로 기본으로 설정해 놓고, 더 작은 다리가 나올수록 갱신하면서 어떤 country에서 다른 나머지 country까지의 다리 길이를 저장해서 return한다.

 

이제 기본적인 데이터를 구하는 함수를 구상했으니 전체적인 문제 풀이방법을 구상해야 한다.

나라가 총 N개 있을때, 현재 나라 country에서 다른 연결되지 않은 모든 나라를 탐색한다.

연결되지 않은 나라들과 다리를 놓을 수 있는지 탐색해서, 다리를 놓을 수 있다면 백트래킹으로 재귀함수로 분화한다.

재귀함수를 호출했으면 다시 다리를 지워서 백트래킹을 진행한다.

 

따라서 정리하자면, 1번 나라에서 나머지 나라로 다리를 건설 할 수 있는지에 대한 bridgeLens 배열을 받아서, 

bridgeLens[j]가 30보다 작으면, 다리를 건설 할 수 있다는 뜻이고, 다리를 건설하는 것을, 1번에서 J번까지의 edge를 만드는 것으로 표현해서 백트래킹을 한다.

 

결국 1번 나라에서 다리를 만들 수 있는 나라가 M개 있다면 총 M+1개의 백트래킹 재귀호출이 생긴다(다리를 안만드는 경우도 있으므로)

 

이제 이 백트래킹 함수를 종료하는 조건은 지금 현재 나라에서 다른 나라들과 모두 연결되어 있는 것이다.

 

따라서 구현 순서를 정리하자면 다음과 같다.

 

1. 주어진 지도에서 각 나라들을 분리하는 BFS함수를 만든다. (findIsland())

2. 특정 나라에서 다른 나머지 나라들을 연결 하는 다리길이의 리스트를 만드는 함수를 만든다.(buildBridge())

3. 다리를 만드는 함수를 만든다. 이는 I나라에서 J나라까지의 edge를 만드는 것으로 생각할 수 있다. (graphUpdate())

4. 현재 나라들의 연결 정보를 탐색하는 함수를 만든다. (exitOption())

5. 백트래킹 함수를 만든다. (solve())