[BAEKJOON] 2178. 미로 탐색

 

---

[백준 2178번: 미로 탐색 문제]
👉 https://www.acmicpc.net/problem/2178

 

오랜만에 다시 푸는 백준 문제. 연구실 일도 아직 다 못했지만, 서울 다녀와서 다시 시작하자는 새로운 마음으로 풀기 시작.

이번 문제는 미로 탈출 문제이다. DFS, BFS의 대표적인 유형이지...

# DFS 풀이

N, M = map(int, input().split())    # N: 줄 개수, M: 정수 개수
maze = [list(map(int, input().strip())) for _ in range(N)]
# 0: 이동 불가, 1: 이동 가능
# 목적지: (N-1, M-1)

answer = float('inf')
visited = [[False] * M for _ in range(N)]
visited[0][0] = True

def dfs(x, y, count):
    global answer
    
    if count >= answer:
        return
    
    if x == N-1 and y == M-1:
        answer = min(answer, count)
        return
    
    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < N and 0 <= ny < M:
            if not visited[nx][ny] and maze[nx][ny] == 1:
                visited[nx][ny] = True
                dfs(nx, ny, count+1)
                visited[nx][ny] = False

dfs(0, 0, 1)
print(answer)

로직이 좀 이상하고 복잡하지만 일단 설명을 시작하자면...

1. maze랑 똑같은 배열을 만들어주는데, 다 False로 채워놓고 방문을 하게 되면 True로 바뀌도록 했다.
2. 시작 지점이 (0, 0)이니까 미리 방문 처리를 해놓는다.
3. DFS 내부에서, 일단 count가 answer보다 크면 그냥 바로 가지치기. 최솟값을 구하는 거니까, 더 큰 값은 볼 필요가 없다.
4. 그리고 목적지에 도착했을 때, answer와 count 중 더 작은 수를 answer에 대입해서 반환시킨다.
5. 그리고 이제 움직이는 로직을 구현했다. 움직이는 건 4방향이 가능하므로 그것에 대해 계속 반복하도록 해줬다. 그리고 nx와 ny가 maze 배열의 인덱스 범위를 벗어나지 않아야 하는 게 첫 번째 조건.
6. 두 번째 조건은 방문한 적이 없어야 하고, 이동이 가능한 칸(=1)이어야 한다. 그럴 때에만 True 처리해주고 다음 칸에 대해 이동 현황을 구하면 된다.

 

물론 저렇게 구현하다가 한두 개 놓친 부분도 있었다.

• nx와 ny의 범위를 제한할 때, 0을 깜빡하고 포함하지 않았었다.
• x와 y가 각각 N-1, M-1일 때 최솟값을 구해주고 반환해야 하는데 그냥 바로 반환을 해버렸다. 디버깅 한다고 미처 신경을 쓰지 못했던 부분...
• dfs(0, 0, 1)을 처음에 dfs(0, 0, 0)으로 작성했다. 시작점부터 카운팅해야 하는 걸 간과했었다.

 

오랜만에 다시 문제 푸는데, 물론 쉬운 문제지만 내 힘으로 다 풀 수 있다는 게 좀 뿌듯하긴 하다. 전에 비해 그래도 성장했구나.. 하는 생각이 들기도 하고?

 

....로 끝나면 좋으련만, 막상 제출하니 시간 초과가 뜬다. 이게 무슨 일이고...  혹시나 싶어서 DFS 로직을 BFS로 싹 바꿨더니 잘 된다... 그래도 DFS로 작성한 걸 BFS로 바꾸는 건 생각보다 어렵진 않아서 다행이다. 물론 더 복잡한 문제가 나오게 되면 어려워지겠지만... 최솟값 구하는 건 BFS인 걸 또 까먹고 DFS로 풀어서 생긴 문제였다.

# BFS 풀이

from collections import deque

N, M = map(int, input().split())    # N: 줄 개수, M: 정수 개수
maze = [list(map(int, input().strip())) for _ in range(N)]
# 0: 이동 불가, 1: 이동 가능
# 목적지: (N-1, M-1)
visited = [[False] * M for _ in range(N)]

def bfs():
    queue = deque()
    queue.append((0, 0, 1))
    visited[0][0] = True

    while queue:
        x, y, count = queue.popleft()

        if x == N-1 and y == M-1:
            return count

        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < M:
                if not visited[nx][ny] and maze[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append((nx, ny, count+1))

answer = bfs()
print(answer)