16946(bfs 응용)

첫인상

입력값이 최대 1000000이므로 nlogn 시간 안에 끝을 봐야 했다 그래서 1을 기준으로 탐색을 돌리면 무조건 시간 초과가 나올 것 같아서 0을 기준으로 탐색을 돌리는게 유리할 것 같다고 생각을 정리하고 시작했다

풀이

인접해 있는 0들을 bfs를 통해서 그룹으로 묶었고 cnt 배열에 각 그룹별로 몇개의 0이 인접해 있는 지 저장해 두었다. 그 후 전체를 탐색하면서 1을 발견하면 주위의 0 그룹의 cnt를 더해주는 방식으로 진행했다.

문제상황

우선 1의 상하좌우에 위치한 0그룹이 같은 그룹일 수 있었다. 이를 해결하기 위해 인접한 그룹을 pq에 넣어서 겹치는 그룹을 제거해주어서 해결했다.
또한 시간초과 날 부분이 없는데 시간초과가 나서 의아했는 데 bfs를 돌릴 때 visit 여부를 체크해주는 타이밍에 따라 queue에 쓸데 없는 값들이 매우 많이 들어갔다. 이를 해결해 주기 위해서 visit을 체크해주는 타이밍을 고치던가 조건문을 하나 추가해서 visit 했을 때 곧 바로 나가는 식으로 해결할 수 있을 것 같다.

코드

#include<iostream>
#include<vector>
#include<queue>
#define pii pair<int,int>
using namespace std;

int n, m;
int map[1005][1005];
int visit[1005][1005];
vector<int> cnt;

void input() {
	cin >> n >> m;

	string str;

	for (int i = 0; i < n; i++) {
		cin >> str;

		for (int j = 0; j < m; j++) {
			map[i][j] = str[j] - '0';
			visit[i][j] = -1;
		}
	}
}

int idx = 0;
void bfs(int x, int y) {
	queue<pii> q;
	int dx[4] = { 0,0,-1,1 };
	int dy[4] = { -1,1,0,0 };
	cnt.push_back(0);

	q.push({ x, y });
	visit[x][y] = idx;
	cnt[idx] += 1;

	while (!q.empty()) {
		x = q.front().first;
		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 < 0 || nx >= n || ny < 0 || ny >= m) {
				continue;
			}

			if (map[nx][ny] == 0 && visit[nx][ny] == -1) {
				q.push({ nx,ny });
				visit[nx][ny] = idx;
				cnt[idx] += 1;
			}
		}
	}
	idx += 1;
}

void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0 && visit[i][j] == -1) {
				bfs(i, j);
			}
		}
	}

	priority_queue<int> pq;
	int dx[4] = { -1,1,0,0 };
	int dy[4] = { 0,0,-1,1 };

	int ins = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0) {
				cout << 0;
			}
			else {
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];

					if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
						continue;
					}

					if (visit[nx][ny] != -1) {
						pq.push(visit[nx][ny]);
					}
				}

				int pre = -1;
				while (!pq.empty()) {
					if (pre == pq.top()) {
						pq.pop();
					}
					else {
						pre = pq.top();
						pq.pop();
						ins += cnt[pre];
					}
				}
				cout << (ins + 1) % 10;
				ins = 0;
			}
		}
		cout << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	input();
	solve();
}