BFS 구현 방법 2가지 정리(visted, time)

 

✅ 1. visited 배열을 사용하는 방법

단순히 특정 노드를 방문했는지 여부만 기록하는 방식

📌 예제 코드 (일반 BFS)

from collections import deque

def bfs(start_x, start_y):
    queue = deque([(start_x, start_y)])
    visited = [[False] * M for _ in range(N)]  # 방문 여부 체크
    visited[start_x][start_y] = True  # 시작 위치 방문 표시

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

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy

            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:  # 방문 안 했으면 이동
                visited[nx][ny] = True
                queue.append((nx, ny))

📌 특징

• O(V + E)의 시간 복잡도를 가짐. (BFS의 기본 성질)
• 방문한 곳을 visited[x][y] = True로 표시.
• "목적지에 도달할 수 있는지"만 확인하는 데 적합.

 

✅ 2. time 배열을 사용하는 방법

각 위치까지 도달하는 "최소 시간(거리)"을 기록하는 방식

📌 예제 코드 (최소 거리 BFS)

from collections import deque

def bfs(start_x, start_y):
    queue = deque([(start_x, start_y)])
    time = [[float('inf')] * M for _ in range(N)]  # 무한대로 초기화
    time[start_x][start_y] = 0  # 시작 위치의 시간(거리) 0

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

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + dx, y + dy
            
            
	#gird 안에 있고, 현재위치의 시간+1이 이동할 위치 시간보다 작아야 이동
            if 0 <= nx < N and 0 <= ny < M and time[nx][ny] > time[x][y] + 1:
                time[nx][ny] = time[x][y] + 1  # 최소 거리 업데이트
                queue.append((nx, ny))

📌 특징

• time[x][y]에 해당 위치까지 도달하는 최소 시간(또는 최소 거리)을 기록.
• 최단 거리 문제에 적합 (예: 미로 탈출, 불 번지는 시간 계산, 유령보다 빠르게 탈출 등)
• 방문 여부뿐만 아니라 이전보다 더 빠른 경로가 있는지 확인함.
• visited 없이도 동작 가능 (time[x][y]가 갱신될 때만 방문했다고 판단 가능)

 

✅ 차이점 정리

	visited 사용	time 사용
목적	방문 여부 체크	최소 거리(시간) 체크
메모리 사용량	O(N×M)	O(N×M)
적용 예시	단순 탐색 (미로 탈출 가능 여부)	최단 거리, 최소 시간 문제
방문 여부 확인 방식	visited[x][y] = True	time[x][y] 값 비교 (time[x][y] > time[prev] + 1)