[Baekjoon] 2206. 벽 부수고 이동하기 [G4]
📚 문제
https://www.acmicpc.net/problem/2206
📖 풀이
최단경로이니 BFS로 구현한다.
visited를 3차원으로 표시한다. 2차원의 위치에 [이동거리, 상태]를 넣어준다.
상태는 방문하지 않은 경우 : 2, 벽을 부수고 방문한 경우 : 1, 벽을 부수지 않고 방문한 경우 : 0이다.
이동거리는 최대 이동거리보다 크게 대략 n * m으로 초기화 한다.
상태는 방문하지 않았으므로 2로 초기화한다.
-
델타 탐색을 할 때 벽을 만나는 경우, 현재 부순 횟수가 0인 경우만 벽으로 이동할 수 있다. 그 때 부순 횟수를 1로 증가시킨다.
부순 횟수가 1이면 이동하지 않는다.
-
벽을 만나지 않는 경우에는 2가지로 생각해볼 수 있다.
-
부순 횟수가 같거나 큰 경우
BFS 탐색에서 부순 횟수가 같은 경우는 최단 거리가 아니므로 탐색하지 않는다.
-
이동하는 곳의 부순 횟수가 더 많은 경우
부순 횟수가 더 적은 걸로 더 탐색해봐야 한다.
처음 탐색하는 곳이면 2이니까 부순 횟수가 0, 1이면 갱신하고,
부순횟수가 1로 탐색한 경우는 0으로 탐색해볼 수 있다.
-
반복문을 도는 도중 n-1, m-1 인덱스의 상태가 2가 아니면 값이 들어갔다는 것이니 반복문을 종료하고 출력한다.
반복문이 끝나고도 n-1, m-1 인덱스의 상태가 2이면 -1을 출력한다.
📒 코드
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
arr = [list(map(int, input().rstrip())) for _ in range(n)]
INF = n * m
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
visited = [[[INF, 2] for _ in range(m)] for _ in range(n)]
queue = deque()
queue.append((0, 0))
visited[0][0] = [1, 0]
while queue and visited[n-1][m-1][1] == 2:
y, x = queue.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if not(0 <= ny < n and 0 <= nx < m):
continue
if arr[ny][nx] == 0 and visited[y][x][1] < visited[ny][nx][1]:
visited[ny][nx] = [visited[y][x][0] + 1, visited[y][x][1]]
queue.append((ny, nx))
else:
if visited[y][x][1] == 0 and visited[ny][nx][1] == 2:
visited[ny][nx] = [visited[y][x][0] + 1, 1]
queue.append((ny, nx))
if visited[n-1][m-1][1] == 2:
print(-1)
else:
print(visited[n-1][m-1][0])
🔍 결과
Author And Source
이 문제에 관하여([Baekjoon] 2206. 벽 부수고 이동하기 [G4]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/Baekjoon-2206.-벽-부수고-이동하기-G4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)