[ 백준 27115 ] 통신소 : C++ 풀이

https://boj.kr/27115 

27115번: 통신소

 

0. 서론

 

킹받는 asdarwin03님이 만든문제

 

BFS 문제였는데, 사실 BFS 하는 과정 자체에 집중하면 안됐었다.

BFS의 과정을 자세히 보면 큐에 넣는 과정이 있는데, 이 큐에 무엇을 넣을지에 대한 생각을 좀 하지 못했던 것 같다.

 

큐에 넣는 과정을 조금만 비틀어도 복잡한 문제를 간단히 할 수 있음을 알 게 됐는데, 이는 우선순위 큐를 활용하는 방법에 대해 내가 생각하지 못했던 과정과 비슷했어서 좀 많이 상심했던 기억이 난다.

 

어쨋건, BFS를 좀 더 깊게 파보면 이렇게 어렵게 문제를 낼 수 있구나 하고 감탄했던 기억이 난다.

 

1. 일단 직설적으로 접근했다.

 

사실 타일을 채우는 모든 곳을 BFS 하면 가장 쉽게 풀  수 있다. BFS를 돌리고 특정 위치를 방문했는지 확인하는 배열을 그냥 두면 된다.

 

통신소가 모든 타일을 채울만큼 강하면서, 통신소가 최대 개수만큼 빽빽하게 들어선 예제가 있다고 생각해보면 시간복잡도가 어마무시하다는 것을 알 것이다. 즉, 이렇게 풀면 틀린다!

 

2. 좀 더 효율적인 방법을 생각했다.

BFS를 진행하는데 만약 해당 자리에 더 강한 전파가 있다고 치면 어떻게 될까? 그렇다면 더 강한 전파로 인해 있으나 마나 한 꼴이 된다, 즉 무시해도 좋다는 거다.

 

그 방법을 이용해서 만약 내가 현재 bfs할 자리가 신호가 더 크다면 bfs를 무시하게 만들었다.

 

다만 이렇게 되면 문제가 있었다. 약한 신호부터 채우게 된다면 결국 위 풀이와 다를게 없어진다. 사실 이를 정렬해서 가장 센 신호부터 처리하는 것이 에디토리얼의 풀이법과 유사하다. 하지만 아래 언급되는 발상이 부족해서 실현에 옮기진 못했다. 그래서 나는 방문 배열을 만들어서 만약 겹치게 된다면 방문 배열에 이미 방문되어있는지를 체킹하는 식으로 풀어보려고 했는데... 헛수고였다. 사실 의미가 없었다.

 

게다가 주어진 통신소들을 BFS하게 된다면 효율적인 부분을 생각하면 할 수록 문제 풀이가 더 복잡해졌다. 예외가 계속 생기고 그걸 메꾸려고 테이프를 붙이고... 하다보니 그냥 의미없는 스파게티 코드의 연속이였다. ㅠㅠ PS를 할 때에는 내 풀이가 점점 복잡해지고, 처리해야할 예외가 계속 늘어날수록 이건 맞는 풀이가 아님을 깨달았다. 그래서 이건 아닌거같고... 시간 초과는 계속 나서 그냥 에디토리얼을 보기로 했다.

 

3. 에디토리얼에선 이렇게 얘기했다. (정답을 원하면 여기부터)

만약 같은 타일에 여러개의 전파가 있다(여러 신호를 가진 여러개의 통신소) 더 센 전파가 있다면 어떻게 될까? 그 자리는 가장 센 전파 이외의 나머지 전파들은 없다고 봐도 무방하다.

 

따라서 가장 센 전파부터 맵에 표시하면서 BFS를 하면 그것이 의도된 풀이법이다.

 

하지만 여기서 중요한 점이 있다. 만약, 신호의 세기가 5 , 3 , 3 인 통신소 3개가 입력으로 주어졌다 치면, 이 통신소 3개 5, 3, 3 을 순서대로 bfs하게 된다면, 5가 내뿜는 4방향의 4짜리 타일 4개를 큐에 나중에 넣게 돼서 결국엔 중첩될 수 있는 일이 일어나게 된다.

 

따라서 가장 센 신호부터 채우는 과정은 찐 통신소만을 정렬해서 하는 게 아니라 이 통신소들이 내뿜어서 영향을 미치는 모든 타일, 즉 BFS 큐에 들어가서 체크할 모든 타일 (이하 노드라고 칭하자.) 전체를 가장 센 신호부터 정렬해서 BFS하면 된다. 그렇게된다면, 가장 센 신호부터 모든 타일을 채워나가기 때문에, 같은 타일엔 최소 1번밖에 들르지 않게 된다.

 

그렇다고 매번 BFS 큐를 정렬을 해야하는 건가? 그건 또 아니다. 입력으로 받은 통신소들을 세기가 큰 순으로 정렬하고, 이 통신소들로 인해 채워질 노드들은 BFS 큐에 넣으면서 실행할 건데, 통신소 배열과, 이 BFS 큐 의 프론트, 즉 다음에 큐에 넣을 값 중에 누가 더 큰지 비교해서 넣으면 결국엔 단조증가되어있는 정렬된 수열형태가 되기 때문에 굳이 BFS 큐를 정렬할 필요는 없다.

 

우선순위 큐를 쓰면 되지 않겠냐고 하지만, 통신소의 개수가 30만개가 넘어가고, 이들이 뿜어낼 전파들의 개수가 어마어마하게 커질 것을 생각하면 이렇게 얼핏 생각해도 이렇게 풀면 안됨을 알 수 있다. 정확하게 따지면 우선순위 큐를 사용하게 되면 큐가 모든 타일에 대해 정렬을 해야하기 때문에 시간복잡도가 비약적으로 증가하게 된다.

 

Big - O 노테이션은 에디토리얼에 언급되어있으니 참고하자. 백준에 나와있음.

 

4. 더 효율적인 풀이

 

더 효율적인 풀이로 누적합, 스위핑을 사용하면 된다고 출제자 분께 들었다. 다만 이 방식들은 나한테 아직 이해하긴 이른거 같아서 BFS 풀이만 올려보고, 좀 더 시간이 지나면 위 개념들을 사용한 풀이들을 한번 해볼 예정이다.

 

소스코드

 

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;

typedef pair<int, pair<int, int>> node;

queue<node> q;

bool map[3000][3000];

node v[300001];

int N, M, K;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M >> K;
	
	for (int i = 0; i < K; ++i) {
		int x, y, p;
		cin >> y >> x >> p;
		x--; y--; p++;
		v[i].first = p;
		v[i].second.first = y;
		v[i].second.second = x;
	}
	sort(v, v + K, greater<node>());
	int frontIdx = 0;
	int frontVal = v[frontIdx].first;
	int ans = 0;
	while (!q.empty() || frontIdx < K) {
		node t;
		if (q.empty() || (frontIdx < K && q.front().first <= frontVal)) {
			t = v[frontIdx++];
			if (frontIdx < K) frontVal = v[frontIdx].first;
		}
		else {
			t = q.front();
			q.pop();
		}
		int y = t.second.first, x = t.second.second;
		if (map[y][x]) {
			continue;
		}
		map[y][x] = t.first;
		ans++;
		if (t.first == 1) continue;
		if (y > 0) q.push(make_pair(t.first - 1, make_pair(y - 1, x)));
		if (y < N - 1) q.push(make_pair(t.first - 1, make_pair(y + 1, x)));
		if (x > 0) q.push(make_pair(t.first - 1, make_pair(y, x - 1)));
		if (x < M - 1) q.push(make_pair(t.first - 1, make_pair(y, x + 1)));
	}
	cout << ans;
}