음식물 피하기
문제
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.
위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.
물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).
지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.
입력
첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.
출력
첫째 줄에 가장 짧은 다리의 길이를 출력한다.
고민을 상당히 많이 했다. 처음엔 섬의 테두리 부분을 찾고, 좌표를 저장한 뒤, 각 섬의 테두리간의 거리 차이를 비교하여, 가장 짧은 거리를 찾으려 했지만, 당연히 실패하였다. 테두리를 구하는 방법도 명확하지 않았고, 그냥 코드가 엉망이었다.
단순히 그래프 탐색이라고 생각하여 쉽게쉽게 생각하다가, 그냥 바다를 건너버리면 어떨까 라는 생각을 하였다.
섬만 그래프를 이루는 것이 아니라, 바다도 역시 그래프를 이루고 있다는 생각을 하니까 문제가 풀리는 듯 하였다.
말은 쉽게 했지만 하루는 온전히 이 문제만 고민한 듯 하다.
구현(BFS)
1.섬을 이루고있는 그래프를 파악하고 번호를 매긴다.(1번섬,2번섬,3번섬)
2.모든 섬을 파악한 후에, 1번섬 부터 바다를 건넌다.
3.바다를 건너며 칸수를 세고, 2번섬에 도달할 때 까지의 최단 거리, 3번섬에 도달할 때 까지의 최단 거리를 모두 저장한다.
4.거리 값의 최소값을 출력한다.
코드를 살펴보자
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
graph = [list(map(int,input().split()))for _ in range(N)]
visited = [[False]*N for _ in range(N)]
result = 1000000000
def bfs(x,y): #섬을 파악하는 1번째 BFS
global cnt
queue = deque()
queue.append((x,y))
visited[x][y] = True
graph[x][y] = cnt
while queue:
x,y = queue.popleft()
for i in range(4):
a,b = x+dx[i],y+dy[i]
if 0 <= a < N and 0 <= b < N:
if not visited[a][b] and graph[a][b] == 1:
visited[a][b] = True
graph[a][b] = cnt #섬을 구분함. 1번섬,2번섬,3번섬
queue.append((a,b))
def bridge(k): #바다를 건너는 2번째 BFS
global result
distance = [[-1] * N for _ in range(N)]
queue = deque()
for i in range(N):
for j in range(N):
if graph[i][j] == k: #해당 섬일 경우
queue.append((i,j))
distance[i][j] = 0
while queue:
x,y = queue.popleft()
for q in range(4):
a,b = x+dx[q],y+dy[q]
if a>=N or a<0 or b>=N or b<0:
continue
if graph[a][b] > 0 and graph[a][b] != k: #다른 땅을 만난다면,
result = min(result,distance[x][y])
return
if graph[a][b] == 0 and distance[a][b] == -1: #바다 라면
distance[a][b] = distance[x][y] +1
queue.append((a,b))
dx = [0,1,0,-1]
dy = [1,0,-1,0]
cnt = 1 #섬 번호를 매길 카운터
for i in range(N): #배추.
for j in range(N):
if graph[i][j] == 1:
if not visited[i][j]:
bfs(i,j)
cnt+=1
for k in range(1,cnt):
bridge(k)
print(result)알고리즘 문제를 많이 풀다보면, 이런 사고방식이 늘진 모르겠지만, 아직 너무 어렵다..
지금까지 BFS나 DFS로 4방향 탐색하며, 적절한 값을 찾는 문제를 많이 풀어서, 이러한 방향성은 보이지만, 그 이후 뭘 어떻게 해야하는지는 또 여러 문제를 풀어보면서 내가 깨달아야하는 부분이라고 생각한다.
공부가 답이다.
