취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27115번 문제인 통신소이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/27115 

주어지는 K개의 통신소 중 적어도 하나와 통신할 수 있는 격자 내의 칸의 개수를 세는 문제이다.

주어진 격자 위에서 각 통신소마다 통신이 가능한 격자를 칠하는 것을 반복하면 답은 구할 수 있겠지만, 문제를 해결하기에 시간복잡도가 충분하지 않다. 대신 전파의 세기 w를 3000부터 1씩 줄여가며 현재 위치가 전파 세기 w의 통신소와 같은 기능을 할 수 있는 칸들을 차례대로 칠해나가는 것으로 문제를 해결하자. 이 때, 각 칸에 접근하는 횟수는 많아야 4회(상하좌우 네 방향; 해당 위치에 다른 통신소를 세우려고 시도하는 경우 제외)임을 관찰하자. 즉, 이와 같은 방법은 문제를 해결하기에 충분한 시간복잡도(O(NM))를 갖는다.

위의 방법은 아래와 같이 BFS와 같은 원리로 구현 가능하다, 

아래는 제출한 소스코드이다.

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

int R, C, K;
int board[3000][3000];
vector<pair<int, pair<int, int>>> vec;
queue<pair<int, int>> que;

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C >> K;
	while (K--) {
		int r, c, w; cin >> r >> c >> w;
		vec.emplace_back(make_pair(w, make_pair(r - 1, c - 1)));
	}

	sort(vec.begin(), vec.end());

	for (int w = 3000; w > 0; w--) {
		while (!vec.empty() && vec.back().first == w) {
			if (!board[vec.back().second.first][vec.back().second.second]) {
				board[vec.back().second.first][vec.back().second.second] = 1;
				que.push(vec.back().second);
			}
			vec.pop_back();
		}
		int qsize = que.size();
		while (qsize--) {
			int r = que.front().first, c = que.front().second; que.pop();
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc]) continue;
				board[rr][cc] = 1;
				que.push(make_pair(rr, cc));
			}
		}
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			ans += board[r][c];
		}
	}

	cout << ans;
}