[백준 2206] 벽 부수고 이동하기 [Java]

백준 2206 - 문제

백준 2206 - 입/출력

---

풀이

(0, 0)에서 (N - 1, M - 1)까지 최대 벽을 1개 부수며 도착할 수 있는 최단거리를 구하면 되는 문제다.

하나의 2차원 배열에 최단거리를 기록하기에는 어느 순간 벽을 부술때와 부수지 않는 경우 중 어떤 경우가 더 빨리 도달할지 기록하기 어렵다.

때문에 두 경우에 대해 최단거리를 기록하고, 가장 먼저 (N - 1, M - 1)에 도달한 경우의 최단거리를 출력해주면 된다.

2차원 배열을 벽을 부수는 경우와 부수지 않는 경우로 하지 않고, queue에 넣어줄 때 현재의 최단거리를 가지고 있는 Point객체를 넣어주는 방식으로 풀이했다.

bfs를 진행하며 다음 영역이 벽이 아니라면, 벽을 부순경우와 부수지 않은 경우 모두 아무 제한 없이 queue에 넣어주면 된다.

만약 다음 영역이 벽이라면, 벽을 부수지 않았고(smash == 0), 이전에 벽을 부수고 이동했을 때 방문한 적 있는지( !visited[1][nx][ny] ) 확인하고 queue에 넣어주면 된다.

 

만약 목적지에 도달했다면 최단거리를 출력해주자.

객체에 거리를 넣어주는 방식이 아닌, visited[2][N][M]을 int형으로 선언해 거리를 갱신해주는 방법도 풀이가 가능하다.

하지만, 목표에 도달해 탐색하지 않은 영역에 대해서도 공간을 할당하는 방법이라 위와 같은 방법을 선택했다.

---

소스코드

소스코드 보기

---

출처

2206번: 벽 부수고 이동하기