Problem 문제풀이
DFS를 잘 사용할 수 있는지 물어보는 문제였다.
전략
-
조건에 맞게
DFS를 하며 도시에 numbering을 한다. -
모든 도시가 국경선을 열지 않았다면 마지막 도시의 number는 N*N - 1일 것이다.
-
numbering의 MAX가 N*N - 1보다 작을 경우 1.을 반복한다.
DFS를 구현하면서 도시의 인구수의 합도 같이 계산하자.
void dfs(int row, int col)
{
visited[row][col] = num_country;
sum[num_country].first += country[row][col];
sum[num_country].second++;
for (int i = 0; i < 4; i++)
{
int nR = row + dirR[i];
int nC = col + dirC[i];
if(nR>=0 && nR<N &&nC>=0 && nC<N)
{
int sub = country[row][col] - country[nR][nC];
if (sub < 0)
{
sub *= -1;
}
if (visited[nR][nC] == -1 && L<=sub && sub<=R)
{
dfs(nR, nC);
}
}
}
}
이제 도시를 DFS하면서 numbering의 MAX를 살펴보자.
국경선을 개방한 곳이 한 군데라도 있을 경우 정답을 1증가시키고 1.을 반복하자.
while (1)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
sum[i*N+j] = { 0,0 };
visited[i][j] = -1;
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (visited[i][j] == -1)
{
dfs(i, j);
num_country++;
}
}
}
if (num_country == N * N)
{
cout << answer;
break;
}
else
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int num = visited[i][j];
country[i][j] = sum[num].first / sum[num].second;
}
}
num_country = 0;
answer++;
}
}
초기화가 이 문제의 핵심이라 생각한다. visited와 sum을 적절히 초기화해주었다면 정답을 받을 수 있을 것이다.
참고로 sum은 누적합을 저장하는 곳으로 그 크기가 N*N까지 가능하다.
TMI)필자의 경우 sum의 사이즈를 N으로 했다가 Run Time Error를…또르륵
실수를 조심하자. 배열의 크기에도 항상 신경쓰자.
전체 코드를 남기며 마무리한다.
#include <iostream>
using namespace std;
int N, L, R, answer;
int num_country;
int country[51][51];
int visited[51][51];
pair<int, int>sum[2501];
int dirR[4] = { 0,1,0,-1 };
int dirC[4] = { 1,0,-1,0 };
void dfs(int row, int col);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> L >> R;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> country[i][j];
}
}
while (1)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
sum[i*N+j] = { 0,0 };
visited[i][j] = -1;
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (visited[i][j] == -1)
{
dfs(i, j);
num_country++;
}
}
}
if (num_country == N * N)
{
cout << answer;
break;
}
else
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int num = visited[i][j];
country[i][j] = sum[num].first / sum[num].second;
}
}
num_country = 0;
answer++;
}
}
return 0;
}
void dfs(int row, int col)
{
visited[row][col] = num_country;
sum[num_country].first += country[row][col];
sum[num_country].second++;
for (int i = 0; i < 4; i++)
{
int nR = row + dirR[i];
int nC = col + dirC[i];
if(nR>=0 && nR<N &&nC>=0 && nC<N)
{
int sub = country[row][col] - country[nR][nC];
if (sub < 0)
{
sub *= -1;
}
if (visited[nR][nC] == -1 && L<=sub && sub<=R)
{
dfs(nR, nC);
}
}
}
}