프로그래머스 (DFS/BFS)게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

이문제는 DFS로 풀면

프로그래머스 게임 맵 최단거리 문제의 핵심은:

**(0,0) → (n-1,m-1)**까지 갈 수 있는 최단 거리를 구하는 것이며,
최단 거리란 "가장 적은 칸을 지나는 경로"를 의미합니다.

---

✅ 지금 코드가 틀린 이유 (DFS는 비효율적)

너는 현재 DFS(깊이 우선 탐색)으로 문제를 풀고 있어요.
하지만 DFS는 모든 경로를 다 탐색하므로, 더 먼 거리의 경로도 탐색해버려서 최단 거리를 보장하지 않아요.
특히 maps[y][x] = maps[pos[1]][pos[0]] + 1로 거리를 누적할 때, 이미 방문한 곳이어도 더 긴 거리로 덮어쓰기 때문에 정답이 15처럼 더 크게 나올 수 있어요.

 

🎯 해결책: BFS로 풀어야 합니다

BFS는 먼저 가까운 노드부터 탐색하므로, 처음 (n-1, m-1)에 도달하는 순간이 최단 거리입니다.

🚨 정리

방식결과설명

DFS	❌ 15 (오답)	최단 거리 보장 X, 더 긴 거리도 탐색함
BFS	✅ 11 (정답)	최단 거리 보장, 효율적

BFS로 풀면

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    visited = [[0]*m for _ in range(n)]
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = 1  # 시작점 거리 1

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우

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

        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            # 맵 범위 안이고, 벽이 아니며, 아직 방문하지 않았다면
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and visited[nx][ny] == 0:
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx, ny))

    return visited[n-1][m-1] if visited[n-1][m-1] != 0 else -1

실행결과

메모이제이션을 사용한 BFS

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    visited = [[False] * m for _ in range(n)]  # 방문 여부를 기록하는 배열
    queue = deque([(0, 0)])  # 시작점 큐에 넣기
    visited[0][0] = True  # 시작점 방문 처리
    distance = [[0] * m for _ in range(n)]  # 거리 정보를 기록할 배열
    distance[0][0] = 1  # 시작점의 거리는 1 (자기 자신)

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우 방향

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

        # 네 방향으로 인접한 노드를 탐색
        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            # 맵의 범위 안에 있고, 벽이 아니며, 방문하지 않은 곳이라면
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True  # 방문 처리
                queue.append((nx, ny))  # 큐에 추가
                distance[nx][ny] = distance[x][y] + 1  # 거리 갱신

    # 목적지에 도달했다면 거리 반환, 아니면 -1 반환
    return distance[n-1][m-1] if distance[n-1][m-1] > 0 else -1

실행결과 수치상 큰 차이가 없음.

DFS로 풀어보면 pruning을 적용해서 중복구간의 최적화를 해야한다.

🔍 코드 설명

1. answer:
   • answer는 최단 거리를 추적하는 변수입니다. 처음에는 float('inf')로 매우 큰 값으로 초기화해두고, 경로를 탐색하면서 최단 거리를 갱신합니다.
2. dfs(x, y, dist):
   • x, y는 현재 위치를 나타내고, dist는 현재 위치까지의 거리입니다.
   • Pruning: dist가 이미 answer보다 크면 더 이상 그 경로를 탐색하지 않도록 합니다. 이를 통해 불필요한 경로를 차단할 수 있습니다.
3. 목적지 도달 시:
   • x == n-1 and y == m-1에 도달하면, 현재까지의 거리(dist)를 최단 거리(answer)와 비교하여 더 작은 값으로 갱신합니다.
4. 상하좌우 탐색:
   • 상하좌우 네 방향으로 이동하며, 벽이 아니고 맵의 범위 내에 있을 때만 이동합니다.
   • 방문한 곳은 다시 가지 않도록 maps[nx][ny] = 0으로 표시하고, 탐색이 끝나면 백트래킹을 통해 방문 표시를 초기화합니다.

def solution(maps):
    n, m = len(maps), len(maps[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우 방향
    answer = float('inf')  # 최단 거리를 추적할 변수, 매우 큰 값으로 초기화

    def dfs(x, y, dist):
        nonlocal answer

        # 목적지에 도달했으면 최단 거리 갱신
        if x == n - 1 and y == m - 1:
            answer = min(answer, dist)
            return

        # pruning: 현재 경로가 이미 최단 거리보다 크면 더 이상 탐색하지 않음
        if dist >= answer:  # 현재 거리보다 더 큰 경로는 더 이상 탐색하지 않음
            return

        # 상하좌우로 이동
        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            # 맵의 범위 안에 있고, 벽이 아니면 (maps[nx][ny] == 1)
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                maps[nx][ny] = 0  # 방문 표시
                dfs(nx, ny, dist + 1)
                maps[nx][ny] = 1  # 백트래킹: 방문 표시 초기화

    # 시작점에서 DFS 탐색
    maps[0][0] = 0  # 시작점 방문 처리
    dfs(0, 0, 1)  # 시작점에서 DFS 시작

    return answer if answer != float('inf') else -1  # 도달 불가 시 -1 반환

다음과 같이 순회한다.

dest:[4, 4]
xy:[0, 0] dist1 maps[0][0]=0
xy:[0, 1] dist2 maps[1][0]=0
xy:[0, 2] dist3 maps[2][0]=0
xy:[0, 3] dist4 maps[3][0]=0
xy:[1, 3] dist5 maps[3][1]=0
xy:[2, 3] dist6 maps[3][2]=0
xy:[2, 2] dist7 maps[2][2]=0
xy:[2, 1] dist8 maps[1][2]=0
xy:[2, 0] dist9 maps[0][2]=0
xy:[3, 0] dist10 maps[0][3]=0
xy:[4, 0] dist11 maps[0][4]=0
xy:[4, 1] dist12 maps[1][4]=0
xy:[4, 2] dist13 maps[2][4]=0
xy:[4, 3] dist14 maps[3][4]=0
answer15
xy:[3, 2] dist14 maps[2][3]=0
xy:[3, 2] dist8 maps[2][3]=0
xy:[4, 2] dist9 maps[2][4]=0
xy:[4, 1] dist10 maps[1][4]=0
xy:[4, 0] dist11 maps[0][4]=0
xy:[3, 0] dist12 maps[0][3]=0
xy:[2, 0] dist13 maps[0][2]=0
xy:[2, 1] dist14 maps[1][2]=0
xy:[4, 3] dist10 maps[3][4]=0
answer11
11

DFS +  pruning과 메모이제이션 까지 사용해야 한다. 하지만 이렇게 해도 효율화 에러 시간 초과가 났다.

def solution(maps):
    n, m = len(maps), len(maps[0])
    visited = [[-1] * m for _ in range(n)]  # -1은 방문 안 했음을 의미
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우 방향

    def dfs(x, y, dist):
        # 목적지에 도달했으면
        if x == n-1 and y == m-1:
            return dist
        
        # 만약 이미 방문한 곳이라면 더 이상 탐색하지 않음 (Pruning)
        if visited[x][y] != -1 and visited[x][y] <= dist:
            return float('inf')  # 더 이상 유효하지 않은 경로
        
        visited[x][y] = dist  # 현재 지점에 최단 거리 기록

        min_dist = float('inf')  # 최단 거리를 추적
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:  # 벽이 아니면
                min_dist = min(min_dist, dfs(nx, ny, dist + 1))  # 재귀적으로 DFS 탐색

        return min_dist

    result = dfs(0, 0, 1)  # 시작점 (0, 0)에서 거리 1부터 시작
    return result if result != float('inf') else -1  # 목적지에 도달할 수 없으면 -1 반환