https://www.acmicpc.net/problem/16946
DFS 연결된 컴포넌트 탐색 문제의 심화버전
시간복잡도 줄이는 문제다.
N * M 행렬이 있을 때 DFS로 탐색을 한다면 행렬의 값 하나당 O(N * M)형태로 탐색을 하게 된다.
근데 그런 행렬의 값이 또 N * M개 있으므로 최종적으로 O(N * N * M * M)형태가 된다.
그럼 해당 문제에선 O(1,000,000,000,000)으로 1조가 되므로 각 값마다 탐색을 할 수 없다.
즉 행렬의 값 하나하나 모두 DFS를 돌리는게 아니라
미리 같은 값을 가진 연결된 컴포넌트들의 크기를 탐색하고 그룹으로 나눈 후 그룹번호와 해당 그룹의 갯수를 구해둔 후 인접한 그룹들의 갯수의 합으로 결과를 내야 한다.
위 그림처럼 0번그룹은 3개, 1번그룹은 3개, 2번그룹은 1개 이런식으로 기록해뒀다가
빨간 원을 그려둔 곳에서 인접한 0의 갯수를 찾는다면
위쪽에서 0번그룹의 갯수인 3을 더해주고, 아랫쪽에서 1번그룹의 갯수인 3을 더해주는 방식으로 진행해야 한다.
정답 코드)
#include<bits/stdc++.h>
using namespace std;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int N, M, group;
vector<vector<int>> arr;
vector<vector<int>> group_arr;
vector<vector<bool>> visited;
vector<pair<int, int>> group_vec;
vector<int> group_count;
void dfs(int y, int x)
{
visited[y][x] = true;
group_vec.push_back({ y, x });
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (arr[ny][nx] == 0 && !visited[ny][nx]) {
dfs(ny, nx);
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> M;
arr.resize(N, vector<int>(M, 0));
group_arr.resize(N, vector<int>(M, -1));
visited.resize(N, vector<bool>(M, false));
for (int i = 0; i < N; i++) { // 입력받고
for (int j = 0; j < M; j++) {
char c;
cin >> c;
arr[i][j] = c - '0';
}
}
for (int i = 0; i < N; i++) { // 0인 그룹 묶기
for (int j = 0; j < M; j++) {
if (arr[i][j] == 0 && !visited[i][j]) {
dfs(i, j);
group_count.push_back(group_vec.size());
for (auto p : group_vec) {
group_arr[p.first][p.second] = group;
}
group_vec.clear();
group++;
}
}
}
vector<vector<int>> result(N, vector<int>(M, 0));
for (int i = 0; i < N; i++) { // 1인 값들 탐색
for (int j = 0; j < M; j++) {
if (arr[i][j] == 1) {
set<int> check_group;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (arr[nx][ny] == 0) {
if (check_group.find(group_arr[nx][ny]) == check_group.end()) {
check_group.insert(group_arr[nx][ny]);
result[i][j] += group_count[group_arr[nx][ny]];
}
}
}
}
result[i][j] += 1; // 본인자리 1 추가
}
}
}
for (int i = 0; i < N; i++) { // 출력
for (int j = 0; j < M; j++) {
cout << result[i][j] % 10;
}
cout << '\n';
}
return 0;
}
※ 참고 문헌