일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- GitHub
- 프로그래머스
- android
- 암호학
- 코드포스
- Codeforces
- Compose
- 쿠링
- textfield
- relay
- androidStudio
- AWS
- Hilt
- Coroutine
- Python
- architecture
- Kotlin
- TEST
- MiTweet
- pandas
- Gradle
- 코루틴
- Coroutines
- activity
- 백준
- MyVoca
- livedata
- boj
- ProGuard
- Rxjava
- Today
- Total
이동식 저장소
3197. 백조의 호수 본문
이 문제의 대회 데이터가 공개되어 있으니 사용해 보자. 원문 제목은 labudovi이다.
3197번: 백조의 호수
문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX
www.acmicpc.net
얼음을 녹이면서 백조가 만날 수 있는지 확인해야 한다.
물과 인접한 얼음이 녹는다는 설명에서 BFS를 적용해야 함을 알 수 있다. 그런데 $O(V^3)$짜리 단순한 BFS로는 시간 초과를 받는다.
사실 이 글은 3197번에 대한 풀이라기보단 최적화를 이루기 위한 나의 장대한 일대기라고 불러도 좋을 것이다. 집에만 있으니까 조금 이상해졌나 보다.
BFS를 시작할 칸을 찾을 때
BFS를 할 때마다 $O(V^2)$짜리 탐색을 하는 것은 좋지 않다. 대신 queue의 원소를 계속 재사용하면 시간을 줄일 수 있다. 즉 어떤 BFS의 단말 노드(더 이상 탐색할 칸이 없는 원소)는 다음 BFS의 시작 원소이므로, 이것들을 저장해 놓으면 다음 BFS를 즉시 시작할 수 있다.
Case 1. 백조가 움직이다가..
- 물을 만났을 때: 탐색 queue에 넣고 계속 움직인다.
- 얼음을 만났을 때: 지금 탐색할 수는 없지만, 다음 날에 얼음이 녹으면 이 칸을 탐색할 수 있다. 따로 저장했다가 이번 탐색이 끝난 후 탐색 queue로 모두 옮겨야 한다.
- 다른 백조를 만나면: 정답을 구했다!
Case 2. 얼음이 녹는데..
- 주변 칸이 얼음이라면: 다음 날에 이 칸이 녹을 예정이므로, 오늘 녹을 얼음과 별도로 저장했다가 재활용하자. 위의 2번에서 얼음을 만났을 때와 같은 맥락이다.
- 주변 칸이 물이라면: 무시한다.
무언가 퍼져나가는 BFS를 구현할 때, 위의 방법론을 사용하여 시간을 줄일 수 있다. 이 문제의 강화판으로 14868. 문명이 있으니 한번 도전해 보자. 난 안 할거다.
'Problem Solving > BOJ' 카테고리의 다른 글
3665. 최종 순위 (0) | 2020.06.21 |
---|---|
1039. 교환 (0) | 2020.04.12 |
1103. 게임 (0) | 2020.04.01 |
1509. 팰린드롬 분할 (0) | 2020.03.29 |
2169. 로봇 조종하기 (0) | 2020.03.27 |