[백준] 2146 다리 만들기 - 골드 3
[오늘의 문제]
https://www.acmicpc.net/problem/2146
[오늘의 학습 키워드]
- 너비 우선 탐색
- BFS
- 구현
- 그래프 탐색, 그래픈 이론
- 격자 그래프
1. 문제설명
좌표평면에 지도의 정보가 주어집니다.
0은 바다, 1은 육지를 의미할 때 현재 육지와 다른 육지를 잇는 다리를 놓으려고 합니다.
이 다리를 놓을 때 가장 적은 비용이 들도록 가장 짧은 다리 하나만 설치한다고 합니다.
육지와 다른 육지를 잇는 다리의 길이가 가장 짧은 경우를 구해 출력하는 문제 입니다.
[제한사항]
- 시간 제한 2초
- 메모리 제한 192MB
- N(100이하의 자연수)
- 0은 바다, 1은 육지
- 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.
2. 접근방식
문제를 보면 육지와 다른 육지를 잇는 최대한 짧은 다리를 놓으려 합니다.
그말은 현재 위치를 기준으로 다음 위치를 탐색할 때 다음 위치는 바다여야 하겠죠
왜냐하면 가장 짧은 다리를 놓기 위해서는 유직의 가장자리에서 출발해야 하고
바다를 가로질러 다른 육지에 다리를 놓아야 하는데 그 육지역시 가장자리여야 가장 짧게 다리를 놓을 수 있겠죠
그렇다면 현재 육지를 기준으로 가장자리를 선정해 다리를 놓을 위치를 정해주어야 하겠죠
다리를 놓을 위치를 정했으면 다음 위치는 바다를 가로질러야 합니다.
바다를 가로질러 새로운 육지에 도착했을 때 탐색을 종료하고 그 길이를 출력해 주어야 합니다.
위 조건들을 정리해보면
1. 육지의 가장자리를 기준으로 다리를 놓을 시작 위치를 찾아줍니다.
2. 바다를 가로질러 다리를 놓아줍니다.
3. 새로운 육지에 도착한 경우 다리놓기를 종료하고 길이를 출력해 줍니다.
위 3가지 조건으로 나뉘어 지는데 한가지 문제가 존재합니다.
바로 육지는 무조건 1이고 바다는 무조건 0이라는 것입니다.
육지 가장자리에서 다리를 놓기 시작하면 다음 위치는 무조건 바다여야 하는데, 새로운 육지에 도착하면 종료해 주어야 합니다.
그러나 육지 가장자리에서 다음 위치 탐색을 위해 4방향 탐색을 실시할 때 바다가 아닌 육지인 위치도 존재합니다.
그렇기에 종료 조건이 모호해지게 되죠 탐색을 위해 다음 위치를 무조건 바다로만 한정하면 새로운 육지에 도착할 수 없고
그렇다고 새로운 육지를 위해 다음 위치가 1인 육지인 경우도 포함한다면
현재 섬의 육지에서 새로운 육지로 다리를 놓아 문제를 틀릴 가능성이 존재하죠
이를 해결하기 위해서 각 육지마다 번호를 부여해 주어야 합니다.
육지마다 고유 번호를 부여한다면 현재 육지를 기준으로 다음 위치를 바다로 한정 지을 수 있고
새로운 육지에 도착한다면 기존의 육지 번호와 틀려지기 때문에 새로운 육지에 도착한 것도 구분할 수 있겠죠
위 사항들을 고려하여 코드로 작성해 보았습니다.
3. 코드
import sys
input = sys.stdin.readline
from collections import deque
# 섬 전체에 고유번호 부여
def BFS(x, y, count):
queue = deque([(x, y)])
visited[x][y] = True
MAPS[x][y] = count # 번호 부여
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 다음 탐색 위치가 육지이며 방문하지 않은 곳 찾아서 queue에 넣기
if 0 <= nx < N and 0 <= ny < N:
if MAPS[nx][ny] == 1 and not visited[nx][ny]:
queue.append((nx, ny)) # queue에 넣기
visited[nx][ny] = True # 방문표시
MAPS[nx][ny] = count # 고유번호 부여
# 섬과 섬의 최단 거리 찾기
def find_loot(count):
queue = deque()
visited = [[-1] * N for _ in range(N)] # 바다와 연결된 육지를 0으로 시작하기 위해 -1로 초기화
# 2중 for문을 통해 모든 위치 탐색하며 현재 섬의 탐색위치 넣어주기
for i in range(N):
for j in range(N):
if MAPS[i][j] == count:
queue.append((i, j))
visited[i][j] = 0 # 섬의 최단거리는 0부터 시작
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < N:
# 다음 위치가 바다이고 아직 방문하지 않은곳인 경우
if MAPS[nx][ny] == 0 and visited[nx][ny] == -1:
queue.append((nx, ny)) # queue에 넣고 거리는 이전 거리에서 1 증가
visited[nx][ny] = visited[x][y] + 1
# 다음 위치가 다른 섬인 경우
if MAPS[nx][ny] != 0 and MAPS[nx][ny] != count:
return visited[x][y] # 이 섬까지 연결되는 거리 반환
# 입력
N = int(input())
MAPS = [list(map(int, input().split())) for _ in range(N)]
# 이 방문표시는 섬의 번호를 구분짓기 위한 방문표시 배열
visited = [[False] * N for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 섬을 찾아서 각 섬마다 번호 부여
count = 1 # 부여할 번호
for i in range(N):
for j in range(N):
# 탐색 위치가 육지이고 아직 방문하지 않은 곳 찾아서 연결된 섬에 고유번호 부여
if MAPS[i][j] == 1 and not visited[i][j]:
BFS(i, j, count)
count += 1
# 위 과정을 거치면 MAPS 배열은 고유번호가 부여된 섬들이 구분된다.
# 섬마다 부여된 고유 번호를 순서대로 탐색하며 최단 거리 찾기
answer = float('inf') # 그러기 위해서 정답을 큰 값으로 설정
for cnt in range(1, count):
answer = min(answer, find_loot(cnt))
print(answer)[코드설명]
# 입력
N = int(input())
MAPS = [list(map(int, input().split())) for _ in range(N)]
# 이 방문표시는 섬의 번호를 구분짓기 위한 방문표시 배열
visited = [[False] * N for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 섬을 찾아서 각 섬마다 번호 부여
count = 1 # 부여할 번호
for i in range(N):
for j in range(N):
# 탐색 위치가 육지이고 아직 방문하지 않은 곳 찾아서 연결된 섬에 고유번호 부여
if MAPS[i][j] == 1 and not visited[i][j]:
BFS(i, j, count)
count += 1
우선 전체적으로 입력을 받고 섬마다 고유 번호를 부여하기 위한 visited 방문 배열을 생성해 주었습니다.
또한 현재 위치를 기준으로 4방향 탐색을 실시해 주어야 하니 dx, dy도 생성하였고 육지마다 부여할 고유 번호를 count 변수로 지정해 주었습니다.
이제 중첩 반복문을 통해 전체 탐색을 실시하여 육지를 기준으로 BFS 탐색을 통해 육지의 전체 크기를 파악하고 해당 육지에 육지 고유번호를 1번부터 부여해 주었습니다.
# 섬 전체에 고유번호 부여
def BFS(x, y, count):
queue = deque([(x, y)])
visited[x][y] = True
MAPS[x][y] = count # 번호 부여
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 다음 탐색 위치가 육지이며 방문하지 않은 곳 찾아서 queue에 넣기
if 0 <= nx < N and 0 <= ny < N:
if MAPS[nx][ny] == 1 and not visited[nx][ny]:
queue.append((nx, ny)) # queue에 넣기
visited[nx][ny] = True # 방문표시
MAPS[nx][ny] = count # 고유번호 부여
섬 전체에 고유 번호를 부여하기 위해서 count 변수로 지정한 고유 번호를 BFS 탐색에 같이 넘겨 주었고 해당 count를 육지 고유번호로 지정해 주었습니다.
또한 육지 전체에 고유 번호를 부여하기 위해서는 다음 위치가 항상 육지여야 하고 방문하지 않았던 곳이어야 하겠죠
이를 위해 queue에 시작 위치를 기준으로 4방향 탐색을 실시하며 방문하지 않은 육지를 찾아 queue에 넣어 주었습니다.
또 그 과정에서 입력받은 MAPS에 바로 육지 고유번호를 부여해 주었습니다.
육지 고유 번호는 섬마다 번호가 달라져야 하기 때문에 1번의 BFS 동작이 종료되면 육지 고유 번호 count를 증가시켜 주었고 visited 방문 배열을 통해 이미 고유 번호가 부여된 섬을 제외한 새로운 섬을 찾아 주었습니다.
# 섬마다 부여된 고유 번호를 순서대로 탐색하며 최단 거리 찾기
answer = float('inf') # 그러기 위해서 정답을 큰 값으로 설정
for cnt in range(1, count):
answer = min(answer, find_loot(cnt))
섬마다 부여된 고유 번호를 순서대로 탐색하며 최단 거리를 찾아야 하는데
그 최단 거리는 1번섬과 3번섬 혹은 1번섬과 2번섬 그것도 아니면 2번섬과 3번섬 어디에서 나올지 알 수 없기 때문에
각 섬에서 출발하여 최단거리의 섬을 찾아주어야 합니다.
이때 찾아온 최단거리를 저장하기 위해서 answer 변수를 생성해 주었고 그 값에는 최대값을 먼저 넣어주어 min 함수의 활용이 가능하도록 해주었습니다.
# 섬과 섬의 최단 거리 찾기
def find_loot(count):
queue = deque()
visited = [[-1] * N for _ in range(N)] # 바다와 연결된 육지를 0으로 시작하기 위해 -1로 초기화
# 2중 for문을 통해 모든 위치 탐색하며 현재 섬의 탐색위치 넣어주기
for i in range(N):
for j in range(N):
if MAPS[i][j] == count:
queue.append((i, j))
visited[i][j] = 0 # 섬의 최단거리는 0부터 시작
while queue:
x, y = queue.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < N:
# 다음 위치가 바다이고 아직 방문하지 않은곳인 경우
if MAPS[nx][ny] == 0 and visited[nx][ny] == -1:
queue.append((nx, ny)) # queue에 넣고 거리는 이전 거리에서 1 증가
visited[nx][ny] = visited[x][y] + 1
# 다음 위치가 다른 섬인 경우
if MAPS[nx][ny] != 0 and MAPS[nx][ny] != count:
return visited[x][y] # 이 섬까지 연결되는 거리 반환
섬과 섬의 최단 거리를 찾기 위해서는 섬의 고유 번호를 기준으로 새로운 육지를 찾으면 그 거리를 갱신해 주어야 하죠
이를 위해서 입력받은 고유 번호를 기준으로 queue와 visited 배열을 생성해 주고 육지를 시작위치로 지정해 주어야 하니
거리를 저장할 방문 배열 visited 배열은 -1로 초기화 해주었습니다.
이제 중첩 반복문을 통해 탐색하려는 육지를 찾아 queue에 모두 넣어줍니다.
그리고 해당 육지는 모두 0으로 초기화 하여 어디서 시작해도 다리의 길이를 맞출 수 있도록 설정해 주었습니다.
이제 queue에 저장된 값들을 순차대로 탐색하며 BFS 탐색을 실시해 주는데 2가지 조건이 존재하죠
1. 다음 위치가 바다로 나가는 경우
2. 다음 위치가 새로운 육지인 경우
두가지 경우에서 바다로 나가는 경우 queue에 계속해서 새로운 좌표값을 넣어주고
visited 배열에 다리의 길이를 1씩 늘려가며 저장해 주어야 합니다.
그러다 새로운 육지에 도착한다면 현재위치까지 연결된 다리의 길이를 반환하여 answer에 저장해 주어야 겠죠
이걸 육지 번호만큼 반복하면 각 섬마다 연결되는 최단 거리의 다리를 찾을 수 있고 그 중 가장 최단 거리를 찾기위해 answer를
계속 초기화 해 나가겠죠
4. 결과
[회고]
이번 문제는 어제 풀었던 문제인데 시간이 늦어 오늘에서야 작성하는 문제입니다.
그간 계속해서 DP 문제만 풀다보니 오랜만의 BFS 문제를 풀때 구현의 재미를 다시한번 느끼게 되었습니다.
내가 생각한 가설을 점검하며 이 과정은 어떻게 해결하지를 계속 생각하다 보니 자연스레 조건이 늘어나고 코드가 복잡해지는데
이 과정을 최대한 단순하고 정형화 시키기 위해서 항상 노력하는것 같습니다.
BFS 문제의 경우 문제를 풀다보면 항상 등장하는 기본 조건들이 있습니다.
좌표평면의 범위를 벗어나지 않고, 방문 배열에 아직 방문하지 않았으며, 내가 설정한 조건에 맞는 다음 위치를 찾은 경우
queue에 넣어가며 너비 우선 탐색을 계속하게 되죠
이런식으로 문제를 계속 풀다보면 나만의 정형화된 구조가 생기는데 저 역시 여러 BFS 문제를 풀다보면 세부 조건,
혹은 BFS 탐색 조건에 따라 값이 달라지지 그 안에 들어가는 정형화된 구조가 존재합니다.
이번 문제를 풀며 항상 풀었었던 BFS 문제를 다시 풀어 어렵지 않게 해결할 수 있었습니다.
가장 기본이 되었던 BFS 문제인 유기농 배추 https://www.acmicpc.net/problem/1012 문제와 여러 BFS 문제에서 조건을 착안하여
섬마다 고유 번호를 부여하고 구분할 수 있었고 BFS 탐색과정을 줄일 수 있었죠
다음에도 비슷한 문제들을 풀어보며 학습을 이어 나가겠습니다.