2665 백준 파이썬

미로 찾기 + A같은 느낌...

처음에는 dfs를 통해 계속 고르는 개수를 증가시키면서 해결하려고 했으나 결국은 검은 방도 모두 탐색해야하므로, 흰방을 모두 탐색한 뒤에, 검은방 탐색시키면 됐었던 문제.

그래서 흰방은 append를 해줬고, 검은 방은 appendleft를 해주었다.

결국은 bfs의 bfs. 였다.

 

탐색에 대한 생각을 다시한번 하게 해줬던 문제.

#https://www.acmicpc.net/problem/2665
from collections import deque
def bfs(x,y):
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    q=deque()
    q.append((x,y))
    while q:
        x,y=q.popleft()
        for i in range(4):
            X=x+dx[i]
            Y=y+dy[i]
            if 0<=X<n and 0<=Y<n:
                if vis[X][Y]==-1:
                    if m[X][Y]==0:
                        vis[X][Y]=vis[x][y]+1
                        q.append((X,Y))
                    else:
                        vis[X][Y]=vis[x][y]
                        q.appendleft((X,Y))
n=int(input())
m=[]
ch=0
for x in range(n):
    x=list(input())
    x=list(map(int,x))
    m.append(x)
vis=[[-1 for _ in range(n)] for _ in range(n)]
vis[0][0]=0
bfs(0,0)
print(vis[-1][-1])