오랜만에 돌아왔다. 놀고만 있었던 건 절대 아니다.
중간에 코로나 걸려서 2주 정도 고생하긴 했지만 문제는 늘 풀었었다.
벨로그에 게시할 임팩트 있었던 문제가 딱히 없었던 거 같다.
근데 방금 지난 1달 정도간 푼 거 보니까 몇 개 있는 거 같기도 하고... 흠흠....
암튼 오늘 게시할 문제는 인구 이동이라는 그래프 탐색 문제이다.
평소에 백준 시뮬레이션 태그의 문제들이 나한테는 다른 같은 레벨의 문제보다 훨씬 난이도 있게 느껴져서 이를 극복하고자 풀어봤다.
문제링크
https://www.acmicpc.net/problem/16234
설명
인구 이동을 할 수 없을 때까지 계속 해서 맵 전체를 탐색하고 수정해가는 문제이다.
우선 나는 백준의 또다른 그래프 탐색 문제인 단지번호붙이기의 아이디어를 가져와 bfs를 진행할 때마다 visited[y][x]에 기록하는 숫자를 늘려가며 인구를 갱신했다.
ex. (1, 1)에서 탐색할 때는 visited[1][1] = 1로 했다면, (1, 2)를 탐색할 때는 visited[1][2] = 2
방문하지 않은 점을 큐에 넣어 그 주변 점이 인구 이동 조건을 만족하는 점이라면 그 값을 val 에 더하고 cnt의 개수를 늘려나가는 방식으로 bfs를 실행하였다.
큐가 빌 때까지 이를 실행한 후, visited[y][x]의 값이 같은 정점들의 값을 바꾸어주었다.
모든 점에서 bfs를 실행했다면 visited배열을 0으로 초기화하고 다시 처음부터 그래프 탐색을 실행한다.
인구 이동이 일어날 수 없을 때까지 그래프 탐색을 반복해야하므로, movecnt라는 변수를 사용하여 이를 체크하고 탈출할 수 있도록 하였다.
시간제한은 2초고 map의 넓이가 50 * 50밖에 되지 않아서 TLE는 받지 않을 거 같다고 생각했다....
근데 시간복잡도가 정확히 어떻게 되는 지는 모르겠다... 맵을 전체 탐색하는 횟수의 최대가 전체 bfs를 진행했을 때, 2나라씩 인구이동을 한다고 가정하면 2분의 1씩 bfs 횟수가 줄어드는 거니까 log n * n에 맵 전체가 50 * 50이고 4방향으로 탐색하니까... n*2 log n인 거 같은데.... 다른 분들 풀이 찾아봐도 시간복잡도에 대한 언급은 없어서 ㅠㅠ
벨로그를 쓰면서 매번 드는 생각이 이건 진짜 나만 볼라고 쓰는 글 같다는 것이다....
다른 분들꺼 보면 가독성도 좋고 이해도 잘 되는데 나 같아도 내 거 보고는 이해 안 갈 거 같음..... 뭐... 많이 쓰다 보면 나아지겠지...ㅠㅠ
코드
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int n, l, r, ans = 0;
int map[51][51], visited[51][51], dir[4][2] = { {-1, 0},{0, 1},{1, 0},{0, -1} };
struct node {
int y, x;
};
void input()
{
cin >> n >> l >> r;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> map[i][j];
}
void resetvisited()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
visited[i][j] = 0;
}
void solution()
{
while (1)
{
int seq = 1;
int movecnt = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (visited[i][j]) // 이미 처리한 점이라면 넘김
continue;
visited[i][j] = seq;
queue<node> q;
q.push({ i, j });
int val = map[i][j]; // 전체값을 구하기 위해
int cnt = 1; // 개수를 구하기 위해
while (!q.empty())
{
int y = q.front().y;
int x = q.front().x;
q.pop();
for (int k = 0; k < 4; k++)
{
int ny = y + dir[k][0];
int nx = x + dir[k][1];
if (ny <= 0 || ny > n || nx <= 0 || nx > n || visited[ny][nx]) // 범위 벗어났거나 이미 방문했을 시 넘김
continue;
int dif = abs(map[y][x] - map[ny][nx]);
if (dif >= l && dif <= r) // 인구이동 조건을 만족한다면
{
visited[ny][nx] = seq;
q.push({ ny,nx });
val += map[ny][nx]; // 전체값 갱신
cnt++; // 개수 갱신
movecnt = 1; // 인구이동이 발생했음을 기록
}
}
}
if (cnt == 1) // 인구 이동이 없었다면 그냥 넘김
{
seq++;
continue;
}
val /= cnt;
for (int y = 1; y <= n; y++)
{
for (int x = 1; x <= n; x++)
{
if (visited[y][x] == seq)
map[y][x] = val; // 인구 갱신
}
}
seq++;
}
}
if (!movecnt)
break;
ans++; // movecnt가 0이 아니라면 인구이동이 있었다는 뜻이므로 ans 1 증가
resetvisited(); // 방문 기록 초기화
}
cout << ans;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
solution();
return 0;
}