[백준]인구이동(시간초과..충격)

일단 문제 자체는 매우 쉬운 문제였다. 그냥 bfs를 해주는 문제였고, 조건 하나가 더 달려있는 문제였다.

그리고 갱신을 위해 그냥 각각의 위치마다의 좌표를 자료형에 보관해서 나중에 탐색 후, 업데이트 해주면

되는 문제였는데, 시간초과 발생했고 이유를 도저히 모르겠어서 넘어갔었다. 하지만 이유를 찾아버렸다. 

그 이유는 다음과 같다.

if문 안에 바로 조건을 넣지 않고 bool형 함수로 따로 구현했는데 그것만으로도 시간 초과가 발생했다.....

(이에 대해서는 스택을 참조하고 리턴주소반환하는것등의 시간이 걸린다고 한다.....)

그리고 자료형을 생성 소멸할때 시간이 걸리므로 글로벌로 한번 선언해주고 초기화하면서 사용해주니까

속도가 400ms --> 100ms로 4배나 줄었다.

 

첫번째 코드가 시간초과가 났던 코드고 두번째 코드가 100ms로 성공한 코드이다.

 

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

 

 

 

#include <iostream>
#include <queue>
#include <math.h>
#include<vector>
using namespace std;
 
int N, L, R , MM = 0, answer=0;
queue<pair<int, int> > q1;
int map[51][51];
int dr[] = {-1,1,0,0};
int dc[] = {0,0,-1,1};//상하좌우
 
void Show() {
    cout << "====================================\n";
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) cout << map[i][j] << " ";
        cout << "\n";
    }
}
 
bool InRange(int r, int c) {
    if (r <= 0 || c <= 0 || r > N || c > N) return false;
    else return true;
}
 
bool IsConnect(int a, int b) {//괄호 꼭 쳐줘야함
    if ((L <= abs(a - b)) && (abs(a - b) <= R)) return true;
    else false;
}
 
//1.벡터를 만들어서 탐색좌표를 넣어서 연합정보를 보관한다.
 
void bfs() {
    int U[51][51] = {0};
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {//머리로 떠오른 코딩을 바로 손으로 옮기지 말고 머리로 시뮬레이션 최대한 문제점 찾아내기
            if (U[r][c] != 0) continue; //방문여부
 
            vector<pair<int, int> > v1;-->이거 자체가 시간이 많이 걸린다.
            U[r][c] = 1;
            q1.push(make_pair(r, c)); //탐색시작
            v1.push_back(make_pair(r, c)); //연합정보들
            int howmany = 0;
            int SSum = 0;
 
            while (!q1.empty()) {
                howmany++;
                int next_r = q1.front().first;
                int next_c = q1.front().second;
                q1.pop();
                SSum += map[next_r][next_c];
                
                for (int i = 0; i < 4; i++) {
                    int rr = next_r + dr[i];
                    int cc = next_c + dc[i];
 
 /////문제의 부분 따로 함수화하니까 시간초과 발생//////
                    if (!InRange(rr, cc) || U[rr][cc]==1) continue; //범위검사
                    if (IsConnect(map[next_r][next_c], map[rr][cc])==true) { //인접한 곳이 조건에 맞으면
                        U[rr][cc] = 1;//방문
                        q1.push(make_pair(rr, cc));
                        v1.push_back(make_pair(rr, cc));
                        //cout << next_r << " " << next_c << "-->" << rr << " " << cc << endl;
                    }
                }
            }
            if (howmany >= 2) {
                //연합을 했다는 거임.
                answer++; //연합의 개수
                int human;
                human = int(SSum / howmany);//최종 연합 인구 수.
                for (int i = 0; i < v1.size(); i++) {
                    map[v1[i].first][v1[i].second] = human;
                }
            }
 
 
        }
    }
}
 
int main()
{
    cin >> N >> L >> R;
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) cin >> map[i][j];
 
    //Show();
    while (1) {
        int a = answer;
        bfs();
        if (a == answer) break;
        MM++;
    }
    cout << MM << endl;
    //Show();
 
    return 0;
}
 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int N, L, R;
int A[101][101];
int isV[101][101]; //방문여부
queue<pair<int, int> > q1; 
queue<pair<int, int> > path; //경로저장(글로벌로해야 빠름)
int dr[] = {1,-1,0,0};
int dc[] = {0,0,1,-1};
 
int solve() {
    int answer = 0;
    
    while (1) {
        bool Is = false;
        memset(isV, 0, sizeof(isV));
 
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (isV[r][c] != 0) continue; //방문했으면 pass
                int sum = A[r][c]; //연합의 총 숫자 누적값을 구하기위해
                isV[r][c] = 1; //방문
                q1.push(make_pair(r, c)); //탐색시작
                path.push(make_pair(r, c)); //경로입력
 
                while (!q1.empty()) {
                    int nr = q1.front().first, nc = q1.front().second;
                    q1.pop();
 
                    for (int k = 0; k < 4; k++) {
                        int nnr = nr + dr[k], nnc = nc + dc[k];
                        if (nnr < 1 || nnc < 1 || nnr > N || nnc > N || isV[nnr][nnc]==1) continue; //범위
                        if (L <= abs(A[nr][nc] - A[nnr][nnc]) && abs(A[nr][nc] - A[nnr][nnc]) <= R) {
                            q1.push(make_pair(nnr, nnc));
                            isV[nnr][nnc] = 1;
                            path.push(make_pair(nnr, nnc));
                            sum += A[nnr][nnc]; //누적
                        }
                    }
                }
                if (path.size() == 1) path.pop(); 
                else { //연합이 있을 경우
                    Is = true;
                    int new_human = sum / path.size();
                    while (!path.empty()) {
                        int nr = path.front().first, nc = path.front().second;
                        path.pop();
                        A[nr][nc] = new_human;
                    }
                }
 
            }
        }
        if (Is == false) break;
        answer++;
    }
 
    return answer;
}
 
int main() {
    cin >> N >> L >> R;
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) cin >> A[i][j];
 
    cout << solve() << endl;
    return 0;
}