[백준 2206번] 벽 부수고 이동하기 - java

문제 설명

1. N x M 크기의 맵이 나타난다. [ 0은 이동가능 ] [ 1은 이동불가 ] 이다.

2. 근데 벽을 한번은 부수고 이동할 수 있다.

3. 0, 0 -> N-1, M-1 로 가는 최소거리를 구해라~

풀이 과정

 1. 최소거리 -> BFS를 이용하고 벽을 부수는 것은 class내에 벽을 부술 수 있는 값을 주면 된다.

 2. 최소 거리를 구하는 경우 BFS를 사용하고 간 길을 check해 주면, 뒤에 도달하는 경우 무조건 현재상황보다 늦게 도달하거나, 동시에 도달함으로 check해 준 길을 다시 오지 않게 해 주면 된다.

 3. 그런데 만약에 한번 벽을 부수어서 그냥 오는 것보다 빠르게 해당 route에 도달했는데, 목적지에 도달하려면 목적지 앞의 벽을 부숴야 하는 경우가 생긴다면 곤란할 것이다.

 

예를 들어 다음과 같은 경우

0000
0110
1100
0001
0111
0010

 

벽 부숨  -> (2,0)위치의 벽을 부수면 (3,0)의 위치에 벽을 부수지 않은 경우보다 먼저 도달 가능하다. 근데 이 경우는 결국 목적지에 갈 수 없다.

안 부숨  -> (2,0)위치에는 늦게 도달하지만 목적지에 도달 가능하다.

 

 4. 따라서 벽을 부순 경우 / 부수지 않은 경우 두 가지의 check배열을 하나씩 만들어서 체크해 주면 된다.

 

 5. 그렇다면, 두 가지 경우로 나누어 class에서 벽을 부순 경우 그 떄의 배열을 검사하고, 아닌 경우 아닌 것에 해당하는 배열을 검사하며 진행하면 된다.

 6. 사실 간단히 구현 가능한 문제이다. class를 다루는 법 정도만 알면 쉽게 풀 수 있을 것이다.

코드