[BOJ] 3055번: 탈출

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

 

고슴도치가 {x, y}를 지나가기 위해서는 물보다 {x, y}에 먼저 닿아야합니다. 아이디어 자체는 BFS인데 BFS에서 물보다 빨리 닿는지를 판단할 수 있어야합니다. 그 방법은 바로 큐 안에 물이 잠식하는 영역과 고슴도치가 방문하는 영역을 함께 담는 것입니다. 물과 고슴도치는 isVisited 변수(혹은 depth 변수)를 공유합니다.

 

예를 들어 물이 (0, 3), (2, 6)에 있고 고슴도치가 (1, 1)에 있다고 할 때

 

큐에 (0, 3, false) | (2, 6, false) | (1, 0, true)을 담습니다.(false, true는 고슴도치인지 물인지 판단하기 위한 변수.) 이후 BFS를 수행하고 나면

 

큐에(0, 4, false) | (0, 5, false) | (1, 3, false) | (2, 5, false) | (2, 7, false) | (1, 6, false) | (3, 6, false) | (1, 1, true) | (2, 0, true) | (0, 0, true)가 담기게 되고 이후 (1, 2) 영역을 생각해보면 물이 (1, 3, false)에서 먼저 갈 수 있으므로 큐에서 (1, 1, true)를 가지고 사방을 판단할 때 (1, 2) 영역은 이미 방문했으므로 고슴도치가 방문할 수 없습니다.

 

이렇게 큐가 비거나 Destination을 만날 때 까지 BFS를 돌립니다. 만약 Destination을 만나지 못하고 큐가 빈다면 고슴도치가 큐에 갈 수 없다는 의미입니다. 쓰이는 아이디어는 BOJ 5427번 문제와 동일합니다.

 

https://github.com/encrypted-def/BOJ/blob/master/3055.cpp