이코테, 백준 - 16234

문제

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

dfs로 인구 이동이 총 몇 번 일어나는지 구하는 문제였다.

 

문제 풀이

dfs를 이용해 국경선이 열리는 곳을 방문 후 stack에 저장하고 stack의 size가 2 이상이면 총 인구수 / 나라수 를 각 stack에 저장된 나라의 인구수로 갱신하고 갱신이 일어나면 flag를 1로 바꿔 다음 while문이 돌아갈 수 있도록 했다.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <stack>
#include <stdlib.h>

using namespace std;

int N, L, R;
int map[51][51];
int visit[51][51];
int flag;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int sumPeople;
stack<pair<int, int>> s;

void printMap() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void dfs(int x,int y) {
    visit[x][y] = 1;
    s.push({ x,y });
    sumPeople += map[x][y];

    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 < N && visit[nx][ny] == 0) {
            int diff = abs(map[x][y] - map[nx][ny]);
            if (diff >= L && diff <= R) {
                dfs(nx, ny);
            }
        }
    }
}

int main()
{

    int i, j;
    int changeNum;
    int answer = 0;

    scanf("%d %d %d", &N, &L, &R);

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    flag = 1;
    while (flag == 1) {
        flag = 0;
        fill(&visit[0][0], &visit[N][N], 0);
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                if (visit[i][j] != 1) {
                    sumPeople = 0;
                    dfs(i, j);
                    if (s.size() == 1) {
                        s.pop();
                        continue;
                    }
                    else {
                        changeNum = sumPeople / s.size();
                        while (!s.empty()) {
                            map[s.top().first][s.top().second] = changeNum;
                            s.pop();
                            flag = 1;
                        }
                    }
                }
            }
        }
        if (flag == 0) break;
        answer++;
        //printMap();
    }

    printf("%d", answer);

    return 0;
}

/*
2 20 50
50 30
20 40
*/