[백준] 벽 부수고 이동하기 4 (16946번)

문제

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

---

해당 칸에서 이동할 수 있는 방의 최대 크기를 구하는 문제다.

0인 곳은 해당이 안 되고 1인 곳을 0으로 바꿨을 때 인접한 모든 방의 크기를 더해서 10을 나눠 출력해주면 된다.

 

처음엔 bfs로 0인 곳의 크기만 구해서 저장한 후에, 인접한 0의 방의 크기를 모두 더해서 출력하면 되겠다고 생각했는데 예외가 있었다.

 

0	0	0
0	1	0
0	0	0

 

의 경우를 생각해보자. 정답은

 

0	0	0
0	9	0
0	0	0

 

일것이다.

그러나 내가 원래 푼 방식은 1의 위에서 8, 오른쪽에서 8, 아래에서 8, 왼쪽에서 8을 더해서 33%10 = 3을 출력하게 됐다.

이처럼 인접한 변이 하나의 큰 방으로 연결된 경우엔 딱 한번만 더하도록 해야한다. 

 

따라서 각 0의 위치에 방의 크기가 아닌 인덱스를 저장한다. 이 인덱스는 방의 크기를 저장한 vector의 인덱스이다.

1은 벽이기 때문에 -1로 두고, 0인 곳은 인접한 모든 0을 같은 인덱스로 저장한다.

 

예를 들어 

 

0	1	0
1	0	0
0	1	1

 

라면 인덱스를 저장하는 배열 visit는

 

0	-1	1
-1	1	1
2	-1	-1

 

이 될 것이다. 그리고 해당하는 방의 크기를 저장하는 벡터 roomSize는 {1,3,1}이 될 것이다. 

각 인덱스와 방의 크기가 연결됨을 잘 확인하자. 

bfs를 통해 지도의 모든 연속된 방의 인덱싱과 크기를 구한 후 결과를 출력하면 된다.

 

결과 출력도 마냥 쉽진 않은데, map을 이용해 인접한 네 방향에서 방 크기의 인덱스를 모두 구한다. 따라서 중복된 방의 크기를 더할 일이 없이 정답을 구할 수 있는 것이다. 코드를 천천히 보면서 이해해보자.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%B2%BD%20%EB%B6%80%EC%88%98%EA%B3%A0%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0%204%20(16946%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
#include <map>
#include <string>
using namespace std;

int N, M;
int p[1001][1001]; // 지도
int visit[1001][1001]; // roomSize의 인덱스를 저장하는 배열
vector<int> roomSize; // 각 인덱스가 해당 인덱스가 기록된 visit의 연속된 0의 크기를 저장한다.
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };

void bfs(int a, int b, int c) {
	queue<pair<int, int>> q;
	q.push({ a,b });
	visit[a][b] = c; //시작점을 c 인덱스로 지정

	int curMax = 1; // 현재 연속된 0의 크기
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx<1 || ny<1 || nx>N || ny>M) continue;
			if (p[nx][ny] != 0) continue;			
			if (visit[nx][ny] == -1) {
				q.push({ nx,ny });
				visit[nx][ny] = c;
				curMax++;
			}
		}
	}
	roomSize.push_back(curMax); // 해당 방의 크기를 인덱스에 맞게 기록한다.
}

int main()
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string str;
		cin >> str;
		for (int j = 1; j <= M; j++) {
			p[i][j] = str[j - 1] -'0';
		}
	}

	memset(visit, -1, sizeof(visit)); // 방문 안했으면 -1

	int idx = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (p[i][j] == 0 && visit[i][j] == -1) {
				bfs(i, j, idx++); // 해당 방의 크기를 roomSize[idx]에 기록한다.
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (p[i][j] == 0) { //0이면 바로 출력
				cout << 0;
				continue;
			}

			map<int, int> m; // 근처 방의 인덱스를 저장할 맵
			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				if (nx<1 || ny<1 || nx>N || ny>M) continue;
				if (p[nx][ny] == 1) continue;
				m[visit[nx][ny]] = 1; // 해당 방의 인덱스를 저장
			}
			int cnt = 1;
			for (auto it = m.begin(); it != m.end(); it++) 
				cnt += roomSize[it->first]; // 방의 크기를 cnt에 추가
			cout << cnt % 10; // 10으로 나눈 나머지를 출력한다.
		}
		cout << "\n";
	}
}