[C++] 백준 16933 - 벽 부수고 이동하기 3

🔐 백준 16933 - 벽 부수고 이동하기 3

https://www.acmicpc.net/problem/16933

🔑 풀이

N × M 행렬이 주어지고, 시작점(1, 1)에서 도착점(N, M)으로 이동하는 최소 이동 횟수를 구하는 문제입니다.

이 과정에서 필요한 제약 조건은 다음과 같습니다.

• 최대 K개의 벽을 부술 수 있다.
• 낮밤이 존재하며, 이동 시마다 낮 ↔ 밤이 전환된다.
• 낮에는 벽을 부술 수 있지만, 밤에는 불가능하다.
• 밤에는 이동하지 않고 기다릴 수도 있다. (이동하지 않아도 낮밤은 바뀜)

BFS에서는 무한 루프 방지와 최단 거리 보장을 위해 한 번 탐색한 상태를 다시 탐색하지 않아야 합니다. 이 문제에서는 일반적인 BFS와는 다르게 좌표, 남은 벽 부수기 횟수, 낮/밤 상태의 여러 상태가 존재합니다. 즉, 같은 좌표라도 벽 부수기 횟수나 낮/밤 상태가 다른 경우 다른 상태로 간주해야 합니다. 그렇기 때문에 visited배열을 4차원 배열로 선언하여 관리합니다.

bool visited[1001][1001][11][2]; // [x][y][남은 벽 부수기][낮/밤]

예를 들어 (2, 3) 좌표에서는

• 낮에 벽 부수기 횟수 1이 남아있다면 벽을 부수고 이동할 수 있지만,
• 밤에 벽 부수기 횟수 1이 남아 있어도 벽을 부술 수 없기 때문에 같은 (2, 3) 좌표라도 최단 경로 계산이 달라집니다.

단순히 좌표만 체크하는 2차원 visited 배열로는 올바른 결과를 보장할 수 없기 때문에, 4차원 배열로 상태를 정의하고, 방문 여부를 판별할 수 있도록 했습니다.

🧩 코드

✨ 주의
이 글에서 제시한 코드는 문제를 해결할 수는 있지만, 최적의 풀이 방법은 아닙니다.
더 빠른 알고리즘이나 다른 접근법이 있을 수 있으니, 아이디어 참고 정도로 활용해 주세요.