[백준 2146] 다리 만들기 (C++/Python)

1. 조건

- 섬 : 동서남북으로 붙어있음
- 가장 짧은 다리 1개만 구하면 된다
- 항상 두 개 이상의 섬이 있는 데이터임 → 다리로 무조건 연결된다

2. 입력

- 1<= n <= 100
- 0 : 바다 / 1 : 육지

3. 출력

- 가장 짧은 다리

4. 반례

5
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 1 0
1 1 0 0 0
// 2

5
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
1 0 0 0 0
// 3

6
1 0 0 0 1 0
0 0 0 1 1 1
0 0 0 0 0 0
1 0 1 1 0 0
0 1 1 1 1 1
0 0 0 0 0 0
// 1

5. 알고리즘

1) 같은 섬에서 나온 다리끼리 연결되면 안되기 때문에 섬마다 번호를 붙여준다. → arr

2) 어떤 섬에서 나온 다리인지 알아내기 위해 섬과 붙어있는 인근의 바다한테 몇번 섬에서 시작된 것인지 표시한다. → start (인데 queue에다가 pair<int, pair<int,int>> 해도 괜찮을 듯 하다.)

3) 바다에 다리를 놓는다. → visited
4) 바다에 하나씩 다리를 놓는데 다른섬에서 출발한 다리를 만나면 거리를 더해 최소값인지 비교한다. 

 

---

 

C++)

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define MAX_NUM 102
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int n;
int arr[MAX_NUM][MAX_NUM];		// 지도
int visited[MAX_NUM][MAX_NUM];	// 다리 설치중
int start[MAX_NUM][MAX_NUM];	// 다리가 어느 섬에서부터 시작 되었는지
queue<pair<int, int>> q;

void FindIsland() {
	int num = 1;
	queue<pair<int, int>> temp;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			// 새로운 섬을 발견하면
			if (arr[i][j] == -1 && visited[i][j] == 0) {
				temp.push({ i,j });
				arr[i][j] = num;
				visited[i][j] = -1;	// 방문표시하고
				
				// 섬의 영역을 알아내고 번호를 붙여준다
				while (!temp.empty()) {
					int x = temp.front().first;
					int y = temp.front().second;
					temp.pop();
				
					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];

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

						if (arr[nx][ny] == -1 && visited[nx][ny] == 0) {
							temp.push({ nx,ny });
							arr[nx][ny] = num;
							visited[nx][ny] = -1;
						}
					}
				}

				// 다음 섬을 위해 번호 올리기
				num++;
			}
		}
	}
}

void FindSea() {
	for (int i = 0; i < n; i++)
		fill(visited[i], visited[i] + MAX_NUM, 0);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			// 바다를 발견하면
			if (arr[i][j] == 0 && visited[i][j] == 0) {
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];

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

					// 붙어있는게 섬이다
					if ((arr[nx][ny] > 0) && visited[i][j] == 0) {
						q.push({ i,j });
						visited[i][j] = 1;
						start[i][j] = arr[nx][ny];	// 몇번 섬이랑 가까운 바다인지 표시
					}
				}
			}
		}
	}
}

int GetShortestPath() {
	int ans = 987654321;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

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

			// 바다를 만남
			if (arr[nx][ny] == 0 && visited[nx][ny] == 0) {
				q.push({ nx,ny });
				visited[nx][ny] = visited[x][y] + 1;
				start[nx][ny] = start[x][y];
			}
			// 섬 만남
			else if (arr[nx][ny] > 0 && visited[nx][ny] == 0 && arr[nx][ny] != start[x][y]) {
				ans = min(ans, visited[x][y]);
			}
			// 다리를 만남
			else if (arr[nx][ny] == 0 && visited[nx][ny] != 0 && start[nx][ny] != start[x][y]) {
 				ans = min(ans, visited[x][y] + visited[nx][ny]);
			}
		}
	}

	return ans;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];

			if (arr[i][j] == 1)
				arr[i][j] = -1;
		}
	}

	// 섬을 찾는다
	FindIsland();
	FindSea();
	cout << GetShortestPath();

	return 0;
}

처음 문제 풀 때는

// 다리를 만남
else if (arr[nx][ny] == 0 && visited[nx][ny] != 0 && start[nx][ny] != start[x][y]) {
    ans = min(ans, visited[x][y] + visited[nx][ny]);
}

이 부분을 생각하지 못하고 섬과 연결된 바다에서 다른 섬으로 갈 때까지 무조건 다리를 놓게했다.

문제에서 주어진 예제를 이용하여 설명하자면 1번 섬에서 시작된 다리는 2번, 3번 섬을 만날 때까지 놓고, 2번 섬에서 시작된 다리는 1번 3번 섬을 만날 때까지 놓았는데 정답자 분들 시간을 보니 내 풀이와 시간차이가 300배 가량 차이가 나는 것이었다. (처음 섬에다 번호 안 붙여줬을 때는 약 1000ms, 섬에 번호 붙여주니까 300ms로 줄었음) 

그래서 다른 분들 풀이를 봤는데 그제서야 '다리가 섬을 꼭 만날 필요가 없이 다른 섬에서 출발한 다리만 만나면 되는구나'를 깨달았고 문제를 다시 풀었다.

코드를 더 줄일 수 있을 것 같은데 당장은 생각나지 않으니 나중에 또 다시 풀어봐야겠다.

 

 

 

Python)

import sys
from collections import deque

read = sys.stdin.readline

dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()

n = int(read().rstrip())
arr = [ [0] * n for _ in range(n)]
start = [ [0] * n for _ in range(n)]

# 입력받기
for i in range(n):
    arr[i] = list(map(int, read().rstrip().split()))

    for j in range(n):
        arr[i][j] = (-1 if arr[i][j] == 1 else 0)

# 섬에 번호 붙여주기
def find_island():
    visited = [ [0] * n for _ in range(n)]
    temp = deque()
    num = 1

    for i in range(n):
        for j in range(n):
            if arr[i][j] == -1:
                temp.append((i,j))
                visited[i][j] = 1
                arr[i][j] = num

                while temp:
                    x, y = temp.popleft()

                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]

                        if 0 <= nx < n and 0 <= ny < n:
                            if arr[nx][ny] == -1 and visited[nx][ny] == 0:
                                temp.append((nx,ny))
                                visited[nx][ny] = 1
                                arr[nx][ny] = num

                num += 1

# 바다 찾기
def find_sea():
    visited = [ [0] * n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            # 바다를 찾았고 아직 방문 안했다
            if arr[i][j] == 0 and visited[i][j] == 0:
                
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]

                    # 섬과 연결된 바다라면
                    if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] > 0 and visited[i][j] == 0:
                        visited[i][j] = 1
                        start[i][j] = arr[nx][ny]
                        q.append((i,j))

    return visited

# 최단거리 찾기
def get_shortest_path():
    ans = 987654321

    while q:
        x,y = q.popleft()

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            # 다리를 안 놓은 바다를 만남
            if arr[nx][ny] == 0 and visited[nx][ny] == 0:
                q.append((nx,ny))
                visited[nx][ny] = visited[x][y] + 1
                start[nx][ny] = start[x][y]
            # 섬을 만남
            elif arr[nx][ny] > 0 and arr[nx][ny] != start[x][y]:
                ans = min(ans, visited[x][y])
            # 다리를 만남
            elif visited[nx][ny] > 0 and start[nx][ny] != start[x][y]:
                ans = min(ans, visited[x][y] + visited[nx][ny])

    return ans

find_island()
visited = find_sea()

print(get_shortest_path())