[python3] 이코테 - 미로탈출 (ch5. DFS/BFS)

참고) 이것이 취업을 위한 코딩테스트다 with 파이썬 책을 기반으로 작성된 문제와 코드입니다. 
따라서 문제는 자세하게 적지 않고, 간단한 설명과 제 코드만 올리겠습니다.

 

실전문제(2) 미로탈출

- NxM 의 미로
- 시작 위치는 (1,1), 탈출구는 (N,M)
- 갈 수 있는 길 1, 괴물이 존재하는 칸 0
- 탈출하기 위해 거치는 칸의 최소 개수를 구하기

##### 입력조건
- 첫쨋줄에 N,M 주어짐
- 4 <= N,M <= 200
- 둘쨋줄 부터는 미로에 대한 정보 (1 or 0)
- (1,1) (N,M)은 항상 1

 

<문제풀이>

1. 첫번째 시도

queue를 활용하지 않고 구현형식(반복문) 형태로 풀었는데 너무 오래걸려서 시간초과가 뜰것 같다. 
그래서 책을 참고하여 queue를 활용하기로 결정했다.

2. 두번째 시도 및 오답노트

- 방문한 노드를 999로 바꾸는 형식을 활용했지만
- count 형식으로 풀었는데, 코드 특성상 모든 1을 거치기 때문에 1인 값이 모두 999로 바뀐다.
- 따라서 999로 변화하는 값을 세어주게되면 결국 1의 갯수를 세는것과 같아진다.
- 하는 수 없이 책을 참조하여 1, 2, 3, ,,, 이렇게 값을 더해주는 방식으로 구현했다. 진짜...어렵다 알고리즘 ...
- 더해 준다는 것?  1번째로 방문한 (0,0)의 값이 1일것이다. 그리고 (0,0)과 인접한 1인 노드를 방문하게 될텐데 그 노드는 전부 2가 될것이다. 
- 전부 2로 변한 nx, ny 는 모두 큐에 들어가게 되고, 큐를 하나씩 빼오면서 또 그와 인접한 값들이 3으로 변한다. 이 과정에서 결국 1로 연결되어있는 길(?)만 3으로 변할 것이고, 인접한 길이 없을 경우 2에서 머무르게 된다.

from collections import deque
# 상하좌우 살펴보고 1이면 해당칸으로 이동, 그리고 result +1 하는 방식사용
#입력 받기
n, m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 1. 상하좌우 이동 방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
    
def bfs(x,y):

    q = deque()
    q.append((x,y)) # 0,0 큐에 넣고 시작
    
    while q: # 큐가 빌때까지
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # nx, ny가 범위를 벗어나면 무시하고 다음 i로
            if nx >= n or ny >= m or nx < 0 or ny < 0 :
                continue

            # nx, ny 노드가 괴물칸 (0) 인 경우도 다음 i로
            if graph[nx][ny] == 0:
                continue
            
            # 갈 수 있는 길인 1이면
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                q.append((nx,ny))
                
    return graph[n-1][m-1]

print(bfs(0,0))

• 출력

첫쨋줄 N M
둘쩃줄부터 N+1줄까지 배열에 대한 입력받음
마지막줄은 최종 출력 값