[Algorithm] DFS/BFS - 4

[미로 탈출]

- NxM크기의 미로

- 시작 위치는 (1,1), 미로의 출구는 (N,M)

- 괴물이 있는 부분은 0, 괴물이 없는 부분은 1

- 탈출하기 위해 움직여야하는 최소 칸의 개수 출력 (칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산)

위와 같은 예시 인 경우, 총 움직여야 하는 칸의 개수는 다섯칸

 

[해석]

- 무조건 기억 ! DFS : 스택, 재귀 / BFS : deque (이게 헷갈려서 스택으로 풀 뻔 했다..)

- 최소 머시기를 구하라는 문제는 BFS로 탐색하면 될듯 하다

- 이 문제를 처음 봤을 때, 4방향을 살피고 괴물 유무를 파악한 후에 좌표 이동하는 것 까지 생각이 났지만 좌표 리스트를 어떻게 deque에 넣지? 라는 생각을 했따 (하지만 너무 간단한 방법..set() 방법을 사용해서 넣는 것이어따,,)

- deque에 첫 좌표를 넣고 4방향을 살핌 (4방향에 대한 리스트 값 미리 지정해야함)

- 만약, 벽이거나 이동 좌표에 괴물이 위치한다면 이동 하지 않음

- 그렇지 않다면 이동좌표 값에 1을 더해준다 - 왜냐고? 아래와 같이 생각하면 됨

이렇게 다음 좌표 값에 1을 더해주면 내가 움직이는 칸의 개수가 된다!! (** 이건 진짜 생각도 못했다 두둥..)

- 그런 다음에 이동 좌표를 다시 append 해주고 popleft해주고 위의 과정을 반복

- 이렇게 진행되고 마지막 즉, (n,m) 좌표에 위치한 값을 출력하면 끝..!

 

[코드] # 참고하였음

from collections import deque
n,m = map(int, input().split())

graph = []
for i in range(n): ## 이미 여기서 stack, list 만든거임
    graph.append(list(map(int, input()))) ## split을 안하면 입력할때 띄어쓰기로 입력 안해도 됨

## bfs : queue
## dfs : stack, 재귀

print(graph)

dx = [-1, 1, 0,0] ## 상하좌우
dy = [0, 0, -1, 1]

def bfs(x,y):
    q = deque()
    q.append((x,y))


    while q:

        x,y = q.popleft()

        for i in range(4): ## 4방향 탐색
            nx = x + dx[i]
            ny = y + dy[i]

            if nx >= n or nx < 0 or ny >= m or ny < 0: ## 크기 벗어나는지 확인
                continue

            if graph[nx][ny] == 0: ## 괴물 유무 확인
                continue

            if graph[nx][ny] == 1: ## 괴물이 없다면?
                graph[nx][ny] = graph[x][y] + 1 ## 해당좌표값 +1

                q.append((nx,ny)) ## 큐에 이동한 좌표 새로 삽입

    return graph[n-1][m-1] ## 마지막 좌표 값 출력 = 움직인 칸의 개수

print(bfs(0,0))

Ref : 나동빈, "이것이 코딩테스트다"