일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- boj
- 암호학
- activity
- MiTweet
- Gradle
- android
- Kotlin
- GitHub
- architecture
- Coroutines
- 코드포스
- androidStudio
- Hilt
- MyVoca
- Coroutine
- Codeforces
- 백준
- pandas
- 프로그래머스
- Python
- 코루틴
- Compose
- livedata
- TEST
- 쿠링
- ProGuard
- relay
- AWS
- Rxjava
- textfield
- Today
- Total
이동식 저장소
16946. 벽 부수고 이동하기 4 본문
벽 부수고 이동하기라는 제목이 달려 있지만, 원본과는 전혀 다른 문제이다.
각 벽에 대해 다음을 수행한다.
1. 벽을 부순다.
2. 부순 위치로부터 이동할 수 있는 칸의 개수를 센다. 이때 출발점도 세어야 한다.
아주 나이브한 방법으로, 모든 벽마다 BFS를 수행하면 정답을 구할 수 있다. 물론 그렇게 쉽게 풀릴 문제였으면 글을 쓰지도 않는다.
그러나 이 방법은 너무 오래 걸린다. 예를 들어 이런 입력을 생각해 보자.
10 10
1111111111
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0번째 행의 각 벽마다 bfs를 수행해야 하는데, 보다시피 중복된 탐색이 10번 이루어진다. 각 벽마다 bfs를 실행하는 코드의 시간 복잡도는 최대 O((N+M)NM)으로, 넉넉하게 시간 초과를 받을 수 있다.
어쨌든 탐색을 하긴 해야 하긴 하는데.. 위에서 문제가 된 중복 탐색을 없애면 되지 않을까?
여기까지 읽고 잠시 자신만의 풀이를 생각해 보자. 충분히 생각해 본 다음에 풀이를 읽길 바란다.
이 문제는 벽이 있을 때 상하좌우 네 방향으로 움직일 수 있는 칸의 개수를 구하는 문제이다. 우리는 이 문제를 4개의 동일한 부분 문제로 쪼갤 수 있다.
현재 칸에서 벽이 아닌 상하좌우 칸으로 이동했을 때, 그곳으로부터 몇 칸을 더 움직일 수 있을까?
벽이 아닌 칸은 크기가 1 이상인 "0 그룹"에 속한다. 여기서 "0 그룹"이란 "상하좌우로 움직여서 도달할 수 있는 0의 집합"이다. 각 칸마다 단 한 번의 bfs 탐색을 통해 모든 0 그룹을 찾을 수 있다.
이제 우리는 상하좌우에 있는 서로 다른 0 그룹의 크기의 합을 구하면 된다. "서로 다른"이 중요한 이유는 다음 입력을 보면 알 수 있다.
2 2
10
00
그룹을 구분하는 방법은 여러 가지가 있는데, 가장 쉬운 방법으로는 서로 다른 번호를 부여하면 된다.
이제 직접 코딩해 보자.
브론즈1 10개 푸는 것보다 이거 하나 푸는게 더 좋다. 경험치든, 실력이든..
'Problem Solving > BOJ' 카테고리의 다른 글
테스트 입력 파일을 쉽게 사용하는 방법 (0) | 2020.02.29 |
---|---|
2692. 양팔저울 (0) | 2020.02.28 |
2623. 음악프로그램 (0) | 2020.02.16 |
2263. 트리의 순회 (0) | 2020.02.02 |
13549. 숨바꼭질 3 (0) | 2020.02.02 |