백준 16946. 벽 부수고 이동하기 4

게시 2024/10/11

https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/images/boj-og.png

By Dukgukim

알고리즘 중급 문제 중 611 - BFS(연습)

벽 부수고 이동하기 4

1. 간단 설명

벽 부수고 이동하기 시리즈

근데 약간 문제 성격이 다르다

기존 문제들이 벽 부수고 최단거리를 구하는 문제였다면

이번 문제는 방의 크기를 체크하는 문제

2. 예시

예제1)

이 주어지면

첫번째 {0,0}의 벽을 부수어본다

001
010
101

이렇게 되는데, 0,0을 부쉈을 때 해당 위치에서 이동할 수 있는 칸(연결된 방 크기)은

{0,0}, {0,1}, {1,0} 총 3칸이다

다음으로 0,1은 이미 빈칸이므로 0을 출력하고

{0,2}의 벽을 부숴보면

100
010
101

이렇게 되므로, {0,1}, {0,2}, {1,2}에 도달할 수 있으므로 3칸이다

이런식으로 쭉 하면

303
050
303

가 출력된다

예제 2)

인 경우, 첫번째 {0,0}만 보면

이므로, {0,0}과 이어진 칸은 모두 4칸이므로 4이다

이런식으로 구하는 문제

3. 알고리즘

시간제한 2초, 메모리 크기 제한 512MB

연결된 섬을 구하는 문제와 매우 유사하다

그런데, 모든 벽에 대해서 이를 수행해야하는데 시간,공간복잡도가 괜찮을까?

1. N, M 입력받고 map 정보를 입력받는다
2. 2중 for문을 돌려서 각 셀이 벽일때(즉, 1일때)
	2-1. 벽을 0으로 만들고 BFS를 수행한다
	2-2. BFS를 통해 해당 셀과 연결된 0을 모두 찾아 리턴한다
	2-3. 백업해둔 맵 정보를 다시 복원한다

벽을 하나씩 부수고 BFS를 수행하는 방법은 너무 비효율적인것 같다

각 벽에 대해 BFS를 수행하는 경우 최대 1000 * 1000 번의 BFS를 호출해야할 수 있으므로, 시간초과 가능성이 높음

다른 방식을 고려해야한다

크게 두 부분으로 나눌 수 있는데

0인 영역의 크기를 미리 구하는 파트
- 0인 구역들을 미리 BFS로 탐색해서, 각 구역에 번호와 연결된 0의 크기를 저장해둔다
- 이렇게 해두면, 인접한 벽을 부술 때, 그 벽에 인접한 0의 크기를 빠르게 구할 수 있음
해당 벽을 부쉈을 때, 그2. 벽 주면의 0 영역 크기 합산
- 각 벽에 대해서, 그 벽에 인접한 서로 다른 0의 구역의 크기를 모두 더한 후, 이를 10으로 나눈 나머지를 계산
- 서로 다른 구역만 더하기 위해서, 각 벽에 대해 인접한 구역 번호를 중복없이 관리룹이 몇개 있는지 체크하는 파트

로 나눌 수 있다

1. N, M을 입력받고 map 정보 입력받기
	1-1. 초기화를 진행하면서 group을 모두 -1로 초기화한다(0번부터 시작하기 위해)
2. BFS를 돌려서 map에 대해서 구역이 몇개 있는지, 그 크기는 몇인지 체크한다
3. 그룹화가 모두 끝났다면, 2중 for문을 돌면서 벽을 하나씩 부숴본다
	3-1. 해당 벽을 부쉈을 때, 이 벽과 연결된 그룹이 있는지 체크한다
	3-2. 만약 그룹이 있다면 이 그룹을 추가한다
	3-3. 4방향 탐색이 끝났다면 기록된 그룹의 크기를 전체 크기에 추가한다
4. 기록된 내용을 출력한다 

필요 변수

행렬 크기 int N, M (1 ≤ N, M ≤ 1000)
맵 배열 int map[1001][1001] -> 약 4MB
그룹 번호를 저장할 배열 int group[1001][1001]
결과를 기록할 배열 int result[1001][1001]
그룹의 번호와 크기를 기록할 벡터 vector<int> group_size
4방향 체크를 위한 int direct[4][2]
해당 벽과 연결된 그룹을 체크하기 위한 set<int> adj_group
- 벡터를 사용해도 가능하지만, 중복체크가 필요하므로 중복원소 입력 방지를 위한 set을 사용

4. 소스코드

  
#include <iostream>
#include <vector>
#include <queue>
#include <set>

#define MAX 1001

using namespace std;

int N, M;
int map[MAX][MAX];
int group[MAX][MAX];
int result[MAX][MAX];
vector<int> group_size; // 그룹 번호와 크기를 저장하는 벡터
int direct[4][2] = { 0,1,1,0, 0,-1,-1,0 };

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M;
	
	for (int y = 0; y < N; y++) {
		string input; cin >> input;
		for (int x = 0; x < M; x++) {
			map[y][x] = input[x] - '0';
			group[y][x] = -1; // 그룹 번호는 -1로 초기화 
		}
	}

}

// 빈칸의 개수 그룹화하고, 크기를 리턴하는 함수
int BFS(int y, int x, int group_num) {
	queue < pair<int, int> > qu;
	qu.push({ y, x });
	group[y][x] = group_num; // 해당 좌표에 해당 그룹 번호를 기록한다

	int size = 1;

	while (!qu.empty()) {
		pair<int, int> now = qu.front();
		qu.pop();

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.first;
			int dx = direct[t][1] + now.second;
		
			if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue; // 맵 벗어남
			if (map[dy][dx] == 1) continue; // 벽인 경우
			if (group[dy][dx] != -1) continue; // 이미 그룹화됨

			group[dy][dx] = group_num; // 해당 그룹번호 저장
			size++;
			qu.push({ dy, dx });
		}
	}

	return size;
}

int main() {
	Input();

	// 1. 그룹화 및 크기 계산
	int group_num = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			// 빈 땅이고, 그룹이 없는 곳의 그룹화 및 크기 계산
			if (map[y][x] == 0 && group[y][x] == -1) {
				group_size.insert( 
					group_size.begin() + group_num, 
					BFS(y, x, group_num)
				); // 그룹 번호와 크기를 넣음
				group_num++;
			}
		}
	}

	// 2. 해당 벽을 부쉈을 때, 땅의 크기 구하기
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			// 벽인경우
			if (map[y][x] == 1) {
				set<int> adj_group; // 중복원소 추가 방지를 위해 set 사용
				int total_size = 1; // 해당 벽을 부순다

				// 이 벽과 연결된 그룹이 있는지 체크
				for (int t = 0; t < 4; t++) {
					int dy = direct[t][0] + y;
					int dx = direct[t][1] + x;

					if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue;
					if (map[dy][dx] == 1) continue;

					adj_group.insert(group[dy][dx]); // 그룹을 추가한다
				}

				for (int e : adj_group) {
					total_size += group_size[e]; // 해당 그룹의 원소 개수만큼 추가함
				}

				result[y][x] = total_size % 10;
			}
		}
	}

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cout << result[y][x];
		}
		cout << '\n';
	}

	return 0;
}

이미 알고있었던 연결된 섬을 구하는 문제에

벽을 부수고 크기를 구하는 파트가 추가된 문제였다

추가된 부분을 어떻게 구현해야할지 감이 안와서 해멨다

특히 set을 이용해서 그룹 중복 추가를 방지하는 부분과

포스팅에 쓰지는 않았지만 다른 풀이를 참고하면서

int map[1001][1001]과 같이 사용하는 방법 대신,

map.resize(N, vector<int>(M)); group.resize(N, vector<int>(M, -1));과 같이

2중 벡터를 이용한 맵 관리나

auto [now_y, now_x] = qu.front() 과 같이

구조적 바인딩(structured bindings)을 사용하는 방법도 배울 수 있었다

Algorithm, Problem Solving