[백준 2206] 벽 부수고 이동하기 (with Python / BFS)
문제링크
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
문제설명
문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
예제 입력 1 복사
6 4
0100
1110
1000
0000
0111
0000
예제 출력 1 복사
15
문제풀이
목표지점까지 BFS를 통해 이동하면서 갈수 있는 최단거리를 구하는 게 목표다.
한칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸.
틀린풀이 (처음 시도한 생각)
0. 시작위치 큐에 삽입.
deque([(0, 0, 0, 1)]) => 즉 큐를 생성하면서 (x, y, crush, cnt)를 삽입한것이다.
x, y는 시작좌표, crush는 벽을 부쉈는지 체킹하는 변수, cnt 는 출발지로부터의 거리값 갱신하는 변수.
1. 큐에서 현재좌표 뽑아내서 현재위치에서 갈 수 있는 다음위치를 계산 (상하좌우).
2. 다음위치에 있는 노드 방문가능한지 조건문 로직
- 조건문은 1차적으로 인덱스 범위에 있는지, 그리고 방문하지 않은 노드인지 체크
- 1차적으로 통과하면 노드가 (1) 길인 경우와 (2) 벽인 경우를 나누어 조건문 검사.
- 길인 경우에 거리값 갱신 및 큐에 다음위치와 갱신한 거리값 삽입 => append((nx, ny, crush, cnt + 1))
- 벽인 경우에,
- 부순적이 없다면 큐에 (다음 위치, 거리값 갱신한 변수, 부쉈는지 여부 판별하는 변수) 삽입.
=> append((nx, ny, crush + 1, cnt + 1))
이렇게 순조로울 거라고 생각했으나 18%에서 틀리고 말았다.
틀린 코드
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
# N 행 , M 열
graph = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[0 for _ in range(M)] for _ in range(N)]
cnt = 0
possible = False
answer = []
# 입력값 받아서 맵 채우기
for i in range(N):
graph[i] = list(map(int, input().rstrip()))
def BFS(x, y):
global cnt, possible
queue = deque([(x, y, 0, 1)])
while queue:
curX, curY, crush, cnt = queue.popleft()
# 목표 좌표에 도달했다면 서치 종료
if curX == N-1 and curY == M-1:
possible = True
answer.append(cnt)
for i in range(4):
nx = curX + dx[i]
ny = curY + dy[i]
# 인덱스 범위에 있고, 방문하지 않은 노드인지 체크
if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
# 노드가 0이면 방문
if graph[nx][ny] == 0:
queue.append((nx, ny, crush, cnt + 1))
visited[nx][ny] = 1
# 다음 이동할 좌표가 벽이라면
else:
# crush값이 0 이면(그전에 벽 부수지 않았다면)
if not crush:
queue.append((nx, ny, crush + 1, cnt + 1))
visited[nx][ny] = 1
return possible
if BFS(0, 0):
print(min(answer))
else:
print(-1)
올바른 풀이
도저히 모르겠어서 서치해보니 역시나 예외인 테케가 있었다.
노드를 방문했었던 것이,
기존에 벽을 부순적이 있는 상태에서 방문한건지,
부순적이 없는 상태에서 방문한건지 알아야 할 필요가 있다.
즉, 무슨말이냐 현재위치까지 오면서 벽을 부쉈는지 여부에 따라 visited 저장을 다르게 해야한다.
visited리스트를 기존과 다르게 visited[check][nx][ny]로 바꾸어 구현하자.
코드
정답코드
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
# N 행 , M 열
graph = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
possible = False
answer = []
# 입력값 받아서 맵 채우기
for i in range(N):
graph[i] = list(map(int, input().rstrip()))
def BFS(x, y):
global possible
queue = deque([(x, y, 0, 1)])
while queue:
curX, curY, crush, cnt = queue.popleft()
# 목표 좌표에 도달했다면 서치 종료
if curX == N-1 and curY == M-1:
possible = True
answer.append(cnt)
for i in range(4):
nx = curX + dx[i]
ny = curY + dy[i]
# 인덱스 범위 체크
if 0 <= nx < N and 0 <= ny < M:
# 방문안한 노드라면
if not visited[nx][ny][crush]:
visited[nx][ny][crush] = 1
# 다음 이동할 노드가 길이라면
if graph[nx][ny] == 0:
queue.append((nx, ny, crush, cnt + 1))
# 다음 이동할 좌표가 벽이라면
else:
# 벽인데 그전에 다른벽을 부순적이 없다면
if not crush:
queue.append((nx, ny, crush + 1, cnt + 1))
# 벽인지 길인지 체크가 먼저냐
# 아님 방문여부, 인덱스범위 체킹이 먼저냐 생각해보기
# 일단 인덱스범위는 1차적으로 체킹해야될듯
# => 잘못된 범위 참조해서 인덱스 오류날 수 있음
return possible
if BFS(0, 0):
print(min(answer))
else:
print(-1)