문제

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

소스코드

import sys
from collections import deque
input = sys.stdin.readline

if __name__ == "__main__":  
    n = int(input())
    area = [list(map(int,input().split())) for _ in range(n)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    q = deque()
    visited = [[0] * n for _ in range(n)]
    cnt = 1
    #섬 단지별로 나누기
    for i in range(n):
        for j in range(n):       
            if area[i][j] == 1 and not visited[i][j]:
                visited[i][j] = 1
                area[i][j] = cnt # 여기 체크 안해줘서 틀렸음!! 꼭 체크
                q.append([i,j])
                while q:
                    x,y = q.popleft()
                    for k in range(4):
                        xx = x + dx[k]
                        yy = y + dy[k]
                        if 0<= xx < n and 0<= yy < n and not visited[xx][yy]:
                            if area[xx][yy] == 1:
                                visited[xx][yy] = 1
                                area[xx][yy] = cnt
                                q.append([xx,yy])
                cnt +=1
    #섬 가장자리 체크
    for i in range(n):
        for j in range(n):
            flag = False
            if area[i][j] > 0:
                for k in range(4):
                    xx = i + dx[k]
                    yy = j + dy[k]
                    if 0<=xx<n and 0<=yy<n and area[xx][yy]==0:
                        flag = True
                        break
            if flag:
                q.append([i,j,area[i][j]])
    #가장자리에서 다른 섬으로 다리를 연결했을 때 가장 적은 수 찾기
    result = 1000000
    while q:
        sx,sy,inum = q.popleft()
        bridge = deque()
        bridge.append([sx,sy,0])
        visited = [[0]*n for _ in range(n)]
        while bridge:
            x,y,c = bridge.popleft()
            for k in range(4):
                xx = x + dx[k]
                yy = y + dy[k]
                if 0 > xx or n <= xx or 0 > yy or n <= yy or area[xx][yy] == inum or visited[xx][yy]:
                    continue
                if area[xx][yy] == 0 :
                    visited[xx][yy] = 1
                    bridge.append([xx,yy,c+1])
                elif area[xx][yy] != inum:
                    result = min(result,c)
                    break
    print(result)

설명

생각 로직

1. 섬을 찾아서 단지 나누듯 나눈다 (각 대륙마다 다른 숫자부여)
2. 섬의 가장자리를 모두 수집한다.
   -> 1일 때 상하좌우 하나라도 0 이 있다면 가장자리이다. -> 큐에 넣기
3. 가장자리를 하나씩 탐색한다.
4. 탐색하는 가장자리에서 상하좌우 현재 섬번호와 다른 섬이면 카운팅 최소값을 체크한다.

후기

• pypy로 해야 시간초과가 나지 않는다.
• 섬의 넘버를 부여할 때 while문 진입하기 전에 섬의 넘버 부여 + visiting 체크해줘야 상하좌우 말고 기준인 중심이 체크된다 !!!
• 변수가 여러개니까 헷갈리지 말고 어떤 반복문에 어떤 변수가 주 인지 잘 체크하자