[BOJ-2146] 다리만들기

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

2146번: 다리 만들기

---

[ 풀이 ]

두차례의 BFS를 이용해서 풀었다.

1. 라벨 번호 붙이기 + 바다와 인접한 섬위치 구하기 : BFS ( bfs_labeling()함수)

- 1인 값들은 섬번호로 바꿨다. MAP[y][x]를 1->라벨번호(1,2,3,..)

- 바다와 인접한 위치를 시작점들을 큐 q1에 넣는다.

 

2. 바다와 인접한 위치를 시작점으로 하여 다른섬이 나올 때까지 최소거리를 구하기

- 바다와 인접한 위치를 시작점으로 점점 확장해 나가는 방법으로 했다.

- 참고: https://mygumi.tistory.com/109

- q1에 있는 위치를 시작점으로 바다를 섬으로 바꾼다. 즉, MAP[y][x]를 0->label 로 변경하는 것. 

현위치의 상/하/좌/우 주변이 바다라면, 섬으로 확장을하면서 확장횟수를 1씩 증가한다.

 

- 만일 현위치의 상/하/좌/우 주변이 다른 섬번호라면 종료하고 dist[현재섬번호]+dist[다른섬번호] 를 리턴한다.

( dist[label-1], -1을 한것은 0을 시작으로 하기때문이다. 1번섬 확장횟수는 dist[0] )

 

+여기서 최소거리를 구할때 바로 리턴하지말고, 

다른 섬을 만날때 거리의 값을 거리리스트(distance_list)에 넣어서 그 중 제일 작은 값을 리턴한다.

---

[코드(python)]

import sys
from collections import deque

N=0
MAP=[]
visited=None
outter=None

q0=deque() #섬번호 부여
q1= deque() #바다가 인접한 섬위치를 저장하는 역할.-> 섬을 확장.

# 현위치의 상/하/좌/우
dy=[-1,1,0,0]
dx=[0,0,-1,1]

distance_list=[]

def isRange(y,x):
    global N
    if (y>=0 and y<N) and (x>=0 and x<N):
        return True
    return False

def bfs_labeling(cury, curx, label_number):
    global MAP, visited
    #매개변수를 큐에 추가한다.
    q0.append((cury, curx, label_number))
    
    while q0:
        y, x,  label= q0.popleft()
        if not visited[y][x]:
            visited[y][x]=True #방문
            MAP[y][x]=label #섬번호 부여

            water_cnt=0 #주변에 바다가 접해있는지 확인.
            #현위치의 상/하/좌/우가 바다가 아닌 육지(1)라면
            for i in range(4):
                nexty, nextx= y+dy[i], x+dx[i]
                
                if isRange(nexty, nextx):
                    #현위치의 주변에 바다가 있는지 확인해야한다.
                    if MAP[nexty][nextx]==0:
                        water_cnt+=1
                        
                    #방문을 하지 않았고, 육지라면.-> 육지번호를 부여
                    if (not visited[nexty][nextx]) and (MAP[nexty][nextx]==1):
                        q0.append((nexty, nextx, label))
            if water_cnt>0:
                #주변에 바다가 1개이상이라면있다면, 바다와 인접한 위치이다.
                #0은 다른섬이 나올때까지의 경로를 카운트한다.
                q1.append((y,x,label,0))

def bfs(island_cnt):#island_cnt: 섬개수
    global visited, MAP, distance_list
    #최소거리를 구한다.
    dist=[0]*(island_cnt)
    
    #q1은 바다와 인접한 섬의 위치이다. (이미 방문한 상태)
    #점점 섬번호로 확장해나간다. 그 위치의 주변이 서로다른 섬번호라면
    #현위치섬번호가 간거리 + 다른섬번호가 간거리 합으로 리턴한다.
    while q1:
        y, x, label, d=q1.popleft()
        MAP[y][x]=label
        dist[label-1]=d

        #현위치 주변에 아직 방문하지 않은 바다가 있는지 탐색한다. 그리고 dist[label]을 카운트한다.
        #만일 바다가 아닌 다른 섬번호라면 dist[현재섬번호]+dist[인접다른섬번호] 를 리턴
        for i in range(4):
            nexty, nextx= y+dy[i], x+dx[i]
            if isRange(nexty, nextx):
                #바다가 아닌 다른 섬번호이면.
                if (MAP[nexty][nextx]>0) and (MAP[nexty][nextx]!=label):
                    distance_list.append(dist[label-1]+dist[MAP[nexty][nextx]-1])
                
                elif (not visited[nexty][nextx]) and (MAP[nexty][nextx]==0):
                    visited[nexty][nextx]=True #방문을 한다.
                    q1.append((nexty, nextx, label, d+1))

def main():
    global N, MAP, visited, distance_list
    N=int(sys.stdin.readline()) #지도의 크기 입력
    visited=[[False]*N for _ in range(N)]  #방문리스트 입력
    
    for _ in range(N): #지도그리기
        MAP.append( list( map(int, sys.stdin.readline().split()) ) )

    #지도번호 라벨링
    label_number=1
    island_cnt=0 #섬개수 카운트
    for y in range(N):
        for x in range(N):
            if (MAP[y][x]!=0) and (not visited[y][x]):
                bfs_labeling(y,x, label_number)
                island_cnt+=1#섬개수 카운트
                label_number+=1
                
    #최소 거리를 구한다.
    bfs(island_cnt)
    print(min(distance_list)) #bfs실행.
    #큐를 비운다.
    q0.clear()
    q1.clear()
       
      
if __name__=='__main__':
    main()

---

[java코드]

import java.io.*;
import java.util.*;

public class Main
{
	static int N;
	static boolean visited[][];
	static int MAP[][];
	
	static int dy[]= {-1,1,0,0};
	static int dx[]= {0,0,-1,1};
	
	//BFS를 위한 큐
	static Queue<Island> q = new LinkedList<>();
	
	
	//중첩클래스
	static class Island
	{
		//필드
		int y,x,label;
		int distance=0;
		
		//생성자
		Island(int y, int x, int label){
			this.y=y;
			this.x=x;
			this.label=label;
		}
	}
	
	
	public static void main(String[] args) throws IOException
	{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		N=Integer.parseInt(br.readLine());
		
		//지도&방문리스트 초기화
		MAP=new int[N][N];
		visited=new boolean[N][N];
		
		//지도입력
		for(int y=0; y<N; y++) 
		{
			StringTokenizer st= new StringTokenizer(br.readLine());
			for(int x=0; x<N; x++) {
				MAP[y][x]=Integer.parseInt(st.nextToken());
			}
		}
		

		//label: 라벨번호 시작:1 -> 섬개수
		int label=1;
		for(int y=0; y<N; y++)
		{
			for(int x=0; x<N; x++)
			{
				if(!visited[y][x] && MAP[y][x]==1)				
					labeling(y,x,label++);		
			}
		}
		
		//가장자리인 원소를 찾아서 큐에 넣는다.
		for(int y=0; y<N; y++) {
			for(int x=0; x<N; x++) {
				if(MAP[y][x]>0 && isEdge(y,x))
					q.add(new Island(y,x,MAP[y][x]));
			}
		}
		
		//확장을한다.
		int result=bfs(label);
		System.out.println(result);
	}
	
	
	public static boolean isRange(int y, int x) 
	{
		if((y>=0 && y<N)&&(x>=0 && x<N)) return true;
		return false;
	}
	
	
	public static void labeling(int y, int x, int label) 
	{
		//Island 객체를 생성하고
		Island island= new Island(y,x,label);
		
		//큐에 넣는다.
		q.add(island);
		
		//큐가 비어있지 않을때 까지
		while(!q.isEmpty())
		{
			Island now=(Island)q.poll(); //맨왼쪽원소를 뺀다.
			//현재 now가 방문된 안된 상태인가?
			if(!visited[now.y][now.x])
			{
				visited[now.y][now.x]=true;
				MAP[now.y][now.x]=now.label;
				
				//now의 상/하/좌/우
				for(int i=0; i<4; i++) 
				{
					int nexty=now.y+dy[i];
					int nextx=now.x+dx[i];
					if(isRange(nexty, nextx))
					{
						//아직 방문안한상태이고, 값이 1이라면
						//큐에 추가한다.
						if((!visited[nexty][nextx])&&(MAP[nexty][nextx]==1)) 					
							q.add(new Island(nexty, nextx, label));
					}
				}	
			}
		}
	}
	
	//현재위치가 섬의 가장자리인가?
	public static boolean isEdge(int y, int x) {
		int water_cnt=0;
		for(int i=0; i<4; i++)
		{
			int nexty=y+dy[i];
			int nextx=x+dx[i];
			if(isRange(nexty, nextx)) 
			{
				if(MAP[nexty][nextx]==0)
					water_cnt++;
			}
		}
		if(water_cnt>0) return true;
		return false;
	}
	
	//섬의 가장자리에 위치한 부분을 계속확장시킨다.
	public static int bfs(int label) {
		int distances[]= new int[label];
		int min_distance=(int)Math.pow(100, 2); //최소거리 초기화
		
		
		while(!q.isEmpty())
		{
			Island now=(Island) q.poll();
			MAP[now.y][now.x]=now.label;
			distances[now.label-1]=now.distance;
			
			
			for(int i=0; i<4; i++)
			{
				int nexty=now.y+dy[i];
				int nextx=now.x+dx[i];
				if(isRange(nexty, nextx))
				{
					if((MAP[nexty][nextx]==0)&&(!visited[nexty][nextx])) {
						Island e= new Island(nexty, nextx, now.label);
						e.distance=now.distance+1;
						visited[nexty][nextx]=true;
						q.add(e);
					}

					//다른섬을 만난다면..
					else if((MAP[nexty][nextx]!=0) && (MAP[nexty][nextx]!=now.label)) {
						min_distance=Math.min(min_distance, distances[MAP[now.y][now.x]-1]+distances[MAP[nexty][nextx]-1]);
					}
				}
			}
		}
		return min_distance;
	}
}

---

5차례의 시도를 했다. 문제를 풀기까지 하루라는 시간이 걸렸다.

아직도 나는 BFS를 더 공부해야되나보다 ㅎㅎ;

 

이후에 본 괴물님의 코드

많이 참고해야겠다 ㅎㅎ

나보다 시간도 116ms이고, 무엇보다도 메모리가 나보다 1/3 배였다.

import sys
from collections import deque as dq, defaultdict as dd
input = sys.stdin.readline
n = int(input())
mapp = [[*map(int, input().split())] for i in range(n)]
a = 2

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
visited = [[1]*n for _ in range(n)]
boundary = dd(list)
for i in range(n):
    for j in range(n):
        if mapp[i][j] == 1:
            que = dq([(i, j)])
            mapp[i][j] = a
            visited[i][j] = 0
            while que:
                x, y = que.popleft()
                for ddx, ddy in zip(dx, dy):
                    nx, ny = x + ddx, y + ddy
                    if 0 <= nx < n > ny >= 0:
                        if mapp[nx][ny] == 1 and visited[nx][ny]:
                            visited[nx][ny] = 0
                            mapp[nx][ny] = a
                            que.append((nx, ny))
                        elif mapp[nx][ny] == 0 and visited[nx][ny] != a:
                            visited[nx][ny] = a
                            boundary[i, j].append((nx, ny))
            a += 1

def shortest_bridge(i, j, m):
    a = mapp[i][j]
    que = boundary[i, j]
    visited = set(que)
    d = 1
    while d < m and que:
        new_que = []
        for x, y in que:
            for ddx, ddy in zip(dx, dy):
                nx, ny = x + ddx, y + ddy
                if 0 <= nx < n > ny >= 0:
                    if a != mapp[nx][ny] and (nx, ny) not in visited:
                        if mapp[nx][ny] != 0:
                            return d
                        visited.add((nx, ny))
                        new_que.append((nx, ny))
        que = new_que
        d += 1
    return m

m = 10000
for i, j in boundary:
    m = shortest_bridge(i, j, m)
print(m)

---

데이터 추가로 틀리게 된 코드.... => 다른섬을 만날때까지 최소거리를 찾는과정이었다...알고보니.. ㅎ

import sys
from collections import deque

N=0
MAP=[]
visited=None
outter=None

q0=deque() #섬번호 부여
q1= deque() #바다가 인접한 섬위치를 저장하는 역할.-> 섬을 확장.

# 현위치의 상/하/좌/우
dy=[-1,1,0,0]
dx=[0,0,-1,1]

def isRange(y,x):
    global N
    if (y>=0 and y<N) and (x>=0 and x<N):
        return True
    return False

def bfs_labeling(cury, curx, label_number):
    global MAP, visited
    #매개변수를 큐에 추가한다.
    q0.append((cury, curx, label_number))
    
    while q0:
        y, x,  label= q0.popleft()
        if not visited[y][x]:
            visited[y][x]=True #방문
            MAP[y][x]=label #섬번호 부여

            water_cnt=0 #주변에 바다가 접해있는지 확인.
            #현위치의 상/하/좌/우가 바다가 아닌 육지(1)라면
            for i in range(4):
                nexty, nextx= y+dy[i], x+dx[i]
                
                if isRange(nexty, nextx):
                    #현위치의 주변에 바다가 있는지 확인해야한다.
                    if MAP[nexty][nextx]==0:
                        water_cnt+=1
                        
                    #방문을 하지 않았고, 육지라면.-> 육지번호를 부여
                    if (not visited[nexty][nextx]) and (MAP[nexty][nextx]==1):
                        q0.append((nexty, nextx, label))
            if water_cnt>0:
                #주변에 바다가 1개이상이라면있다면, 바다와 인접한 위치이다.
                #0은 다른섬이 나올때까지의 경로를 카운트한다.
                q1.append((y,x,label,0))

def bfs(island_cnt):#island_cnt: 섬개수
    global visited, MAP
    #최소거리를 구한다.
    dist=[0]*(island_cnt)
    
    #q1은 바다와 인접한 섬의 위치이다. (이미 방문한 상태)
    #점점 섬번호로 확장해나간다. 그 위치의 주변이 서로다른 섬번호라면
    #현위치섬번호가 간거리 + 다른섬번호가 간거리 합으로 리턴한다.
    while q1:
        y, x, label, d=q1.popleft()
        MAP[y][x]=label
        dist[label-1]=d

        #현위치 주변에 아직 방문하지 않은 바다가 있는지 탐색한다. 그리고 dist[label]을 카운트한다.
        #만일 바다가 아닌 다른 섬번호라면 dist[현재섬번호]+dist[인접다른섬번호] 를 리턴
        for i in range(4):
            nexty, nextx= y+dy[i], x+dx[i]
            if isRange(nexty, nextx):
                #바다가 아닌 다른 섬번호이면.
                if (MAP[nexty][nextx]>0) and (MAP[nexty][nextx]!=label):
                    return dist[label-1]+dist[MAP[nexty][nextx]-1]
                
                elif (not visited[nexty][nextx]) and (MAP[nexty][nextx]==0):
                    visited[nexty][nextx]=True #방문을 한다.
                    q1.append((nexty, nextx, label, d+1))

               
def main():
    global N, MAP, visited
    N=int(sys.stdin.readline()) #지도의 크기 입력
    visited=[[False]*N for _ in range(N)]  #방문리스트 입력
    
    for _ in range(N): #지도그리기
        MAP.append( list( map(int, sys.stdin.readline().split()) ) )

    #지도번호 라벨링
    label_number=1
    island_cnt=0 #섬개수 카운트
    for y in range(N):
        for x in range(N):
            if (MAP[y][x]!=0) and (not visited[y][x]):
                bfs_labeling(y,x, label_number)
                island_cnt+=1#섬개수 카운트
                label_number+=1
    print(bfs(island_cnt)) #bfs실행.
    #큐를 비운다.
    q0.clear()
    q1.clear()
       
      
if __name__=='__main__':
    main()

 

13일이 지난 뒤에 데이터가 추가됐는데

맞았다고 표시된 내 코드가 틀린 상태로 변경됐다.

어디가 문제일까..ㅠㅜ

---

[ 코드 1 (python) ]

* 나의풀이 *

- DFS: 라벨링 (섬에 번호를 붙인다. 1,2,3,...)

- BFS: 섬에서 바다와 인접한 부분을 구해서 큐에 넣는다. (water_cnt가 1이상인 좌표를 큐에 넣는다.)

 

- BFS를 이용하여 현재 섬 라벨번호와 다른 라벨번호를 만날때까지의 거리(d)를 구한다.

- 다른 섬에 도달할때 d에서 1을 뺀다. 

- 다른 섬에 도달할 때까지 가장 짧은 경로를 구한다. (minimum_distance)

- 테스트 케이스 통과

- 결과: 23% 에서 시간초과

- BFS, DFS를 두번쓰는 것 같다.

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**6)
N=0
MAP=[]
visited=None
outter=None

q= deque()

# 현위치의 상/하/좌/우
dy=[-1,1,0,0]
dx=[0,0,-1,1]

def isRange(y,x):
    global N
    if (y>=0 and y<N) and (x>=0 and x<N):
        return True
    return False
                
def dfs_labeling(y, x, label_number):
    global MAP, visited
    if not visited[y][x]: #방문했는가?
        visited[y][x]=True #현위치 방문하고
        MAP[y][x]=label_number
        
        for i in range(4):
            nexty= y+dy[i]
            nextx= x+dx[i]
            
            #현위치의 상/하/좌/우 가 연결되어있는지 확인
            if isRange(nexty, nextx):
                #아직 방문하지 않았고, 0이 아닌 값이라면
                if (not visited[nexty][nextx]) and (MAP[nexty][nextx]!=0):
                    dfs_labeling(nexty, nextx, label_number)

def bfs():
    global MAP, visited, N
    min_number=float('inf')
    visited=[[False]*N for _ in range(N)] #방문리스트 다시 초기화
    while q:
        y,x, label_number, d= q.popleft()
        #만일 label_number가 0보다 큰 다른숫자라면
        if (MAP[y][x]>0) and (MAP[y][x]!=label_number):
            min_number=min(min_number, d-1)
            
        if not visited[y][x]: # 현위치를 방문하지 않았다면
            visited[y][x]=True
            #현위치 주변이 label_number이 아닌 수라면
            for i in range(4):
                nexty=y+dy[i]
                nextx=x+dx[i]
                if isRange(nexty, nextx):
                    if (not visited[nexty][nextx]) and (MAP[nexty][nextx]!=label_number):
                        q.append((nexty, nextx, label_number, d+1))
    return min_number
                
def main():
    global N, MAP, visited, outter
    N=int(sys.stdin.readline()) #지도의 크기 입력
    visited=[[False]*N for _ in range(N)]  #방문리스트 입력
    
    for _ in range(N): #지도그리기
        MAP.append( list( map(int, sys.stdin.readline().split()) ) )

    #지도번호 라벨링
    label_number=1
    for y in range(N):
        for x in range(N):
            if (MAP[y][x]!=0) and (not visited[y][x]):
                dfs_labeling(y,x, label_number)
                label_number+=1

    min_distance=float('inf') # 섬과 섬사이의 최소거리 무한대로 초기화
    for y in range(N):
        for x in range(N):
            if (MAP[y][x]!=0): #0이 아닌 섬이라면
                water_cnt=0
                #현위치에 바다가(0)의 개수를 카운트
                for i in range(4):
                    nexty=y+dy[i]
                    nextx=x+dx[i]
                    if isRange(nexty, nextx):
                        # 주변에 바다가 있는가?
                        if (MAP[nexty][nextx]==0):
                            water_cnt+=1
                if water_cnt>0:
                    q.append((y,x,MAP[y][x], 0))#현위치를 큐에 넣고
                    min_distance=min(min_distance, bfs())# bfs()탐색결과에서 섬사이의 최소거리를 구한다.
                        
    print(min_distance)
    
if __name__=='__main__':
    main()

---

[ 코드2 (python) ]

- DFS : 섬번호 라벨링

- 큐 2개를 이용했다.

  - 큐1: 바다와 인접한 위치를 저장하여 BFS를 탐색하여 현재위치에 가장짧은 거리를 구한다.

    그래서 여러개의 바다 인접위치들중 가장 짧은 거리를 찾는다.

 

  - 큐2: 바다와 인접한 섬의 위치에서 다른 섬이 나올때까지의 거리를 구한다. (여기서 BFS) 활용

  - 바다와 인접한 섬위치에서 다른 섬 나올때까지 가장짧은 거리를 구한뒤에 큐2를 비운다.

- 결과: 런타임 에러 ㅠ

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**6)
N=0
MAP=[]
visited=None
outter=None

q1= deque() #바다가 인접한 노드들의 순서를 나타내는 역할.
q2=deque() # 바다인접한 라벨에서 다른라벨이 올때까지 최소거리를 구하는 역할

# 현위치의 상/하/좌/우
dy=[-1,1,0,0]
dx=[0,0,-1,1]

def isRange(y,x):
    global N
    if (y>=0 and y<N) and (x>=0 and x<N):
        return True
    return False
                
def dfs_labeling(y, x, label_number):
    global MAP, visited
    if not visited[y][x]: #방문했는가?
        visited[y][x]=True #현위치 방문하고
        MAP[y][x]=label_number
        water_cnt=0
        for i in range(4):
            nexty= y+dy[i]
            nextx= x+dx[i] 
            #현위치의 상/하/좌/우 가 연결되어있는지 확인
            if isRange(nexty, nextx):
                #아직 방문하지 않았고, 0이 아닌 값이라면
                if (not visited[nexty][nextx]) and (MAP[nexty][nextx]!=0):
                    dfs_labeling(nexty, nextx, label_number)
                #주변에 바다(0)이 있다면 water_cnt를 카운트
                if MAP[nexty][nextx]==0:
                    water_cnt+=1
                    
        #water_cnt가 1개이상이라도 있다면, 현위치를  q1에 추가한다.
        if water_cnt>0:
            q1.append((y,x,label_number, 0))


def bfs1():
    #q1은 바다가 인접한 좌표를 나타냈다.
    #q1에 저장된 차례대로 pop하여 bfs2()를 탐색해서 최소거리를 구한뒤
    #가장 짧은 거리를 구한다.
    minimum_distance=float('inf') #최소 거리를 무한대로 가정한다.
    while q1:
        y,x,label_number, d= q1.popleft()
        bfs2_result= bfs2(y , x, label_number, d)
        q2.clear() #다른 섬에 도달했다면 q2를 비워야한다.
        minimum_distance= min(minimum_distance, bfs2_result)
    return minimum_distance

def bfs2(y,x, label_number, d):
    global MAP, visited, N

    visited=[[False]*N for _ in range(N)] #방문리스트 다시 초기화
    #bfs2 매개변수에 해당하는 값들을 먼저 큐에 넣는다.
    q2.append((y,x, label_number, d))
    
    while q2:
        y,x, label_number, d= q2.popleft()
        #만일 label_number가 0보다 큰 다른숫자라면
        #d-1: 다른섬에 도달하기 직전까지의 거리를 리턴하므로 
        if (MAP[y][x]>0) and (MAP[y][x]!=label_number):
            return d-1
            
        if not visited[y][x]: # 현위치를 방문하지 않았다면
            visited[y][x]=True
            #현위치 주변이 label_number이 아닌 수라면
            for i in range(4):
                nexty=y+dy[i]
                nextx=x+dx[i]
                if isRange(nexty, nextx):
                    if (not visited[nexty][nextx]) and (MAP[nexty][nextx]!=label_number):
                        q2.append((nexty, nextx, label_number, d+1))
                        
                
def main():
    global N, MAP, visited, outter
    N=int(sys.stdin.readline()) #지도의 크기 입력
    visited=[[False]*N for _ in range(N)]  #방문리스트 입력
    
    for _ in range(N): #지도그리기
        MAP.append( list( map(int, sys.stdin.readline().split()) ) )

    #지도번호 라벨링
    label_number=1
    for y in range(N):
        for x in range(N):
            if (MAP[y][x]!=0) and (not visited[y][x]):
                dfs_labeling(y,x, label_number)
                label_number+=1

    print(bfs1()) #bfs1실행.
    
if __name__=='__main__':
    main()

---

[ 코드3 (python) ]

- 섬번호 부여를 DFS가 아닌 BFS를 사용했습니다.

(그러나 결과는 역시나 런타임 에러 ㅠ)

import sys
from collections import deque
sys.setrecursionlimit(10**6)
N=0
MAP=[]
visited=None
outter=None

q1= deque() #바다가 인접한 노드들의 순서를 나타내는 역할.
q2=deque() # 바다인접한 라벨에서 다른라벨이 올때까지 최소거리를 구하는 역할

# 현위치의 상/하/좌/우
dy=[-1,1,0,0]
dx=[0,0,-1,1]

def isRange(y,x):
    global N
    if (y>=0 and y<N) and (x>=0 and x<N):
        return True
    return False
                
def bfs_labeling(cury, curx, label_number):
    global MAP, visited
    #매개변수를 큐에 추가한다.
    q0.append((cury, curx, label_number))
    
    while q0:
        y, x,  label= q0.popleft()
        if not visited[y][x]:
            visited[y][x]=True #방문
            MAP[y][x]=label #섬번호 부여

            water_cnt=0 #주변에 바다가 접해있는지 확인.
            #현위치의 상/하/좌/우가 바다가 아닌 육지(1)라면
            for i in range(4):
                nexty= y+dy[i]
                nextx= x+dx[i]
                if isRange(nexty, nextx):
                    #현위치의 주변에 바다가 있는지 확인해야한다.
                    if MAP[nexty][nextx]==0:
                        water_cnt+=1
                        
                    #방문을 하지 않았고, 육지라면.-> 육지번호를 부여
                    if (not visited[nexty][nextx]) and (MAP[nexty][nextx]==1):
                        q0.append((nexty, nextx, label))
            if water_cnt>0:
                #주변에 바다가 1개이상이라면있다면, 바다와 인접한 위치이다.
                #0은 다른섬이 나올때까지의 경로를 카운트한다.
                q1.append((y,x,label,0))


def bfs1():
    #q1은 바다가 인접한 좌표를 나타냈다.
    #q1에 저장된 바다인접 좌표를 차례대로 pop한뒤, bfs2()를 탐색해서 최소거리를 구한다.
    #가장 짧은 거리를 구한다.
    minimum_distance=float('inf') #최소 거리를 무한대로 가정한다.
    while q1:
        y,x,label_number, d= q1.popleft()
        bfs2_result= bfs2(y , x, label_number, d)
        q2.clear() #다른 섬에 도달했다면 q2를 비워야한다.
        minimum_distance= min(minimum_distance, bfs2_result)
    return minimum_distance

def bfs2(cury,curx, cur_label_number, cur_d):
    global MAP, visited, N

    visited=[[False]*N for _ in range(N)] #방문리스트 다시 초기화
    #bfs2 매개변수에 해당하는 값들을 먼저 큐에 넣는다.
    q2.append((cury,curx, cur_label_number, cur_d))
    
    while q2:
        y,x, label_number, d= q2.popleft()
        #만일 label_number가 0보다 큰 다른숫자라면
        #d-1: 다른섬에 도달하기 직전까지의 거리를 리턴하므로 
        if (MAP[y][x]>0) and (MAP[y][x]!=label_number):
            return d-1
            
        if not visited[y][x]: # 현위치를 방문하지 않았다면
            visited[y][x]=True
            #현위치 주변이 label_number이 아닌 수라면
            for i in range(4):
                nexty=y+dy[i]
                nextx=x+dx[i]
                if isRange(nexty, nextx):
                    if (not visited[nexty][nextx]) and (MAP[nexty][nextx]!=label_number):
                        q2.append((nexty, nextx, label_number, d+1))
                        
                
def main():
    global N, MAP, visited, outter
    N=int(sys.stdin.readline()) #지도의 크기 입력
    visited=[[False]*N for _ in range(N)]  #방문리스트 입력
    
    for _ in range(N): #지도그리기
        MAP.append( list( map(int, sys.stdin.readline().split()) ) )

    #지도번호 라벨링
    label_number=1
    for y in range(N):
        for x in range(N):
            if (MAP[y][x]!=0) and (not visited[y][x]):
                bfs_labeling(y,x, label_number)
                label_number+=1

    print(bfs1()) #bfs1실행.
    
if __name__=='__main__':
    main()

---

[ 코드4 (python) ]

- 참고: https://mygumi.tistory.com/109

- BFS : 섬번호 부여, 바다와 인접한 섬위치를 큐에 삽입

- BFS : 바다와 인접한 섬위치를 출발점으로 하여 바다라면 점점확장시킨다.

  : 주변이 만일 다른섬번호라면 종료하고 dist[현재섬번호 달린거리]+dist[다른섬번호 달린거리].

- (69%)에서 PyPy: 메모리 초과/ Python3: 시간초과 

=> 틀린이유: bfs()함수에서 아직 방문하지 않았고, 주변이 바다(MAP[nexty][nextx]=0)일때 방문을 안했다...ㅎ

import sys
from collections import deque

N=0
MAP=[]
visited=None
outter=None

q0=deque() #섬번호 부여
q1= deque() #바다가 인접한 섬위치를 저장하는 역할.-> 섬을 확장.

# 현위치의 상/하/좌/우
dy=[-1,1,0,0]
dx=[0,0,-1,1]

def isRange(y,x):
    global N
    if (y>=0 and y<N) and (x>=0 and x<N):
        return True
    return False

def bfs_labeling(cury, curx, label_number):
    global MAP, visited
    #매개변수를 큐에 추가한다.
    q0.append((cury, curx, label_number))
    
    while q0:
        y, x,  label= q0.popleft()
        if not visited[y][x]:
            visited[y][x]=True #방문
            MAP[y][x]=label #섬번호 부여

            water_cnt=0 #주변에 바다가 접해있는지 확인.
            #현위치의 상/하/좌/우가 바다가 아닌 육지(1)라면
            for i in range(4):
                nexty, nextx= y+dy[i], x+dx[i]
                
                if isRange(nexty, nextx):
                    #현위치의 주변에 바다가 있는지 확인해야한다.
                    if MAP[nexty][nextx]==0:
                        water_cnt+=1
                        
                    #방문을 하지 않았고, 육지라면.-> 육지번호를 부여
                    if (not visited[nexty][nextx]) and (MAP[nexty][nextx]==1):
                        q0.append((nexty, nextx, label))
            if water_cnt>0:
                #주변에 바다가 1개이상이라면있다면, 바다와 인접한 위치이다.
                #0은 다른섬이 나올때까지의 경로를 카운트한다.
                q1.append((y,x,label,0))

def bfs(island_cnt):#island_cnt: 섬개수
    global visited, MAP
    #최소거리를 구한다.
    dist=[0]*(island_cnt)
    
    #q1은 바다와 인접한 섬의 위치이다. (이미 방문한 상태)
    #점점 섬번호로 확장해나간다. 그 위치의 주변이 서로다른 섬번호라면
    #현위치섬번호가 간거리 + 다른섬번호가 간거리 합으로 리턴한다.
    while q1:
        y, x, label, d=q1.popleft()
        MAP[y][x]=label
        dist[label-1]=d

        #현위치 주변에 아직 방문하지 않은 바다가 있는지 탐색한다. 그리고 dist[label]을 카운트한다.
        #만일 바다가 아닌 다른 섬번호라면 dist[현재섬번호]+dist[인접다른섬번호] 를 리턴
        for i in range(4):
            nexty, nextx= y+dy[i], x+dx[i]
            if isRange(nexty, nextx):
                #바다가 아닌 다른 섬번호이면.
                if (MAP[nexty][nextx]>0) and (MAP[nexty][nextx]!=label):
                    return dist[label-1]+dist[MAP[nexty][nextx]-1]
                
                elif (not visited[nexty][nextx]) and (MAP[nexty][nextx]==0):
                    q1.append((nexty, nextx, label, d+1))

               
def main():
    global N, MAP, visited
    N=int(sys.stdin.readline()) #지도의 크기 입력
    visited=[[False]*N for _ in range(N)]  #방문리스트 입력
    
    for _ in range(N): #지도그리기
        MAP.append( list( map(int, sys.stdin.readline().split()) ) )

    #지도번호 라벨링
    label_number=1
    island_cnt=0 #섬개수 카운트
    for y in range(N):
        for x in range(N):
            if (MAP[y][x]!=0) and (not visited[y][x]):
                bfs_labeling(y,x, label_number)
                island_cnt+=1#섬개수 카운트
                label_number+=1
    print(bfs(island_cnt)) #bfs실행.
       
      
if __name__=='__main__':
    main()