[백준_14923] 미로탈출_bfs_python

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

14923번: 미로 탈출

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

1600번: 말이 되고픈 원숭이

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

2206번: 벽 부수고 이동하기

3차원 그래프 탐색문제로  2차원 탐색에 조금 맛이 들렸다면 정복하기 재밌을만한 문제들이다.
한 평면에서의 탐색이 아니라 왜 다른 평면을 만들어 탐색을 이어나가야하는지 생각하기 좋은 문제들이다.

한 평면만으로 탐색이 안되는 이유는 무한탐색이 일어날 수 있기때문에 방문처리를 해주어야하고, 결과적으로 False를 리턴 할 pos가 방문처리를 먼저 해버리게 되었을때 문제가 발생하게 된다.벽을 깨 돌아가는 경우에서 True가 나오는 경우에 대해 차근히 생각해보면 좋을 것 같다.

from collections import deque
r,c = map(int,input().split())
graph = [list(input()) for _ in range(r)]
answer = 0
dxs,dys = [-1,0,1,0],[0,1,0,-1],  #URDL
visited = [[0]*c for _ in range(r)]

def in_range(x,y):
    return 0<=x<r and 0<=y<c
def bfs(x,y):
    global answer,arr

    visited[x][y] = -1
    que = deque()
    que.append((x,y))
    arr.append([x,y])
    while que:
        dx,dy = que.popleft()
        nx,ny = 0,0
        if graph[dx][dy] == 'U':
            nx,ny = dx + dxs[0], dy+dys[0]
        elif graph[dx][dy] =='R':
            nx,ny = dx + dxs[1], dy+dys[1]
        elif graph[dx][dy] =='D':
            nx,ny = dx + dxs[2], dy+dys[2]
        else:
            nx,ny = dx + dxs[3], dy+dys[3]

        #내부에서 탐색중일때
        if in_range(nx,ny) and visited[nx][ny]==0:
            visited[nx][ny] = visited[dx][dy] -1
            que.append((nx,ny))
            arr.append([nx,ny])
        elif in_range(nx,ny) and visited[nx][ny] < 0 :  #순환할때
            return False
        elif in_range(nx,ny) and visited[nx][ny] > 0:
            return -visited[dx][dy]
        elif not in_range(nx,ny):   #벗어나는 지점
            return -visited[dx][dy]

    return False

for i in range(r):
    for j in range(c):
        if not visited[i][j]:
            arr = []
            res= bfs(i,j)
            if res:
                answer += res
                for a,b in arr:
                    visited[a][b] = -visited[a][b]

print(answer)