2146 - BFS

BFS는 개념적으로 이해할 땐 쉽게 느껴지지만
마음먹고 어렵게 내면 어려운 알고리즘이다.

0. 범위를 벗어나면 Continue (기본)
1. 큐에 넣어야 하는 것들을 명확히 해야한다.
2. 종결 조건에 대해 명확해야함. 특히 큐의 시작점이 여러개라면
3. 대체로 while(q)문이 다 돌고 나서야 반환해야 옳은 정답을 내는 경우가 많다.
   (만나는 경우라도 그게 반드시 최소값을 보장하진 않기 때문)
4. 반례는 그리 복잡하지 않은 곳에서 나온다.(공통이기도 함)

접근 :
섬의 소속별로 배열에 저장할 필요성 느끼고 받아오는 것에서부터 그대로 받지 않고 [,]식으로 받아옴
[0]에는 값을, [1]에는 소속을 저장
섬의 최전방을 탐색후 다른 큐에 넣고 배열은 1로(다리의 최초길이) 초기화
최전방들로부터 BFS 진행.
pop후에 벡터중에 자신과 다른 소속을 만나면 리턴.

챌린징 Point

1. 연산의 최적화를 위해 BFS를 돌리고 섬의 경계에서 다른 큐로 넣었는데,
   섬과 다리의 구분이 어려워 이를 수정하는 것에 꽤나 애를 먹었다.
   ㄴ> n=2일때, [1, 0][0, 1] 처럼 한 번에 끝나는데 다리, 섬 구분이 안되면 2출력했음
   >>> 섬의 경우 그냥 0 = 0으로 초기화하고 다리들을 오히려 1부터 넣어서 구분

2. [2][2] - [2][3]의 만나는 지점이 생겼다고 바로 반환해서는 안된다.
   기존에 넣었던 것들에서 더 짧게 만나는 경우가 나오기 때문.
   ㄴ>n=5 라면
   1 1 0 0 0
   0 1 0 0 0
   0 0 0 0 1
   0 0 1 0 1
   0 0 0 0 0

---

구현

import sys
from collections import deque

n = int(input())


def BFS(b,a,cnt):
	if (L[b][a][0] == 0 or L[b][a][1]):
		return False
	q = deque()
	L[b][a][1] = cnt
	q.appendleft((b,a))
	while(q):
		y,x = q.pop()
		ny = [1,0,-1,0]
		nx = [0,1,0,-1]
		L[y][x][0] = 0 #섬으로 바꾸려는 의도
		for w in range(4):
			dy = y + ny[w]
			dx = x + nx[w]
			if (dy < 0) or (dx < 0)  or (dy >= n) or (dx >= n):
				continue
			if (L[dy][dx][1]):
				continue
			if (L[dy][dx][0] == 1) and (L[dy][dx][1] == 0):
				L[dy][dx][1] = cnt
				q.appendleft((dy,dx))
				continue
			if (L[dy][dx][0] == 0) and (L[dy][dx][1] == 0): #후 조건 추가
			#값을 바꾸긴 해야함
				L[dy][dx][0] = 1
				L[dy][dx][1] = cnt
				frq.appendleft((dy,dx,cnt))
	return True
	#frq.appendleft(()) 최전방일때 담을 것

def BFS2():
	mmin = 10001
	while(frq):
		y,x,t = frq.pop()
		ny = [1,0,-1,0]
		nx = [0,1,0,-1]
		mini = []
		for r in range(4):
			dy = y + ny[r]
			dx = x + nx[r]
			if (dy < 0) or (dx < 0)  or (dy >= n) or (dx >= n):
				continue
			if L[dy][dx][1] == t:
				continue
			if (L[dy][dx][0] == 0) and (L[dy][dx][1] == 0):
				L[dy][dx][0] = L[y][x][0] + 1
				L[dy][dx][1] = t
				frq.appendleft((dy,dx,t))
				continue
			if (L[dy][dx][1] != t):
				mini.append(L[dy][dx][0])
		if mini:
			temp = (min(mini) + L[y][x][0])
			if temp < mmin:
				mmin = temp
	return mmin
	

L=[]
for _ in range(n):
	L.append(list(map(list,sys.stdin.readline().strip().split())))
for i in range(n):
	for j in range(n):
		L[i][j][0] = int(L[i][j][0])
		L[i][j].append(0)

##섬의 구분과 섬의 최전방을 담는 과정
frq = deque()
cnt = 1
for ii in range(n):
	for jj in range(n):
		if BFS(ii,jj,cnt):
			cnt+=1
print(BFS2())