미로 탈출

이 문제는 이것이 코딩테스트다. 152페이지 문제이다.

BFS문제를 많이 다뤄 보지 않았어서 시간이 오래 소모 되었던 것같다.

DFS,BFS는 양식이 거의 비슷하니깐 틀자체를 기본적으로 몸에 익혀야겠다.

아래는 나의 코드이다.

 

import sys
from collections import deque

N,M = map(int,sys.stdin.readline().split())
myMap = []
visited=[[False]*M for _ in range(N)]
moves = [[1,0],[0,1],[-1,0],[0,-1]]
for i in range(N):
    temp=list(map(int,sys.stdin.readline().split()[0]))
    myMap.append(temp)

def BFS(start,end):
    que= deque()
    que.append(start)
    while que:
        q=que.popleft()
        if q[0] == end[0] and q[1] == end[1]:
            return myMap[end[0]][end[1]]
        visited[q[0]][q[1]] = True
        for move in moves:
            nq_x=q[0]+move[0]
            nq_y=q[1]+move[1]
            if nq_x < 0 or nq_y< 0 or nq_x > end[0] or nq_y > end[1]:
                continue
            if myMap[nq_x][nq_y] == 0 or visited[nq_x][nq_y] == True:
                continue
            if myMap[nq_x][nq_y] == 1:
                myMap[nq_x][nq_y] = myMap[q[0]][q[1]] + 1
            que.append([nq_x,nq_y])
    return "No way"


print(BFS([0,0],[N-1,M-1]))

 

만약 경로를 출력하는 문제가 나온다면 역순으로 한번 더 조사하는 방법을 쓰면 될 것같다. 10 -> 9 ->8->7 순으로

 

이러한 최단거리나 최단경로 구하는 문제에서는 DFS를 사용하면 시간초과가 날 수 있다.

길의 갈래가 무수히 많아 질 수 있기 때문이다.

BFS를 잘 활용해보자