백준 16234번 인구 이동

문제 링크입니다: https://www.acmicpc.net/problem/16234

재미있는 DFS(Depth First Search) 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. 그래프를 입력받고 국경을 열 수 없을 때까지 while문을 돌립니다.

2. while문을 한번 돌릴 때마다 visited 배열을 초기화시키고 결과를 1 증가시킵니다.

3. 모든 칸을 순회하며 방문하지 않은 칸을 기준으로 벡터 v에 좌표를 추가하고 DFS 함수를 호출합니다.

4. DFS 함수는 다음 칸이 범위 내에 있고 아직 방문하지 않았으며 현재칸과 다음칸의 차이가 L 이상 R 이하일 경우에만 재귀 호출을 하며 국경을 엽니다.

5. 4번에서 국경을 열 때 벡터 v에 다음칸 좌표를 넣어주고 국가의 수도 늘어났기 때문에 num도 1 증가시켜줍니다.

6. 4번의 과정이 다 끝난 뒤에는 모든 칸마다 순회하며 인구를 (연합군의 수)/(국가의 수)로 바꿔줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 50;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int N, L, R;

int people, num;

int graph[MAX][MAX];

bool visited[MAX][MAX];

vector<pair<int, int>> v;

 

void DFS(int y, int x)

{

        for (int i = 0; i < 4; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 int diff = abs(graph[y][x] - graph[nextY][nextX]);

                 if(0 <= nextY && nextY < N && 0 <= nextX && nextX < N)

                         if (L <= diff && diff <= R && !visited[nextY][nextX])

                         {

                                 //조건 충족할 경우에만

                                 visited[nextY][nextX] = true;

                                 v.push_back({ nextY, nextX });

                                 people += graph[nextY][nextX];

                                 num++;

                                 DFS(nextY, nextX);

                         }

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> L >> R;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         cin >> graph[i][j];

 

        int result = 0;

        while (1)

        {

                 memset(visited, false, sizeof(visited));

 

                 bool found = false;

                 for(int i=0; i<N; i++)

                         for (int j = 0; j < N; j++)

                         {

                                 if (visited[i][j])

                                          continue;

 

                                 visited[i][j] = true;

                                 people = graph[i][j];

                                 num = 1;

 

                                 v.clear();

                                 v.push_back({ i, j });

                                 DFS(i, j);

 

                                 //국경이 하나라도 열리면

                                 if (num >= 2)

                                 {

                                          found = true;

                                          //업데이트

                                          for (int i = 0; i < v.size(); i++)

                                                  graph[v[i].first][v[i].second] = people / num;

                                 }

                         }

 

                 if (found)

                         result++;

                 else

                         break;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~