https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
풀이 과정
조건에 맞는 그래프들을 연결하고 연결된 그래프들의 값을 갱신하며 시간을 카운트하는 문제이다. 먼저 조건에 맞는 그래프를 link_map()함수로 연결시켰다. 그리고 모든 노드를 방문하며 dfs()가 실행되었을 경우, dfs()에서 연결 컴포넌트와 요소의 합을 구하고 fill_dfs()를 호출해서 해당 연결 컴포넌트의 값들을 채웠다. 그리고 day_cnt를 더해주며 실행된 날짜를 세며 정답을 구했다.
느낀 점
순탄했던 것은 아니지만 생각보다 순탄했다. 우선 내 설계대로 풀어, 결과적으로 정답을 도출해냈다. 하지만 실수가 있어 디버깅을 하며 찾아냈다. 우선 run()의 while()문이 1회 완료되면 테스트 출력을 해보며 오류를 찾으려 했다. 우선 실행했을 때 정상적으로 바뀌는 경우도 있었지만 일부 경우 4방향 탐색을 수행할 때, 위, 오른쪽을 탐색하고 대각선으로 탐색을 하는 경우가 있었다. 4방향 탐색을 해주는 함수들을 살펴봤지만 이상이 없었고, 4방향 탐색을 위해 만든 my, mx에서 오탈자를 발견했다. ','가 와야할 곳에 '.'이 오게 되어서 오류가 발생했다는 걸 확인했다. 처음에 두어번은 의심하며 봤지만 워낙 비슷하게 생긴 문자들이라 그냥 지나치고 다른 곳에서 시간을 쏟고 말았다. 의심이 간다면 처음 검사할 때 꼼꼼히 하는 습관을 들이자.
#include<bits/stdc++.h>
using namespace std;
const int NMX = 51;
int visited[NMX][NMX], mp[NMX][NMX];
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
int n, bot, top, cnt, sum, day_cnt;
vector<pair<int, int>> adj[NMX][NMX];
// 연결 컴포넌트 개수, 합 연산
bool dfs(int y, int x) {
if (visited[y][x]) return false; //방문하지 않은 그래프만 방문
visited[y][x] = 1; // 첫 방문 처리
sum += mp[y][x]; //연결 컴포넌트 요소 합 구하기
for (int i = 0; i < adj[y][x].size(); i++) {
dfs(adj[y][x][i].first, adj[y][x][i].second); //연결되 그래프로 들어감
}
cnt++; //연결된 그래프 개수를 위한 cnt
return true;
}
//연결 컴포넌트를 floor(합/개수) 으로 채움
void fill_dfs(int y, int x, int sm) {
if (visited[y][x] != 1) return; // visited == 1인 곳만 처리
visited[y][x] += 1; //재방문 처리
mp[y][x] = sm; //값 대입
for (int i = 0; i < adj[y][x].size(); i++) {
fill_dfs(adj[y][x][i].first, adj[y][x][i].second, sm); //연결된 그래프로 들어감
}
return;
}
//visited와 그래프 연결 리스트 초기화
void reset() {
fill(&visited[0][0], &visited[0][0] + NMX * NMX, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
adj[i][j].clear();
}
}
return;
}
//top, bot 값을 기준으로 그래프 연결 리스트 작성
bool link_map() {
int flag = false;
for (int i = 0; i < n; i++) { //모든 노드를 방문하며
for (int j = 0; j < n; j ++) {
for (int k = 0; k < 4; k++) { //노드 4방향 탐색
int ny = my[k] + i;
int nx = mx[k] + j;
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue; //조건에 만족해야 실행
int gap = abs(mp[i][j] - mp[ny][nx]);
if (gap <= top && gap >= bot) { //두 노드가 조건에 만족하면 서로 연결
adj[i][j].push_back({ ny, nx });
adj[ny][nx].push_back({ i, j });
flag = true; //연결된 그래프가 남아 있음을 알림
}
}
}
}
return flag;
}
//입력
void input() {
cin >> n >> bot >> top;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> mp[i][j];
}
}
return;
}
//출력
void output() {
cout << day_cnt;
return;
}
//실행
void run() {
while (link_map()) { // 새롭게 연결된 그래프가 있다면 실행
for (int i = 0; i < n; i++) {//모든 그래프 방문
for (int j = 0; j < n; j++) {
cnt = 0; sum = 0; //그래프 개수와 그래프 요소 합 초기화
if (dfs(i, j)) fill_dfs(i, j, sum / cnt); //dfs()에서 방문 실행되었을때, 요소들을 새롭게 채움
}
}
day_cnt++; //실행된 날짜를 카운트
reset(); //visited와 연결 리스트를 초기화
};
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//입력
input();
//실행
run();
//출력
output();
return 0;
}'알고리즘 : C++ > BaekJoon' 카테고리의 다른 글
| 백준 2852번 - NBA 농구 (0) | 2023.05.28 |
|---|---|
| 백준 10709번 - 기상캐스터 (0) | 2023.05.28 |
| 백준 2589번 - 보물섬 (0) | 2023.05.25 |
| 백준 2870번 - 수학 숙제 (0) | 2023.05.23 |
| 백준 15686번 - 치킨 배달 (0) | 2023.05.23 |