백준 3197번 백조의 호수

문제 링크입니다: https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

1500이라는 숫자가 생각보다 큰 숫자라는 것을 깨닫게 된 문제였습니다.

처음에는 단순 BFS로 접근했다가 TLE가 발생하였기 때문에 최대한 시간을 줄이고자 노력했습니다.

 

알고리즘은 아래와 같습니다.

1. 호수 정보를 입력받을 때 백조의 위치를 저장하고 얼음이 아니라면 waterQ에 좌표를 넣어줍니다.

2. 전형적인 BFS 문제처럼 접근하는데 우선 백조 한 마리를 최대한 움직여봅니다.

2.1 물에 인접한 얼음은 다음에 탐색할 공간이므로 nextQ에 좌표를 넣어주고 현재 물인 지점 혹은 다른 백조가 있는 지점만 q에 좌표를 넣어줍니다.(이 때, 어느 큐에 넣든 해당 좌표는 이미 방문했다고 표시해줍니다.)

2.2 다른 백조를 만나는 즉시 while문을 빠져나오고 경과한 일 수를 출력하며 프로그램을 종료합니다.

3. 2번에서 프로그램이 끝나지 않는다면 물에 인접한 얼음을 녹여줍니다.

4. 백조들끼리 만날 때까지 2, 3번을 반복해줍니다.

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

 

* 비주얼 스튜디오에서는 메모리가 부족한지 string lake[MAX]를 전역변수로 선언하면 프로그램이 바로 종료해버리네요.