Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 은행 지도에서 경비원까지의 최단 거리 찾기 (다중 시작점 BFS)

문제 설명

은행 지도를 나타내는 행렬이 주어집니다. 각 셀은 다음 세 가지 문자 중 하나를 가집니다.

  • 'O': 빈 공간 (이동 가능)
  • 'G': 경비원 위치 (시작점)
  • 'W': 벽 (이동 불가)

모든 빈 공간('O')을 가장 가까운 경비원('G')까지의 최단 거리로 대체해야 합니다. 벽('W')은 통과할 수 없습니다. 결과 행렬에서 경비원은 0, 벽은 -1으로 표시합니다.

입력 및 출력 예시

입력 행렬 (5x5)

OOOOG
OOOWO
OWOOO
GWWWO
OOOOG

출력 행렬 (거리 값)

33210
233-11
1-1432
0-1-1-11
12210

해결 접근법: 다중 시작점 BFS (Multi-source BFS)

이 문제는 여러 시작점(모든 경비원)에서 동시에 BFS를 탐색하는 전형적인 다중 시작점 BFS 문제입니다. 각 경비원을 큐에 초기에 모두 넣고(거리 0), 동시 탐색을 수행하면 각 빈 공간에는 자연스럽게 가장 가까운 경비원까지의 최단 거리가 기록됩니다.

알고리즘 단계

  1. 초기화: 결과 행렬 result를 -1로 채웁니다. (미방문 및 벽 표시 겸용)
  2. 시작점 큐 삽입: 행렬을 순회하며 경비원('G')을 찾으면 result를 0으로 설정하고, 위치 (행, 열, 거리=0)을 덱(deque)의 왼쪽에 추가합니다.
  3. BFS 탐색: 큐가 빌 때까지 반복합니다.
    • 큐의 오른쪽에서 현재 위치 (x, y, dist)를 꺼냅니다. (pop())
    • 상하좌우 4방향으로 이동할 다음 좌표 (nx, ny)를 계산합니다.
    • 유효성 검사: 맵 범위 내인지(is_ok), 빈 공간('O')이면서 아직 방문하지 않았는지(result == -1) 확인합니다. (isSafe)
    • 조건 만족 시 result[nx][ny] = dist + 1로 갱신하고, (nx, ny, dist+1)을 큐 왼쪽에 추가합니다. (appendleft)
  4. 결과 출력: 완성된 result 행렬을 출력합니다.

파이썬 구현

from collections import deque

# 방향 벡터: 상, 우, 하, 좌
DIR_ROW = [-1, 0, 1, 0]
DIR_COL = [0, 1, 0, -1]

def is_ok(i, j, m, n):
    """좌표 (i, j)가 맵 범위 내에 있는지 확인"""
    return 0 <= i < m and 0 <= j < n

def is_safe(i, j, matrix, result):
    """이동 가능 여부 확인: 빈 공간('O')이면서 미방문(-1) 상태인가?"""
    return matrix[i][j] == 'O' and result[i][j] == -1

def calculate_dist(matrix):
    m = len(matrix)
    n = len(matrix[0]) if m > 0 else 0
    
    # 결과 행렬 -1로 초기화 (벽도 -1, 미방문도 -1)
    result = [[-1] * n for _ in range(m)]
    q = deque()

    # 1. 모든 경비원(G)을 시작점으로 큐에 삽입 (거리 0)
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 'G':
                result[i][j] = 0
                q.appendleft((i, j, 0))  # (행, 열, 거리)

    # 2. BFS 수행
    while q:
        x, y, dist = q.pop()  # 오른쪽에서 꺼냄 (FIFO 효과를 위해 appendleft/pop 조합 사용)
        
        for k in range(4):
            nx, ny = x + DIR_ROW[k], y + DIR_COL[k]
            
            if is_ok(nx, ny, m, n) and is_safe(nx, ny, matrix, result):
                result[nx][ny] = dist + 1
                q.appendleft((nx, ny, dist + 1))

    return result

# 실행 예시
if __name__ == "__main__":
    bank_map = [
        ['O', 'O', 'O', 'O', 'G'],
        ['O', 'O', 'O', 'W', 'O'],
        ['O', 'W', 'O', 'O', 'O'],
        ['G', 'W', 'W', 'W', 'O'],
        ['O', 'O', 'O', 'O', 'G']
    ]

    distances = calculate_dist(bank_map)
    
    for row in distances:
        print(' '.join(map(str, row)))

코드 핵심 포인트

  • Deque 활용: appendleft와 pop을 조합해 큐(FIFO)처럼 사용합니다. 파이썬 deque는 양쪽 끝에서 O(1)에 삽입/삭제가 가능해 BFS에 최적입니다.
  • 방문 배열 겸용: 별도의 visited 배열 대신 result 행렬의 값이 -1인지 확인하여 방문 여부를 판별합니다. 벽('W')도 애초에 -1로 남아있으므로 자연스럽게 처리됩니다.
  • 다중 시작점: 모든 경비원을 처음부터 큐에 넣음으로써, 가장 먼저 도달하는 경비원의 거리가 최단 거리가 되도록 보장합니다.

시간 및 공간 복잡도

  • 시간 복잡도: O(M × N) — 각 셀을 최대 한 번 방문합니다. (M: 행 수, N: 열 수)
  • 공간 복잡도: O(M × N) — 결과 행렬과 큐(최악의 경우 모든 셀 저장)에 비례합니다.

마무리

이 문제는 그리디나 다익스트라가 아닌 BFS의 특성(레벨 순회 = 최단 거리 보장)과 다중 시작점 기법을 결합해 효율적으로 해결하는 전형적인 알고리즘 문제입니다. 미로 찾기, 로봇 청소기, 네트워크 전파 시간 계산 등 다양한 변형 문제에 응용 가능합니다.