https://www.acmicpc.net/problem/2206

5 8
01000000
01010000
01010000
01010011
00010010

ans: 20

어려웠다. 나 혼자서는 풀 수 없는 문제였다. 깔끔하게 인정.

이 페이지에서는 다른 사람의 블로그에 있는 정답코드와 설명을 내가 이해한 대로 정리해보려고 한다.

https://iseunghan.tistory.com/316

이 문제에서 짚고 가야 할 포인트를 두 가지로 보았다.

먼저 벽을 뚫을 수 있는 상태를 dirll = 0, 이미 한번 뚫은 상태를 drill = 1 라고 하자.

1. 한 정점에서 목적지 정점까지의 각 경로에서 드릴을 한 번만 사용핳 수 있다.

   한 정점에 대해서 목적지로 가는 경로는 여러가지 경로가 있다.

   예를 들어 (0,0) 정점부터 시작한다고 하면 (0,0)에서 부터 목적지로 향하는 경로는 (1,0)을 거쳐 가는 경로와 (0,1)을 거쳐 가는 경로 두 가지이다. 두 가지 경로를 모두 살펴보면,

   먼저 (1,0)을 거친다고 하자. (1,0)을 탐색했을 때는 (1,0)이 벽이 아니므로 드릴을 사용할 필요가 없다.

   하지만 (0,1)을 거쳐가면 (0,1)이 벽이므로 드릴을 사용해야 하고 이후에 파생되는 경로에서는 드릴을 사용할 수 없다. 그래서 한 정점에 대해서 분기되는 정점에 드릴의 사용가능 여부를 알아야 한다. (= 다음 정점에서 드릴을 사용할 수 있는지 없는지에 대한 정보가 있어야 한다.)

보통 지금까지 BFS를 한 방식은, 큐에다가 한 정점에 대해서 분기되는 다음 정점이 무엇인지 넣어주었다. 여기서는 이 점을 이용해서 큐에다가 다음 정점(이웃한 정점)이 무엇인지와 함께 그 정점에서 드릴의 사용가능 여부도 함께 넣어준다.

1. 드릴을 사용한 상태에서 방문? 사용하지 않은 상태에서 방문?

앞서 큐에다가 이웃한 정점의 값을 넣을 때, 드릴 사용가능여부도 넣어준다고 했다.