이동식 저장소

16946. 벽 부수고 이동하기 4 본문

Problem Solving/BOJ

16946. 벽 부수고 이동하기 4

해스끼 2020. 2. 18. 16:17
 

16946번: 벽 부수고 이동하기 4

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

www.acmicpc.net


벽 부수고 이동하기라는 제목이 달려 있지만, 원본과는 전혀 다른 문제이다.

 

각 벽에 대해 다음을 수행한다.

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
Comments