[백준] 2178번 - 미로탐색 (파이썬)

문제링크

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

2178번: 미로 탐색

 

나의풀이

1. 대부분의 그래프탐색 문제는 dfs,dfs로 풀리고 dx, dy를 활용하여 풀면 된다는 사실을 알게되었다.
2. 초반에 방문하고자하는 노드를 0,0으로 놓고 하나씩 주변 노드를 검색해가며 옮겨가면된다!
3. 해당 문제처럼 마지막에 "최단거리"를 구하는 문제와 같이 위치가 아니라 진행수를 구하는 문제면 +=1씩 해나아간 행렬을 하나 더 만든 후(해당 문제에서 dist) 구해주는것이 편하다.

from collections import deque
n,m = map(int, input().split())
matrix = [list(map(int, list(input()))) for _ in range(n)]

visited = [[False] * m for _ in range(n)]
dist = [[0] * m for _ in range(n)] #거리 +1 씩 해줄거고 마지막에 이거 출력할거임
queue = deque()
queue.append((0,0)) #시작점
dist[0][0] = 1 #시작점 거리는 1로 해줌

#방향키
#dx[0] dx[0] : 왼쪽
#dx[1] dx[1] : 오른쪽
#dx[2] dx[2] : 위
#dx[3] dx[3] : 아래
dx = [0,0,-1,1]
dy = [-1,1,0,0]

while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0  <= nx < n and 0 <= ny < m:#그래프 벗어나면 안돼
            if visited[nx][ny] == False and matrix[nx][ny] == 1: #방문노드가 아니고, matrix에 1이 있는위치면 위치 바꿔주기
                queue.append((nx, ny))
                dist[nx][ny] += dist[x][y] + 1 #dist에서 x,y는 1이니까 그거보다 +1 해줘서 넣어줌 (2)
                visited[nx][ny] = True #방문처리까지
                
print(dist[n-1][m-1]) #n,m은 갯수니까 행렬에서는 -1씩