BFS - 미로 탐색 [2178번]

BFS보다는 DFS로 풀이하는게 직관적이다 보니, BFS에 대한 풀이가 아직은 익숙하지 않다...

휴..이제 좀 열심히 해야지 ㅜㅜ

 

어쨌든 이번에도 역시나 DFS로 풀이를 했는데 시간초과가 났다...

해당 풀이는 아래와 같다.

def dfs(loc, curTime):
    global minTime
    if loc == [N-1, M-1]:
        minTime = min(minTime, curTime)
        return 
    
    chk = False
    for i in range(4):
        nx = loc[0]+dx[i]; ny = loc[1]+dy[i]
        if 0<=nx<N and 0<=ny<M and visited[nx][ny] == True:
            chk = True
            visited[nx][ny] = False
            dfs([nx, ny], curTime+1)
            visited[nx][ny] = True
            
    if chk == False:
        return
            
# 1 = 이동 가능한 칸, 0 = 이동 불가능한 칸
N, M = map(int, input().split())
miro = []; visited = []
minTime = 10000
dx = [1, 0, -1, 0]; dy = [0, 1, 0, -1]
for i in range(N):
    tmp = list(map(lambda x : int(x), list(input())))
    miro.append(tmp)
    
    tfList = list(map(lambda x : x == 1, tmp))
    visited.append(tfList)
    
dfs([0, 0], 1)
print(minTime)

 

일단 BFS 풀이에 앞서서 다시한번 DFS와 BFS에 적합한 유형을 정리해보자면,

 

 

• DFS & BFS 상관이 없는 유형
  • 단순 모든 정점을 방문하는 것이 중요한 문제인 경우
• DFS가 적합한 유형
  • 검색 대상 그래프가 큰 경우 = 정점과 간성의 개수가 큰 경우
  • 경로의 특징을 저장해야하는 경우 -> EX) A부터 B까지 가는 경로를 구하는데 있어서 같은 숫자가 있으면 안되는 경우 ( * BFS는 경로의 특징을 가지지 못 함)
• BFS가 적합한 유형
  • 미로찾기와 같이 최단거리 구해야 하는 경우
  • 현재 노드에서 가까운것 부터 구하기 때문에 경로 탐색 시, 첫번째로 찾아지는 해답이 곧 최단거리

아래는 BFS로 풀이한 결과이다.

보통 BFS의 핵심은 Queue 사용이다. 여기에 대한 익숙도가 높아져야할 것으로 보인다.

# 1 = 이동 가능한 칸, 0 = 이동 불가능한 칸
N, M = map(int, input().split())
miro = []
for i in range(N):
    tmp = list(map(lambda x : int(x), list(input())))
    miro.append(tmp)
    
from collections import deque
q = deque([(0,0)])
dx = [1, 0, -1, 0]; dy = [0, 1, 0, -1]
while q:
    x, y = q.popleft()
    for i in range(4):
        nx = x+dx[i]; ny = y+dy[i]
        if 0<=nx<N and 0<=ny<M and miro[nx][ny] == 1:
            miro[nx][ny] = miro[x][y] + 1
            q.append((nx, ny))
print(miro)
print(miro[N-1][M-1])