백준 2665번 미로만들기 Python

백준 2665번 미로만들기 Python

문제

n×n 크기의 바둑판 형태의 미로가 주어집니다.

각 칸은 흰 방(1) 또는 검은 방(0) 으로 이루어져 있습니다.

흰 방은 자유롭게 이동할 수 있지만, 검은 방은 벽으로 막혀 있어서 이동할 수 없습니다.

시작점은 항상 왼쪽 위(0,0) 흰 방이고, 도착점은 오른쪽 아래(n-1,n-1) 흰 방입니다.

목표는 시작점에서 도착점까지 이동할 수 있도록 최소한의 검은 방을 흰 방으로 바꾸는 것입니다.

처음부터 이동이 가능한 경우에는 0이 정답이 됩니다.

테스트케이스

입력 예시

8
11100110
11010010
10011010
11101100
01000111
00110001
11011000
11000111

출력 예시

2

이 예시에서는 검은 방 두 개를 흰 방으로 바꾸면 도착점까지 도달할 수 있습니다.
단 하나의 검은 방만 바꾸어서는 연결되는 경로가 만들어지지 않습니다.

문제 작동원리

이 문제에서 주어진 미로는 여러 개의 0과 1로 이루어져 있습니다.

0은 벽, 즉 막힌 길이고 1은 통로, 즉 이동 가능한 공간을 의미합니다.

시작점에서 도착점까지 가려면 상하좌우로 인접한 1을 따라가야 하지만, 중간에 0이 가로막고 있습니다.

이때, 검은 방(0)을 흰 방(1)으로 바꾸면 벽이 사라지고 길이 생기게 됩니다.

이동 불가능한 원래 상태

입력 예시에서 원래 주어진 미로는 다음과 같습니다 (1은 흰 방, 0은 검은 방).

11100110  
11010010  
10011010  
11101100  
01000111  
00110001  
11011000  
11000111  

이 상태에서는 아무리 상하좌우로 이동해도 시작점에서 도착점까지 완전하게 연결되는 경로가 존재하지 않습니다.
예를 들어, 시작점(1,1) 근처에서는 일부 구역으로 갈 수 있지만, 중간에 연결이 완전히 끊기는 부분이 있습니다.

검은 방을 2개 바꾸면 생기는 변화

예를 들어, 다음 두 위치의 검은 방을 흰 방으로 바꾸었다고 가정하겠습니다.

• (4,4) → 원래 검은 방(0) → 흰 방(1)로 변경
• (7,8) → 원래 검은 방(0) → 흰 방(1)로 변경

이렇게 되면 이전에 끊어져 있던 통로가 이어집니다.
즉, 중간의 단절된 구간이 새로 뚫리면서 출발점에서 도착점까지 연결된 하나의 길이 형성됩니다.

바꾼 후의 일부 미로를 단순히 표현하면 다음과 같습니다.

11100110  
11010010  
10011010  
11111100 ← (4,4) 위치가 열림  
01000111  
00110001  
11011000  
11000111 ← (7,8) 위치가 열림  

이제 출발점(0,0)에서 오른쪽, 아래쪽, 다시 오른쪽으로 여러 방향으로 이동하면서
도착점(7,7)까지 도달할 수 있는 통로가 완성됩니다.

이때 2개의 검은 방을 바꾸면 가능하지만,
1개의 검은 방만 바꿨을 경우에는 여전히 중간에 막힌 구간이 존재하여 끝까지 연결되지 않습니다.
즉, 이 문제의 정답은 “2”,
즉, 두 개의 검은 방을 흰 방으로 바꾸면 처음과 끝이 연결되는 최소 경우라는 의미입니다.

따라서 문제의 작동 원리는
“경로를 완성하기 위해 필요한 최소한의 벽(0)을 허물어 흰 방(1)을 만드는 과정을 통해,
처음에서 끝까지 연결되는 통로를 확보하는 원리”입니다.

---

아이디어

이 문제의 핵심 아이디어는 "0-1 BFS" 개념을 이용하는 것입니다.

즉, 흰 방(1) 은 이동할 때 비용이 없고, 검은 방(0) 은 벽을 부수는 데 비용 1이 듭니다.

이를 위해 덱(deque) 을 사용하면, 비용이 0인 이동은 덱의 앞쪽, 비용이 1인 이동은 덱의 뒤쪽에 삽입함으로써,
자연스럽게 최소 벽 부수기 횟수가 보장되는 형태로 탐색이 진행됩니다.

이 논리 덕분에 따로 다익스트라 알고리즘처럼 우선순위 큐를 사용할 필요가 없습니다.
덱은 FIFO 구조를 유지하면서, 0-1 가중치 조건에서는 항상 최소 비용 순으로 탐색을 보장합니다.

즉,

• 흰 방을 만날 때는 현재 경로의 비용을 유지한 채 가장 앞쪽에 삽입하여 즉시 탐색합니다.
• 검은 방을 만날 때는 비용을 1 증가시키고 뒤쪽에 넣어서 나중에 처리합니다.

이렇게 하면, 탐색 도중 도착점에 도달했을 때 이미 그 경로가 최소의 벽 부수기 횟수로 도달한 경우가 됩니다.

덱 논리의 흐름

1. 처음에 (0,0)에서 출발하며, 현재까지 바꾼 벽의 수 z=0으로 시작합니다.
2. 인접한 흰 방(1)은 appendleft()로 덱의 앞부분에 넣습니다.
   → 이는 "비용 0"의 이동이며, 가장 먼저 탐색해야 합니다.
3. 인접한 검은 방(0)은 append()로 덱의 뒷부분에 넣습니다.
   → 이는 "비용 1"의 이동으로, 비용이 드는 이동이므로 나중에 탐색됩니다.
4. 덱에서 하나씩 꺼내며 이 과정을 반복하면, 가장 먼저 도착하는 순간의 비용이 최소값이 됩니다.

이 과정을 통해, 최소한의 벽을 부수고 도착점에 이르는 경로가 자동으로 탐색됩니다.

1) 벽 0개로 지금 닿는 곳(0)만 표시 (벽=■, 미도달=·)

r\c	0	1	2	3	4	5	6	7
0	0	0	0	■	■	·	·	■
1	0	0	■	·	■	■	·	■
2	0	■	■	·	·	■	·	■
3	0	0	0	■	·	·	■	■
4	■	0	■	■	■	·	·	·
5	■	■	·	·	■	■	■	·
6	·	·	■	·	·	■	■	■
7	·	·	■	■	■	·	·	·

2) 1단계에 인접한 벽만 ①로 추가 (누적: 0 그대로 유지)

r\c	0	1	2	3	4	5	6	7
0	0	0	0	①	■	·	·	■
1	0	0	①	·	■	■	·	■
2	0	①	①	·	·	■	·	■
3	0	0	0	①	·	·	■	■
4	①	0	①	■	■	·	·	·
5	■	①	·	·	■	■	■	·
6	·	·	■	·	·	■	■	■
7	·	·	■	■	■	·	·	·

3) 벽 1개 허용 시 닿는 흰칸만 1로 추가 (누적: 0/① 그대로 유지)

r\c	0	1	2	3	4	5	6	7
0	0	0	0	①	■	·	·	■
1	0	0	①	1	■	■	·	■
2	0	①	①	1	1	■	·	■
3	0	0	0	①	1	1	■	■
4	①	0	①	■	■	1	1	1
5	■	①	1	1	■	■	■	1
6	·	·	■	1	1	■	■	■
7	·	·	■	■	■	·	·	·

4) 3단계의 1에 인접한 벽만 ②로 추가 (누적: 0/①/1 그대로 유지)

r\c	0	1	2	3	4	5	6	7
0	0	0	0	②	■	·	·	■
1	0	0	②	1	②	■	·	■
2	0	①	②	1	1	②	·	■
3	0	0	0	②	1	1	②	②
4	■	0	②	②	②	1	1	1
5	②	②	1	1	②	②	②	1
6	·	·	■	1	1	②	■	②
7	·	·	■	②	②	·	·	·

5) 마지막 부분들만 2로 추가 (누적: 0/①/1/②는 그대로 유지하고, 끝 구간만 2로 채움)

r\c	0	1	2	3	4	5	6	7
0	0	0	0	②	■	·	·	■
1	0	0	②	1	②	■	·	■
2	0	①	②	1	1	②	·	■
3	0	0	0	②	1	1	②	②
4	■	0	②	②	②	1	1	1
5	②	②	1	1	②	②	②	1
6	·	·	■	1	1	②	■	2
7	·	·	■	②	②	2	2	2

---

전체코드

from collections import deque
N=int(input())
arr=[]
check=[[0 for _ in range(N)] for _ in range(N)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
for _ in range(N):
    k=input()
    arr2=[]
    for i in k:
        arr2.append(int(i))
    arr.append(arr2)

dq=deque()
dq.append([0,0,0])
cnt=0
while dq:
    x,y,z=dq.popleft()
    if x==N-1 and y==N-1:
        print(z)
        break

    for a,b in zip(dx,dy):
        x_a=a+x
        y_a=b+y

        if 0<=x_a

결론

• 덱을 활용해 흰 방은 앞으로, 검은 방은 뒤로 넣음으로써 최소 비용이 자동으로 계산됩니다.
• 검은 방을 흰 방으로 바꾸는 횟수를 비용으로 설정하여 0-1 BFS 형태로 탐색이 진행됩니다.
• 출발점에서 도착점까지 도달할 때의 첫 번째 출력값이 최소 벽 변환 수가 됩니다.
• 이 방법은 다익스트라 알고리즘보다 간단하고 빠르며, 0과 1의 두 가지 비용만 있을 때 최적입니다.