2206번 벽 부수고 이동하기(BFS, 조건) - ☆

#문제링크 : https://www.acmicpc.net/problem/2206

전략 : https://www.acmicpc.net/board/view/27386

위의 링크와 같은 전략이고, 좀 더 설명을 붙이자면, 단순히 큐에 벽을 부쉈는지 안부쉈는지의 상태(smash)만 추가해서 이중 check배열로 거리를 갱신해간다면, 벽을 부수고 목표에 도달하는 경우와 벽을 부수지 않고 목표에 도달하는 경우, 나중에 벽을 부수고 목표에 도달하는 경우들이 맞물려서, check 배열에 오버랩(중복갱신)된다. 상태라는 개념을 check배열에도 넣어서 갱신되는 정보가 누락되거나 중복되지 않게 기록을 해야만 하는 것이다. 그래서 check 배열을 3중 배열로 선언했고, 가다가 벽을 부순다면 상태를 1로 만들어서 check[][][1]에 기록하도록 했고, 벽을 부수지 않는다면, check[][][0]에 기록하도록 했다. 코드 로직이 bfs의 한뎁스마다 바로바로 최단 거리가 갱신되도록 되어있기 때문에, 목표 행렬로 갱신이 되면 무조건 최단이 되고, 목표 행렬에 도달하지 못하면 -1을 반환하도록 했다. 세세한 로직을 따라가기는 어렵지만 큐에 들어가는 내용은, 처음부터 벽을 부수고 가는 경로, 한 타임 뒤에 벽을 부수고 들어가는 경로, 두 타임 뒤에 벽을 부수고 들어가는 경로 ... 마지막에 벽을 부수고 도착하는 경로까지 모든 경로가 큐에 들어가고 빠져나온다. 즉, 목표에 도달하기 전까지는 뒤죽박죽으로 중복갱신되기도 하고 누락되기도 한다. 하지만 최종, 목적지에 값이 생길 수 있다면 무조건 당연하게도 최단의 경로가 나온다. bfs의 구조적 특징이 적용되기 때문이다.

※주의사항

1. cin과 scanf를 혼용하면 안된다.

2. '상태'라는 새로운 변수를 check배열에 추가한다. 추가하는 방식은 차원을 증가시키는 것.

3. Queue에는 조건을 만족하는 모든 경로가 Push 된다. 

4. check[][][0]에는 벽을 부수지 않고 나아가는 경로에 거리값이 갱신된다.(누락되는 경로가 있다. = 벽)

5. check[][][1]에는 벽을 부수고 나아가는 경로에 거리값이 갱신된다. (중복갱신된다.)

Code

입력 -> check[][][0] 배열 -> check[][][1] 배열