Logo냥냠감자기술 블로그
Skip to Content
작성일: 2024-01-12

문제

백준 16234 - 인구이동 

  • 난이도: 골드5
  • 알고리즘: 그래프탐색, 너비우선탐색, 깊이우선탐색

코드

#include <iostream> #include <vector> #include <cstdlib> using namespace std; const int dx[4]={1, 0, -1, 0}; const int dy[4]={0, -1, 0, 1}; int sideLen, lowerGap, upperGap; int checkToMove(int indexX, int indexY, vector<vector<int>>& map, vector<vector<bool>>& visited, vector<pair<int, int>>& currVisit) { currVisit.push_back({indexX, indexY}); visited[indexY][indexX]=true; int ret=map[indexY][indexX]; for(int i=0; i<4; i++) { int currY=indexY+dy[i]; int currX=indexX+dx[i]; if(currY<0 || currY>sideLen-1 || currX<0 || currX>sideLen-1) continue; if(visited[currY][currX]) continue; int gap=abs(map[indexY][indexX]-map[currY][currX]); if(gap<lowerGap || gap>upperGap) continue; ret+=checkToMove(currX, currY, map, visited, currVisit); } return ret; } void setPeople(int peopleNum, vector<pair<int, int>>& currVisit, vector<vector<int>>& map) { for(int i=0; i<currVisit.size(); i++) { int currX=currVisit[i].first; int currY=currVisit[i].second; map[currY][currX]=peopleNum/currVisit.size(); } } int main() { cin>>sideLen>>lowerGap>>upperGap; vector<vector<int>> map(sideLen, vector<int>(sideLen)); for(int i=0; i<sideLen; i++) { for(int j=0; j<sideLen; j++) { cin>>map[i][j]; } } int ret=0; while(true) { bool noMove=true; vector<vector<bool>> visited(sideLen, vector<bool>(sideLen, false)); for(int i=0; i<sideLen; i++) { for(int j=0; j<sideLen; j++) { vector<pair<int, int>> currVisit; if(visited[i][j]) continue; int peopleNum=checkToMove(j, i, map, visited, currVisit); setPeople(peopleNum, currVisit, map); if(currVisit.size()>1) { noMove=false; } } } if(noMove) break; ret++; } cout<<ret; }

회고

태그에는 너비 우선 탐색이라 되어 있었지만, 나는 깊이 우선 탐색으로 해결했다. 시뮬레이션 느낌으로 직접 수행해 가면서 더 이상 인구 이동이 일어나지 않을 때까지의 숫자를 세는 방식으로 문제를 해결했다. 그래프 문제 오랜만에 푸는데, 얼마 후에 있을 코딩 테스트에서 왠지 그래프 문제가 나올 것 같아 연습 중이다.