[백준] 14442번: 벽 부수고 이동하기 2 (C++ 풀이)

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

풀이

dist배열을 3차원으로 두고 BFS탐색을 해서 풀었다.

1. dist[x좌표][y좌표][벽을몇개부셨는지]

2. 벽이 없고 그냥 빈칸이면 dist[nx][ny][wall] = dist[x][y][wall] + 1;

3. 벽이 있다면 wall+1이 k이하의 값인지 확인해야한다. 왜냐하면 문제에서 벽은 k번까지 부실 수 있다고 되어있기 때문이다. dist[nx][ny][wall + 1] = dist[x][y][wall] + 1;

4. BFS탐색을 마치고 for(i: 0~k)로 0이 아닌 최소값을 구해서 출력한다. 만약에 다 0이면 갈수있는 방법이 없는 것이므로 -1을 출력한다.

 

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/14442.cpp

결과