[백준/자바] 16946 벽 부수고 이동하기 4

16946 벽 부수고 이동하기 4 사진 클릭시 문제로 이동

---

문제

N×M의 행렬로 표현되는 맵이 있다.

맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.

한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다.

두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다.

다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다.

원래 빈칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

예제 입력 1

3 3
101
010
101

예제 출력 1

303
050
303

예제 입력 2

4 5
11001
00111
01010
10101

예제 출력 2

46003
00732
06040
50403

---

설명

해당 문제는 다음 알고리즘 분류를 가진다.

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색
• 분리 집합

처음에는 문제가 무슨 소린가 했다.

 

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

이 말의 뜻은 1의 위치를 0으로 변환하고 인접한 0 그룹의 개수를 채워 넣으면 된다는 의미였다.

 

N과 M이 각각 최대 1000이기 때문에 bfs를 여러 번 돌렸다가 시간 초과가 발생했다.

이를 해결하기 위해서 우선 분리 집합개념을 이용해 0으로 이루어진 그룹에 번호를 지정하고 해당 그룹의 개수를 센다.

예제 2번

그룹 번호	그룹 수
1	2
2	3
3	1
4	1
5	1
6	1

 

이렇게 <그룹 번호, 그룹수> 구한 뒤 1을 가진 영역을 차례로 살펴본다.

예를 들어 현재 빨간색 동그라미 위치의 1을 살펴본다고 하자.

이때 주위의 그룹의 수는 1, 2, 3이 된다.

이 그룹 번호에 해당하는 수의 그룹 수의 합 + 1을 하면 해당 위치의 이동할 수 있는 칸의 수가 나오게 된다.

이때 같은 그룹으로 둘러싸진 경우가 있을 수 있으며 둘러싼 그룹의 번호를 구할 때는 HashSet을 사용해 중복을 제거해야 한다.

 

코드