문제 링크
https://www.acmicpc.net/problem/2146
구현
먼저 각 섬이 모두 1로 되어있길래, 구분할 수 있게 2, 3과 같이 바꿔주는 전처리를 거쳤다. 그리고 BFS를 다시 하나하나 돌면서, 다른 섬이 나오면 멈추고 최소 거리를 갱신해주는 형식으로 풀었다. 생각보다 실행시간이 길지 않았다.
코드
from sys import stdin
from collections import deque
input = lambda : stdin.readline()
def solution():
n = int(input())
islands = []
for i in range(n):
islands.append(list(map(int, input().split())))
visited = [[False for col in range(n)] for row in range(n)]
flag = 0
for i in range(n):
for j in range(n):
if islands[i][j] and not visited[i][j]:
queue = deque()
queue.append((j, i))
flag += 1
while queue:
node = queue.popleft()
islands[node[1]][node[0]] = flag
for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
nx, ny = node[0] + dx, node[1] + dy
if 0 <= nx < n and 0 <= ny < n and not visited[ny][nx] and islands[ny][nx]:
visited[ny][nx] = True
queue.append((nx, ny))
min = n * n
for i in range(n):
for j in range(n):
queue = deque()
queue.append(((j, i), 0))
color = islands[i][j]
if color:
visited = set()
while queue:
node = queue.popleft()
if islands[node[0][1]][node[0][0]] and islands[node[0][1]][node[0][0]] != color:
if node[1] < min:
min = node[1]
break
for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
nx, ny = node[0][0] + dx, node[0][1] + dy
if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited and islands[ny][nx] != color:
queue.append(((nx, ny), node[1] + 1))
visited.add((nx, ny))
print(min - 1)
if __name__ == '__main__':
solution()