(JAVA) 백준 3197번 : 백조의 호수 --- [BFS]

www.acmicpc.net/problem/3197

3197번: 백조의 호수

 

안녕하세요. 

 

이 문제는 BFS 알고리즘 문제입니다.

solved.ac 에서 골드1 문제 입니다.

 

 

오랜 시간 고민하고 풀었습니다.

 

처음에 작성한 매커니즘은 시간 초과가 발생해서, 한참을 줄이려고 고민했습니다.

 

그러다 BFS 알고리즘 두 번을 사용해서 해결하는 솔루션을 찾아냈고, 이를 통해 문제를 해결했습니다.

 

다른 풀이를 참고해보니

BFS + 우선순위큐, Disjoint-Set 알고리즘 등의 방법이 있었습니다만,

저는 BFS + 우선순위큐를 사용해서 해결헀습니다. (하지만 속도는 조금 느리더군여..)

 

 

우선, 짚고 넘어갈 부분을 확인해보자면

 

  -  백조가 서 있는 곳 또한 물입니다. 그래서 1초가 경과하면, 백조 주위의 얼음이 녹아야 합니다. (이것때문에 한 번 틀렸었습니다.)

 

  -  구하려는 답은 최단 거리가 아닙니다. 얼음이 녹고, 백조 -> 백조 이동이 가능한 최소 시간 입니다. 

즉, BFS 알고리즘을 통해 얻는 값은 백조 -> 백조 이동할 때, 중간에 있던 얼음들 중 가장 큰 시간 입니다.

*** 말이 좀 헷갈리는데, 소스코드를 참고하시면 될 것 같습니다.

 

  -  1초당 한 번씩 모든 물 주위의 얼음을 녹이려고 하는 시도는 무조건 시간 초과가 발생합니다. (1초)

그렇기 때문에, 별도의 int 배열을 만들어 해당 얼음이 녹을 수 있는 시간을 미리 계산해서 담아둬야 합니다.

 

 

 

매커니즘

---

  1)  우선순위 큐에 '.' 인 좌표 값(x,y) 을 모두 집어넣기 (초기 물의 위치. 이를 통해 각각의 얼음들이 녹을 수 있는 시간을 계산하고자 함)

 

 

  2)  BFS 알고리즘을 통해 모든 얼음의 녹는 시간을 별도 int 2차원 배열에 저장

 

  ***  방문 체크 필수. 이에 더해, 기존에 계산해둔 녹는 시간과 비교해서 적게 녹는 시간인 경우에 큐에 새로 집어넣기

 

 

  3)  BFS 알고리즘을 통해 백조 -> 백조 이동할 때 중간중간에 존재하는 얼음들 중 최고 시간 얻어서 출력

 

  ***  우선순위 큐를 사용하기 때문에, 가장 먼저 백조에 도착하는 경우가 가장 빨리 녹는 얼음들을 지나가는 경로입니다. 그래서 그 얼음들이 전부 녹아야 이동할 수 있으니까 얼음들 중 가장 녹는 시간이 오래 걸리는 값을 얻기만 하면 끝입니다.

 

  ***  2) 와 마찬가지로 우선순위 큐를 사용하기 때문에 방문 체크 필수.

 

  ***  현재 큐에서 꺼낸 count 값과 배열에 저장해둔 녹는 시간과 비교해서 배열의 녹는 시간이 큰 경우에는 배열의 값으로 큐에 새로 집어넣고, 반대의 경우에는 현재 count 값을 그대로 큐에 집어넣으면 됩니다.

 

 

 

 

나머지 자세한 부분은 소스코드 참고해주시고

혹시 궁금하거나 모르는 부분이 있다면 댓글 부탁드립니다.

 

 

감사합니다!

 

 

소스코드

---