[platinum3][해설,분류안봄] 16930 달리기 (조금 색다른 풀이)

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

 

bfs 가 메인인 플레티넘 문제는 거의 풀어본 적이 없는 것 같았는데, 역시나 까다로웠다.

남들과는 조금 다르게 disjoint set 분리 집합을 이용해 건너뛸 칸을 저장하면서 풀어갔다.

이런식으로  v[x][y][방향] 으로 방문을 저장했다.

초록색부분 처럼 왼쪽으로 이동할 수 있는 빈칸을 탐색하고 있을 때,  이미 방문한 칸을 마주치게 된다면(검정색마크) 

parent[x][y] = {x1,y1} , parent[x1][y1] = {x2,y2} .... parent[x4][y4] = {x5,y5} 이런식으로 방문하지 않은 칸이 나올때까지 parent를 새로 설정하고 , find함수를 이용해 다음에  왼쪽또는 오른쪽으로 (x1,y1) or (x2,y2)...(x4,y4)를 마주쳤을 때 바로 (x5,y5)로 건너뛸 수 있도록 한다.

 

 

이렇게 했을 때 탐색하면서 건너뛸 곳을 이미 정해두고, 다음에 탐색을 생략하면서 거의 선형적 O(N*M) 으로 문제를 풀 수 있게 될 것이다.

처음에는 저렇게 유니온 파인드를 이용해 점프하는 방식을 지금 진행하는 방향과 수직일때만 적용했다.

방금 전 예시는 진행하는 방향과 수평인 방향의 visit에서도 적용했는데, 사실 처음에는 그럴 필요가 없다고 생각했다.

 

x,y 가 x1,y1 으로 왼쪽으로 탐색하려고 할 때, 이미  방문한 노드들은  이미 그 노드들로 부터 왼쪽으로 최대 K만큼 탐색을 해나갔을 것이기 때문이다. 따라서  뒷북으로 탐색하려고 한 x,y는 x1,y1을 마주치는 순간 더 이상 탐색할 필요가 없으므로(이미 x1~4, y1~4에서 이전에 왼쪽을 탐색했을 것이기 때문에)  더이상의 탐색을 종료하게 되었다.  

아까전에 x,y  -> x5 ,y5 로 건너뛰었던 것과는 다르다.

 

그러나 이 방법은 어떤 반례가 있는지는 못찾았지만... 한참을 찾아도 모르겠어서 그냥 안전빵으로 유니온 파인드로 점프하는 방식을 택했다.

 

  평범한 골드3정도의 bfs 탐색처럼 보였지만 어떻게 탐색을 생략할 것인가 고민을 필요로 하는 문제였다.