문제 출처 : https://www.acmicpc.net/problem/2206
난이도 : 골드 3
문제 파악
N×M 격자에서 (1,1) → (N,M)까지 최단 거리로 이동해야 한다.
0: 이동 가능1: 벽(이동 불가)- 단, 벽을 딱 1번 부수고 이동할 수 있음
- 도착 불가능하면
-1
이 문제에서 “최단 거리”라는 키워드는 거의 항상 BFS를 떠올리면 된다.
근데 여기서는 “벽을 부쉈는지 여부” 때문에 단순 BFS로는 상태가 부족하다.
핵심 아이디어
상태를 2개로 나눠서 BFS 한다
벽을 부술 수 있는 기회는 딱 1번이라서, 이동하는 동안 상태가 두 가지로 나뉜다.
special = 1: 아직 벽을 안 부숨 (→ 앞으로 부술 수 있음)special = 0: 이미 벽을 부숨 (→ 앞으로 못 부숨)
즉, 같은 좌표 (y,x)라도
(y,x, special=1)로 도착한 경우(y,x, special=0)로 도착한 경우
이 둘은 완전히 다른 상태다.
그래서 visited도 2겹으로 관리해야 한다.
visited[y][x][1]: 아직 안 부순 상태로 도착했을 때의 최단 거리visited[y][x][0]: 이미 부순 상태로 도착했을 때의 최단 거리
그리고 visited의 값은 “가능/불가능”이 아니라 거리다.
- 0이면: 아직 그 상태로 방문한 적 없음
- 1,2,3...이면: 그 상태로 도착한 최단거리
BFS 진행 방식
큐에는 (y, x, special)을 넣는다.
이웃 칸을 볼 때 경우는 두 가지다.
1) 다음 칸이 빈칸(0)이라면
- 그냥 이동 가능
- 상태
special은 그대로 유지
조건:
visited[ny][nx][special] == 0(그 상태로 아직 방문 안 했을 때만)
2) 다음 칸이 벽(1)이라면
special == 1일 때만 “부수고 이동” 가능- 이동하면
special이 0이 된다 (필살기 소모)
조건:
special == 1- 그리고 “부순 상태(special=0)”로 그 칸에 아직 도착한 적 없어야 함
해답 및 풀이
import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int,input().split())
graph = []
for _ in range(N):
graph.append(list(map(int,input().rstrip())))
# 0은 이동할 수 있는 곳
# 1은 이동할 수 없는 벽이 있는 곳
# (1,1) 에서 (N,M) 로 이동하려 할때 최단경로 구하기
# 이동 불가능할때는 -1 출력
# 벽 부수기 한번 딱 가능
# ---
# 벽 부수기가 없다면 단순 최단경로 BFS 문제
# 벽 부수기를 어떻게 처리할 지 ?
# + 시작하는 칸부터 count + 1 해주어야 함 (문제 조건)
# 일단 상하좌우 이동 -> 방향벡터
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 벽부수기 처리를 special = True of False 로 해서 분기 처리?
# visited 배열에 차원을 하나 더 추가해서 0 or 1로 처리
visited = [
[[0, 0] for _ in range(M)] for _ in range(N) # [방문 여부 and 거리, 필살기 여부]
]
queue = deque()
queue.append((0,0,1)) # (y,x,special)
visited[0][0][1] = 1 # 시작 칸도 count + 1
while queue:
y, x, special = queue.popleft()
if y == N -1 and x == M -1:
print(visited[y][x][special])
sys.exit(0)
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if not (0 <= ny < N and 0 <= nx < M):
continue
# 인접 칸이 벽이 아니라면
if graph[ny][nx] == 0 and visited[ny][nx][special] == 0:
visited[ny][nx][special] = visited[y][x][special] + 1
queue.append((ny,nx,special))
# 벽이고, 그 벽에 방문하지 않았다면, 필살기 있을 때만 부수고 이동
elif graph[ny][nx] == 1 and special == 1 and visited[ny][nx][0] == 0:
visited[ny][nx][0] = visited[y][x][special] + 1
queue.append((ny,nx,0))
print(-1) # while 문 돌고 sys.exit 안되었다면 -1 출력다음날 다시 풀고 틀린 코드
import sys
input = sys.stdin.readline
from collections import deque
dx = [-1,1,0,0]
dy = [0,0,-1,1]
N, M = map(int,input().split())
graph = []
for _ in range(N):
graph.append(list(map(int,input().rstrip())))
visited = [
[[0,0]] * M for _ in range(N)
] # [ 경로 횟수, 필살기 유무 ]
# [
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ]
# ]
queue = deque()
queue.append((0,0,1)) # x좌표, y좌표, 필살기 유무
while queue:
x, y, power = queue.popleft()
if x == N-1 and y == M-1:
print(visited[N-1][M-1][0])
sys.exit(0)
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
# 범위 내 존재하고 뚫린 도로라면, 이전 경로횟수 + 1
if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0:
visited[nx][ny][0] = visited[x][y] + 1
queue.append((nx,ny,power))
# 범위 내 존재하는데 벽이라면, 그리고 방문한 적이 없는 벽이라면, 그리고 필살기가 있다면, 필살기 소진하면서, 이전 경로횟수 + 1
if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 1 and visited[nx][ny][1] == 1:
visited[nx][ny][0] = visited[x][y] + 1
queue.append((nx,ny,0))
print(-1)옳은 코드
import sys
input = sys.stdin.readline
from collections import deque
dx = [-1,1,0,0]
dy = [0,0,-1,1]
N, M = map(int,input().split())
graph = []
for _ in range(N):
graph.append(list(map(int,input().rstrip())))
# visited = [
# [[0,0]] * M for _ in range(N)
# ]
# 이렇게 하면 틀린다. 얕은 복사가 되어 값을 하나 고치면 전부 바뀜
visited = [
[ [0,0] for _ in range(M)] for _ in range(N)
] # 맞는 배열 선언
# [
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ],
# [ [0, 0], [0, 0], [0, 0], [0, 0] ]
# ]
queue = deque()
queue.append((0,0,1)) # x좌표, y좌표, 필살기 유무
visited[0][0][1] = 1 # 시작 칸도 count + 1 해주어야 한다.
while queue:
x, y, power = queue.popleft()
if x == N-1 and y == M-1:
print(visited[N-1][M-1][power])
sys.exit(0)
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if not (0 <= nx < N and 0 <= ny < M):
continue # 범위 확인 로직을 한번에 빼서 코드 간편화
# 이러면 벽 유무만 판단하면 됨
if graph[nx][ny] == 0 and visited[nx][ny][power] == 0:
visited[nx][ny][power] = visited[x][y][power] + 1
queue.append((nx,ny,power))
# 벽이고, 방문하지 않았다면, 필살기 있을 때만 부수고 이동
elif graph[nx][ny] == 1 and power == 1 and visited[nx][ny][power] == 0:
visited[nx][ny][0] = visited[x][y][power] + 1
queue.append((nx,ny,0))
print(-1)아직 100% 감이 잡히진 않았다.
그 다음날 다시 푼 코드
import sys
input = sys.stdin.readline
from collections import deque
dx = [-1,1,0,0]
dy = [0,0,-1,1]
N, M = map(int,input().split())
graph = []
for _ in range(N):
graph.append(list(map(int,input().rstrip())))
# [[0, 1, 0, 0],
# [1, 1, 1, 0],
# [1, 0, 0, 0],
# [0, 0, 0, 0],
# [0, 1, 1, 1],
# [0, 0, 0, 0]]
visited = [
[[0, 0] for _ in range(M)] for _ in range(N)
] # 방문 횟수, 필살기 여부
# [
# [[0, 0], [0, 0], [0, 0], [0, 0]],
# [[0, 0], [0, 0], [0, 0], [0, 0]],
# [[0, 0], [0, 0], [0, 0], [0, 0]],
# [[0, 0], [0, 0], [0, 0], [0, 0]],
# [[0, 0], [0, 0], [0, 0], [0, 0]],
# [[0, 0], [0, 0], [0, 0], [0, 0]]
# ]
queue = deque()
queue.append((0,0,1))
visited[0][0][0] = 1 # 시작도 count
while queue:
y, x, power = queue.popleft()
# 리턴 조건
if y == N-1 and x == M-1:
print(visited[y][x][0])
sys.exit(0)
# 4방향 탐색
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
# 범위 확인
if not (0 <= ny < N and 0 <= nx < M):
continue
# 가고자 하는 곳이 벽이 아니고, 방문한적이 없다면
if graph[ny][nx] == 0 and visited[ny][nx][0] == 0:
# 거리 1 추가
visited[ny][nx][0] = visited[y][x][0] + 1
# 큐에 넣기
queue.append((ny,nx,power))
# 가고자 하는 곳이 벽이고, 방문한 적이 없다면, 그리고 power가 있다면
elif graph[ny][nx] == 1 and visited[ny][nx][0] == 0 and power == 1:
# 거리 1 추가
visited[ny][nx][0] = visited[y][x][0] + 1
# 큐에 넣기 , 단 power는 0으로
queue.append((ny,nx,0))
# while문을 돌았음에도 exit 하지 않았다면 -1 출력
print(-1)이렇게 코드를 구현하고 예제를 돌려 답이 맞는 것을 확인하고 제출했다.
그런데 틀렸다고 나왔다.
이유는 어떤 칸을 power=0 상태로 먼저 방문해도 visited[ny][nx][0] != 0이 되어버리니까
나중에 그 칸을 power=1 상태(벽을 아직 안 부순 더 좋은 상태)로 다시 방문하려는 경로를 막아버린다.
그래서 당장은 빠른것같아도 power를 가지고 좀 돌아가는 로직을 고려하지 않기에 오류가 존재할 수 있어서 그렇다.
애초에 내가 이 문제에 풀이에 대해 잘못 이해하고 있었다.
내가 잘못 이해한 부분
여지껏 visited 배열을 visited[y][x] = [횟수, 필살기 여부] 라고 생각하고 코드를 구현했다.
즉 [0, 0]에서 앞의 0은 “이 칸까지 온 거리”, 뒤의 0/1은 “필살기(벽 부수기) 여부”라고 착각했다.
근데 이렇게 접근하면 위와 같은 오류를 범한다.
그래서 방문 처리는
visited[y][x][0]: 벽을 이미 부순 상태(power=0) 로 (y,x)에 도착한 최단 거리visited[y][x][1]: 벽을 아직 안 부순 상태(power=1) 로 (y,x)에 도착한 최단 거리
결론적으로 [0,0]은 (거리, 여부)가 아니라
(벽 부순 상태에서의 거리, 벽 안 부순 상태에서의 거리) 였다.
다시 이해하고 주석을 포함한 코드
import sys
input = sys.stdin.readline
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N, M = map(int, input().split())
graph = []
for _ in range(N):
graph.append(list(map(int, input().rstrip())))
# visited[y][x][0] : 벽을 이미 부순 상태(power=0)로 도착한 최단 거리
# visited[y][x][1] : 벽을 아직 안 부순 상태(power=1)로 도착한 최단 거리
# 값이 0이면 "해당 상태로는 아직 방문 X"
visited = [[[0, 0] for _ in range(M)] for _ in range(N)]
queue = deque()
# 시작점은 벽을 아직 안 부순 상태(power=1)로 시작
queue.append((0, 0, 1))
visited[0][0][1] = 1 # 문제 조건상 시작 칸도 거리 1로 카운트
while queue:
y, x, power = queue.popleft()
# 도착하면 그 "상태(power)"에서의 최단 거리 출력
if y == N - 1 and x == M - 1:
print(visited[y][x][power])
sys.exit(0)
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
# 범위 밖이면 스킵
if not (0 <= ny < N and 0 <= nx < M):
continue
# 1) 다음 칸이 빈 칸(0)인 경우: power 상태 그대로 이동 가능
# 같은 칸이라도 power가 다르면 "다른 상태"이므로 visited[ny][nx][power]로 체크해야 한다.
if graph[ny][nx] == 0 and visited[ny][nx][power] == 0:
visited[ny][nx][power] = visited[y][x][power] + 1
queue.append((ny, nx, power))
# 2) 다음 칸이 벽(1)인 경우: power=1일 때만 한 번 부수고 이동 가능
# 벽을 부수고 이동하면 power는 0이 된다.
elif graph[ny][nx] == 1 and power == 1 and visited[ny][nx][0] == 0:
visited[ny][nx][0] = visited[y][x][1] + 1
queue.append((ny, nx, 0))
# 끝까지 도착 못하면 -1
print(-1)
Frontend Engineers