백준 / 미로 탐색 / 2178번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 미로 탐색 / 2178번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/2178

 

문제 설명

 

---

 

나의 풀이

 

def dfs(graph, visited, count, start, target):
    n, m = start
    a, b = target
    visited[n][m] = True

    if n == (a - 1) and m == (b - 1):
        return count

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    for dn, dm in directions:
        new_n, new_m = n + dn, m + dm
        if 0 <= new_n < len(graph) and 0 <= new_m < len(graph[0]) and graph[new_n][new_m] == '1' and not visited[new_n][new_m]:
            result = dfs(graph, visited, count + 1, [new_n, new_m], target)
            if result is not None:
                return result

    visited[n][m] = False
    return None

N, M = map(int, input().split())
visited = [[False] * M for _ in range(N)]
maze = []

for _ in range(N):
    line = list(input())
    maze.append(line)

result = dfs(maze, visited, 0, [0, 0], [N, M])
if result is not None:
    print(result + 1)
else:
    print(-1)  # 경로를 찾을 수 없는 경우

DFS로 푸니깐 시간 초과가 발생했다. 경로를 찾지 못하는 경우가 있어서 그렇다.

from collections import deque

def bfs(graph, start, target):
    n, m = len(graph), len(graph[0])
    visited = [[False] * m for _ in range(n)]
    queue = deque([(start[0], start[1], 0)])  # (x, y, count)
    visited[start[0]][start[1]] = True

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

        if x == target[0] and y == target[1]:
            return count

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and graph[nx][ny] == '1':
                visited[nx][ny] = True
                queue.append((nx, ny, count + 1))

    return -1

N, M = map(int, input().split())
maze = [list(input().strip()) for _ in range(N)]

start = (0, 0)
target = (N - 1, M - 1)

result = bfs(maze, start, target)
print(result + 1 if result != -1 else -1)

BFS로 푸니깐 정답이 나왔다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/81

깊이 우선 탐색(DFS, Depth-First Search)

https://newkimjiwon.tistory.com/77

너비 우선 탐색(BFS, Breadth-First Search)