😊 백준 2178 : 미로 탐색

2178: 미로 탐색

DFS/BFS 다섯 번째 문제!

오늘은 군대 빡센 날,,, 23시에 블로그 글 쓰니까 제정신이 아니다.

📌 Try 1

# return -1 == 범위 초과 || 1 == 도착 || 0 ==  
def dfs(x, y, cnt):
    if x < 0 or x >= N or y < 0 or y >= M:
        return -1
    elif x == N-1 and y == M-1:
        result.append(cnt)
        return -1
        
    flag = 0
    
    if graph[x][y] == 1:
        graph[x][y] = 0
        
        # for j in graph:
        #     print(j)
        # print(x, y, cnt)
        
        flag += dfs(x+1, y, cnt+1)
        flag += dfs(x, y+1, cnt+1)
        flag += dfs(x-1, y, cnt+1)
        flag += dfs(x, y-1, cnt+1)
    
        if flag:
            graph[x][y] = 1
        return True
        
    return 0

N, M = map(int, input().split())
graph, result = [], []

for _ in range(N):
    graph.append(list(map(int, input())))

dfs(0, 0, 1)

print(min(result))

더 익숙한 dfs로 풀었는데,,, 런타임에러가 떴다.
입출력 예시가 잘 출력되서 그냥 넣었는데, 역시나 오류가 많았다.

내 생각에 문제는, 재귀 함수의 실행 순서를 잘 모른 채로 코드를 막 짰기 때문이다.

아무튼, 검색해보니 dfs는 최단 거리 문제엔 불리하다고 나와있어서 다음 코드는 bfs로 작성했다.

📌 Try 2

from collections import deque

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    
    while queue:
        # x, y, num 에 현재 데이터 저장
        x, y = queue.popleft()
        num = graph[x][y]
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 상 하 좌 우 노드 검사
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            
            # 1 이면, queue에 넣음
            # 현재 노드에 이전 노드 값을 더하기
            if graph[nx][ny] == 1:
                graph[nx][ny] += num
                queue.append((nx, ny))
        
    return graph[N-1][M-1]

N, M = map(int, input().split())
graph = []

for _ in range(N):
    graph.append(list(map(int, input())))

# 상 하 좌 우
dx = [-1, 1, 0 ,0]
dy = [0, 0, -1, 1]

print(bfs(0, 0))

이번엔 bfs로 작성했다.
여러 블로그와 영상을 참고해서 작성했지만, 그래도 나름 많이 고민했다.

상하좌우와 관련된 부분을 간결하게 짜기 위해 나동빈 유튜브를 참고했다. 근데 결국 코드는 거의 유사하다.

🎁 Reference

• [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)
  https://devuna.tistory.com/32 [튜나 개발일기📚]

• (이코테 2021 강의 몰아보기) 3. DFS & BFS
  https://www.youtube.com/watch?v=7C9RgOcvkvo