[백준 / BOJ] 3197 백조의 호수

문제

출처 : www.acmicpc.net/problem/3197

3197번: 백조의 호수

호수에 백조 두마리가 살고있다.

호수의 어떤칸은 얼음으로 덮여있으며, 매일 물과 접촉해있는부분은 녹는다.

 

백조는 얼음이 없는 위치로 움직일수있을때, 두 마리의 백조가 만나기위해 걸리는 최소 시간을 구하는 문제다.

 

풀이

BFS와 다익스트라로 푼 문제다.

백조는 움직일때 시간이 걸리지않는것에 유의해야했다.

 

구현은 

백조가 어떤칸에 가기위해선 해당칸까지 가는 경로가 전부 얼음이 아니여야한다. 따라서, 해당 칸이 녹는날짜에 백조가 이동할수있다.

즉, 모든 칸이 물이 되는시간을 미리 구해놓으면 백조가 해당칸으로 이동하기까지 필요한 날짜를 쉽게 구할수있다.

각 칸의 얼음이 녹는시간은 (얼음은 돌아서녹지않고 항상 인접한 위치부터 순차적으로 녹음) BFS로 구할수있다.

 

1. 기본적인 BFS로 각 칸이 녹는시간을 모두 구해놓는다.

 

2. 백조를 물이 녹는시간을 기준으로 이동시킨다.

이제 백조를 이동시켜야하는데, 백조가 만나는시간은 BFS로 구할수없다.

이유는 - BFS로 구현할경우, 백조가 i,j로 가기위해서 위치기준으로 최소경로를 찾을건데, 이는 얼음이녹는 날짜 기준으로는 최소경로가 아닐수도 있기때문이다. 

얼음이 녹는시간을 저장한 배열이 다음과 같다고하자. (백조의 위치는 L이며, 도착지는 E)

 

1 0 0 0 0 

1 E 1 1 0

1 1 1 L 0

1 1 1 1 1

 

BFS로 탐색할경우, E까지 도달하기위해 필요한시간은 우선 1이된후(위치기준으로 최솟값을 찾음) 0으로 바뀔것이다.(위치기준으로 최솟값을 찾기때문에 더 작은값이 나올수있다!)

 

따라서, 다익스트라를 이용해 이동날짜 기준으로 탐색을 시켜줘야한다.

 

이때, 다음과 같은 경우 도착지에 도착했을때 백조의 이동날짜는 2임에 주의하자.

- E까지 가기위해서, 2일째에 물이녹는위치를 항상 지나가야함

0 0 0 0 0 0

0 2 2 2 0 0

0 2 L 2 0 E 

0 2 2 2 0 0

0 0 0 0 0 0

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/3197%20%EB%B0%B1%EC%A1%B0%EC%9D%98%20%ED%98%B8%EC%88%98/main.cpp

devxb/JJUNalgo