백준 : 2665 미로 만들기

백준 : 2665 미로만들기

문제 분석

• 입력:
  • 첫 줄에 방의 수 N(1≤N≤50)이 주어진다.
  • 다음 N개의 줄에는 길이가 N인 수열이 주어지며, 각 수열은 '0'과 '1'로 이루어져 있다.
• 출력:
  • 시작점에서 도착점까지 이동하기 위해 부숴야 하는 검은 방의 최소 개수를 출력한다.

이 문제는 가중치가 0과 1로 이루어진 그래프에서 최단 경로를 찾는 문제로 볼 수 있다. 각 방을 노드로, 상하좌우 이동을 간선으로 간주하며, 흰 방('1')은 가중치 0, 검은 방('0')은 가중치 1로 설정할 수 있다. 이러한 특성 때문에 0-1 BFS 또는 다익스트라 알고리즘을 활용하여 해결할 수 있다.

최종 코드

0-1 BFS를 활용한 해결

import sys, math
from collections import deque
input = sys.stdin.readline

# 0-1 BFS를 이용한 최소 벽 부수기
def bfs(graph):
    # 각 위치까지의 최소 벽 부순 횟수를 저장하는 배열 (초기값: 무한대)
    dist = [[math.inf]*N for _ in range(N)]
    dist[0][0] = 0      # 시작점 (0, 0)은 벽을 부순 횟수 0으로 시작

    # 덱(Deque)을 이용한 BFS: 앞쪽엔 비용이 낮은 노드, 뒤쪽엔 비용 높은 노드
    pq = deque()
    pq.append((0, 0))   # 시작 위치 추가 (y, x)

    while pq:
        y, x = pq.popleft()     # 현재 위치 꺼냄
        # 상, 하, 좌, 우 네 방향 이동
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ny = y + dy
            nx = x + dx
            # 다음 위치가 미로 범위 내에 있다면
            if 0<= ny < N and 0 <= nx < N:
                # 다음 칸이 흰 방(1)이면 비용 0, 검은 방(0)이면 비용 1
                if graph[ny][nx] == 1:
                    cost = 0    # 흰 방: 벽을 부술 필요 없음
                else:
                    cost = 1    # 검은 방: 벽을 하나 부숴야 함
                # 지금까지 계산된 최소 비용보다 더 적은 비용으로 도달할 수 있다면 갱신
                if dist[ny][nx] > dist[y][x] + cost:
                    dist[ny][nx]  = dist[y][x] + cost
                    # 비용이 0이면 앞쪽에, 1이면 뒤쪽에 추가 (0-1 BFS 핵심)
                    if cost == 0 :
                        pq.appendleft((ny, nx))
                    else:
                        pq.append((ny, nx))
    # 목적지까지 도달했을 때 최소 벽 부순 횟수 반환
    return dist[N-1][N-1]

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

result = bfs(graph)
print(result)

 

다익스트라를 활용한 풀이

import sys, math, heapq
input = sys.stdin.readline

def dijkstra(graph):
    # 각 위치까지의 최소 벽 부순 횟수를 저장하는 2차원 배열
    dist = [[math.inf]*N for _ in range(N)]
    dist[0][0] = 0
    # 우선순위 큐: (현재까지의 비용, y좌표, x좌표)
    hpq = [(0, 0, 0)]
    while hpq :
        cost, y, x = heapq.heappop(hpq) # 최소 비용 노드를 꺼냄

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

            # 범위 안에 있을 때만 처리
            if 0 <= ny < N and 0 <= nx < N :
                # 흰 방이면 추가 비용 없음 (1), 검은 방이면 벽 부수기 필요 (0)
                if graph[ny][nx] == 1:
                    cost_check = 0
                else:
                    cost_check = 1
                # 지금까지의 거리 + 새로 가는 비용 = 새로운 경로 비용
                newcost = dist[y][x] + cost_check
                # 더 적은 비용으로 도달할 수 있으면 갱신
                if dist[ny][nx] > newcost:
                    dist[ny][nx] = newcost
                    heapq.heappush(hpq, (newcost, ny, nx))  # 비용 기준으로 힙에 넣음
    # 도착지까지의 최소 벽 부순 횟수 반환
    return dist[N-1][N-1]
N = int(input())
graph = [list(map(int, input().strip())) for _ in range(N)]

result = dijkstra(graph)
print(result)

 

cost, y, x = heapq.heappop(hpq) 이 코드에서 cost는 뒤 함수에서 호출되는 내용이 없는데 왜 필요한가?

우선순위 큐에서 정렬 기준으로 쓰기 위해 넣는다.

 

✅ 중요 포인트:

• heapq는 튜플의 첫 번째 값(cost) 을 기준으로 정렬한다
• 그래서 heappop()으로 꺼낼 때 비용이 가장 작은 노드가 자동으로 먼저 나온다
• 비록 이후 코드에서 cost를 직접 안 써도, 큐 정렬용으로 반드시 필요하다

newcost = dist[y][x] + cost_check 이부분을 간소화 하기 위해 newcost = cost + cost_check 으로 사용해도 무방하다.

0 - 1 BFS 알고리즘에 대한 이해

다익스트라보다 가볍고 빠르며 가중치가 0과 1만 있을 때 효과적인 최단 경로 탐색 방법이다. 우선순위 큐 대신 deque 를 사용하여 더 빠르고 간단하게 구현할 수 있다.

 

일반 BFS:

• deque.popleft() → 가장 먼저 넣은 위치 꺼냄
• deque.append() → 다음 노드 뒤에 추가

0-1 BFS:

• 가중치가 0인 경우 → 앞에 넣기 (appendleft)
• 가중치가 1인 경우 → 뒤에 넣기 (append)

→ 이러면 결국, 비용이 낮은 노드부터 먼저 방문하게 됨

→ 우선순위 큐(heapq)를 쓴 다익스트라보다 구현이 간단하고 속도도 빠름

다익스트라 vs. 0 - 1 BFS 의 비교

공통점

항목	설명
그래프 형태	2차원 격자 (N×N)
목적	(0, 0) → (N-1, N-1)까지의최소 벽 부수기 횟수(최소 비용)
가중치 의미	흰 방(1): 비용 0 / 검은 방(0): 비용 1
사용 알고리즘	최단 경로 알고리즘
거리 배열 사용	dist[y][x]로 최소 비용 저장
갱신 조건	if dist[next] > dist[now] + cost:

 

차이점

항목	0-1 BFS	다익스트라
사용 조건	간선 가중치가 0 또는 1만 있는 경우	간선 가중치가 양의 정수일 때 모두 가능
자료 구조	deque (덱)	heapq (우선순위 큐)
삽입 방식	비용이 0이면 앞에(appendleft), 1이면 뒤에(append)	모든 노드 heappush()로 넣고 자동 정렬
탐색 순서 제어	직접 삽입 위치로 제어	자동으로 비용 작은 순서대로 정렬
시간 복잡도	O(V + E)	O(E log V)
성능 (이 문제 기준)	더 빠름	충분히 빠름 (N ≤ 50이므로 문제 없음)
코드 복잡도	단순 (조건 분기만 있음)	구조적이지만 약간 복잡함
우선순위 제어	비용이 0인 경로 우선 처리	비용이 작은 경로 자동 처리
사용 가능 예시	벽 부수기, 최소 이동 횟수 등	일반적인 최소 거리 문제 (ex. 도로, 교통)
대표 문제 유형	미로, 벽, 0-1 그래프	도로망, 도시 간 거리, 그래프 전반 최단경로 문제

 

동작 흐름의 차이

• 다익스트라는 “가장 비용이 낮은 노드”를 우선순위 큐가 정렬해준다
• 0-1 BFS는 “비용이 0인 노드”를 덱 앞에, 비용이 1이면 덱 뒤에 넣는다

→ 방문 순서가 비슷하지만 내부 구현이 다르다

0-1 BFS vs 다익스트라 시간복잡도 (백준 기준)

이론상으로는 0-1 BFS가 더 빠르지만, 실제 백준 문제 풀이 기준으로는 아래 사진과 같이 다익스트라가 훨씬 빠른 성능을 보여주었다. 이는 파이썬 처럼 덱/리스트가 빠르지 않은 언어의 차이도 무시할 수 없지만, 다른 요소도 고려해볼 만 하다.

 

0-1 BFS : 76 ms / Dijkstra : 44 ms

 

다익스트라가 더 빠른 이유 (디테일 분석)

1. N 이 작다. 즉, 정점과 간선의 수가 작은 경우 log가 큰 의미가 없다

다익스트라의 복잡도는 O(E log V)인데, 만약 V가 2500 이하라면, log 2500 ≈ 12 은 사실상 상수 처럼 작다. 이런 경우 log의 이점보다는 큐 연산의 효율이 더 높다.

2. 파이썬에서는 deque보다 heapq의 구현이 더 빠르다

heapq는 C로 구현된 내장 모듈이나 collections.deque는 더블 링크드 리스트 기반으로 덱의 앞쪽 조작은 느리다.

3. deque.appendleft()는 상대적으로 비용이 크기 때문에 더 느리다

deque.append()는 뒤에 붙이는 작업으로 거의 O(1)에 가깝다.

하지만 appendleft()는

→ 내부적으로 포인터 이동

→ 파이썬 레벨에서 해줘야 해서 인터프리터 오버헤드 발생

→ if문에 따라 append와 appendleft 를 구분하므로 브랜치가 많아지고, CPU는 예측 실패 시 느려진다

4. heapq는 리스트 기반으로 캐시 최적화가 되어 메모리 접근이 더 빠르다

heapq는 단일 리스트에서 인덱스로 부모-자식 관계를 유지한다. 이는 메모리적으로 캐시 일관성이 매우 좋다.

deque는 노드 기반 구조에 가까우며, 더 많은 캐시 미스가 발생한다.

5. 0-1 BFS는 if cost == 0 : 이라는 추가적인 조건을 검사하는 비용이 있다.

다익스트라는 newcost 가 가장 작은 순서대로 자동 정렬되기 때문에, 0-1 BFS 처럼 어떤 비용을 먼저 처리해야 하는지에 대한 정의를 해주지 않아도 된다.