[알고리즘][파이썬] 2178-미로 탐색

문제

 

코드

import sys
from collections import deque  #60m

r,c = map(int,sys.stdin.readline().strip().split())

graph = []  
visited = [[False]*c for _ in range(r)]

for _ in range(r):
   graph.append(list(map(int,sys.stdin.readline().strip()))) 




dx =[1,-1,0,0]
dy =[0,0,1,-1]
visited[0][0]=True

q= deque()
q.append((0,0,1))
f=0

while(q):
    cx,cy,count= q.popleft()
    for i in range(4):
        nx = cx+dx[i]
        ny = cy+dy[i]
        if(nx>=0 and nx<r and ny>=0 and ny<c):
            if( not visited[nx][ny] and graph[nx][ny]== 1):  
                if(nx==r-1 and ny==c-1):
                    print(count+1)
                    f=1
                    break
                    
                visited[nx][ny]=True
                q.append((nx,ny,count+1))
    if(f==1) : break

문제이해

1과 0으로 이루어진 그래프에서 1의 칸으로만

[0.0]에서 [N-1,M-1]까지 갈 수 있는 최단 거리를 구하는 문제이다. 

 

코드 설계

그래프를 입력받고 (0.0)부터 BFS탐색을 시작한다.

탐색중 (n-1,M-1)칸에 도착하면 탐색을 멈추고 count한 값을 출력한다.

 

BFS탐색 중 큐에 데이터를 갱신할 때 지나온 칸의 수를 누적해서 계산해야 하기 때문에

큐에 데이터를 삽입할 때 좌표값과 count값을 넣을 수 있도록 설계한다.

 

queue.append((x,y,count+1)) 이런 식으로 count 값이 갱신될 수 있도록 한다.

 

 

+추가 코드 

graph값에 직접 count를 누적한 코드이다. 

import sys
from collections import deque

r,c = map(int, sys.stdin.readline().strip().split())

graph = []
visited=[[False]*c for _ in range(r)]
for i in range(r):
    graph.append(list(map(int,sys.stdin.readline().strip())))


dx = [1,-1,0,0]
dy = [0,0,1,-1]

visited[0][0]=True
q=deque()
q.append((0,0))

while(q):
    cx,cy = q.popleft()
    for i in range(4):
        nx =cx+dx[i]
        ny = cy+dy[i]
        if(nx>=0 and nx < r and ny>=0 and ny <c):
            if(graph[nx][ny]==1 and not visited[nx][ny]):
                visited[nx][ny]=True
                graph[nx][ny]=graph[cx][cy]+1
                q.append((nx,ny))

print(graph[r-1][c-1])