[c++] 백준 벽 부수고 이동하기 2(14442), bfs, 반례모음

문제 https://www.acmicpc.net/problem/14442

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

 

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자

 

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

반례모음

1 1 1 0 1

3 3 2 011 111 110 -1

2 4 2 0111 0110 5

3 3 10 011 011 000 5

3 3 3 011 111 110 5

5 5 4 01101 11100 00111 11110 00110 9

 

풀이

• 벽을 K개 까지 부술 수 있고, K는 10개까지 설정 가능하다. 따라서, 벽을 부술 때마다 새로운 map에 이동하도록 합니다.
• 위의 그림처럼 벽을 만났을 때, 아직 벽을 K개만큼 부수지 않았다면 다음 layer로 이동해서 최적의 경로를 탐색합니다.
• 따라서, map의 방문여부를 체크하는 배열을 3차원으로 구성
• 벽을 만났을 때와 만나지 않았을 때를 분리해서 조건처리 해줍니다.
• 더 시간을 줄이고 싶다면, 다음 방문할 좌표가 이전 layer들에서 방문하지 않았을 때에만 방문하도록 합니다.

 

코드

• 일반적인 bfs와 비슷하게 큐에 다음 탐색할 좌표(x,y)를 쌓아주는데, 여기서는 현재 floor에 대한 정보다 함께 쌓아줍니다. 따라서 튜플 자료형으로 3개 인자를 받습니다. 튜플에 대한 내용은 아래 링크에서 확인할 수 있습니다.
  https://forward-gradually.tistory.com/56

[c++] Tuple 사용법

 

• 큐에서 하나씩 front()로 뽑아내서, 인접한(4방향) 좌표를 탐색합니다.
• 벽을 만났을 때와 만나지 않았을 때를 조건문으로 분리합니다.
• 벽을 만났을 경우에는 cur_floor(현재 층)에 따라서 벽을 부술 수 있는지 체크하고, 가능하다면 부수고, map_check에 다음 층에 count합니다. 
• 벽을 만나지 않았을 경우에는 현재 거주하고 있는 층에서 탐색하므로 일반적인 bfs와 동일합니다.

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%EB%B2%BD%20%EB%B6%80%EC%88%98%EA%B3%A0%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0%202(14442).cpp