• Home
  • About
    • Seokmin.Lee photo

      Seokmin.Lee

      Hello, I am a master's student in the Department of Convergence Security (Samsung Advanced Security) at Korea University.After graduation, I am expected as a security developer or researcher member of Samsung SDS.

    • Learn More
    • LinkedIn
    • Github
  • Posts
    • All Tags

[bj][16234]인구이동

14 Feb 2025

문제:

  • 제목: 인구이동
  • 링크 : https://www.acmicpc.net/problem/16234

해결 방식:

BFS (+로직)

  • 얻어간점
    • 종료조건을 정확히 주자
    • 종료조건 중, 언제 끝나는지에 대한 논리를 정확히하자
    • 종료조건을 통해서 출력되는게 무엇인가에 대한 논리 또한 정확히 하자

CODE

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;

int graph[51][51] = { 0, };
int visited[51][51] = { 0, };

int moved = 0;
int moved_time = 0;

int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };

int N, L, R;

int check = 0;

void people_move() {

	memset(visited, 0, sizeof(visited));
	queue<pair<int,int>> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] == 0) {
				
				vector<pair<int, pair<int,int>>> temp;
				temp.push_back({ graph[i][j], {i,j} });
				visited[i][j] = 1;

				q.push({ i,j });
				
				while (!q.empty()) {
					pair<int, int> cur_step = q.front();
					q.pop();

					for (int i = 0; i < 4; i++) {
						pair<int, int> next_step = { cur_step.first + dr[i], cur_step.second + dc[i] };


						if (next_step.first < 0 || next_step.first >= N || next_step.second < 0 || next_step.second >= N) {
							continue;
						}

						if (visited[next_step.first][next_step.second] != 0) {
							continue;
						}

						if (abs(graph[cur_step.first][cur_step.second] - graph[next_step.first][next_step.second]) < L) {
							continue;
						}

						if (abs(graph[cur_step.first][cur_step.second] - graph[next_step.first][next_step.second]) > R) {
							continue;
						}

						visited[next_step.first][next_step.second] = 1;

						temp.push_back({ graph[next_step.first][next_step.second], next_step });

						q.push(next_step);
					}
				}

				int avg = 0;
				for (int i = 0; i < temp.size(); i++) {
					avg = avg + temp[i].first;
				}
				avg = avg / (temp.size());

				//update
				
				for (int i = 0; i < temp.size(); i++) {
					if (graph[temp[i].second.first][temp[i].second.second] != avg) {
						check = 1;
					}
						
					graph[temp[i].second.first][temp[i].second.second] = avg;
				}

			}
		}
	}
	// 종료조건의 논리를 정확히하자. 언제 끝나는가? : 맵의 업데이트가 없을때
	// 무엇을 출력해야하는가? : 맵의 업데이트가 있다면 있었던 날짜증가
	if (check == 0) {
		cout << moved_time;
		exit(0);
	}
	else {
		moved_time = moved_time + 1;
	}
}

int main() {

	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	freopen("텍스트.txt", "r", stdin);

	cin >> N >> L >> R;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> graph[i][j];
		}
	}
	while (1) {
		people_move();
		check = 0;
	}

	cout << moved;
	exit(0);

}




PSCPPBJ Share Tweet +1