[C++] 백준 16234번 인구 이동

구현 / 시뮬레이션 / 그래프 탐색 - 너비 우선 탐색 문제.

인구 이동이 같은 날에 동시에 일어날 수 있다는 것을 생각하고 풀어야 한다.

위 부분을 생각하지 못해서 게시판을 참고하면서 왜 테스트 케이스가 다르게 나오는지 확인했던 문제였다.

 

문제풀이

N x N 크기의 땅이 있을 때, 인접한 두 땅의 인구 수 차이가 L이상, R이하라면 연합을 한다.

그리고 연합 땅들의 인구 수를 (연합의 총 인구수 / 연합의 칸의 개수)로 만든다.

 

사실 BFS로 풀면 어려운 조건은 없다. 그러나 유의해야 할 점이 있다.

위에서 말한 것 처럼, 우리는 인구 이동의 수가 아닌, 며칠동안 인구 이동이 지속되냐 이다.

따라서 같은 날에 인구 이동이 2번, 3번, 4번, ... 이렇게 발생해도 결국 우리는 며칠동안 지속되는지만

확인해주면 되는 것이다.

 

날마다 다음과 같은 조건들을 구하면 된다.

1. 만일, bfs를 돌면서 연합이 될 땅이 하나도 없다면 다음 번에는 BFS를 진행하지 않는다.
2. bfs를 돌면서 연합이 될 땅을 찾았다면 해당 연합들의 땅의 인구 수를 바꿔준다.
3. 정답을 저장하는 변수에 해당 날을 저장해둔다.

위 과정들을 반복하면 된다. 코드를 살펴보자.

사용한 STL과 변수

연합의 좌표를 저장하는 unionPoint를 vector로 쓰기위해 vector STL을 사용했다.

visit 배열을 초기화하기 위한 cstring STL을 사용했다.

BFS를 하기 위해 queue STL, 각 땅의 인구 수 차이를 절대값으로 구하는 abs() 메서드를 사용하기 위해 math.h STL을 사용했다.

• widthHeight : 땅의 높이와 너비
• minDiff : 최소 차이
• maxDiff : 최대 차이
• map 배열 : 땅에서 각 칸의 정보를 저장하는 배열
• visit 배열 : 각 날마다 해당 땅을 방문했는지 저장하는 배열, 날마다 bfs 시작 전에 false로 초기화 해주어야 한다.
• unionPopulationSum : bfs를 돌면서 얻은 현재 연합의 인구수의 합
• unionPopulationNum : bfs를 돌면서 얻은 현재 연합에서 땅의 수
• unionPoint 벡터 : bfs를 돌면서 구한 연합에 속한 땅의 좌표들을 저장하는 벡터
• direction 배열 : 상, 우, 하, 좌 방향으로 bfs를 쉽게 돌기위한 배열. 각 값을 더해주면 된다.
• ans : 출력할 정답

메인함수

처음에 높이, 너비 / 최소차이 / 최대차이를 입력받는다.

그리고 땅의 각 칸의 정보들을 입력받는다.

 

그리고나서, find는 이번 날에 연합을 찾았는지에 대한 변수이고, day는 몇일째인지를 나타내는 변수이다.

날마다 새로운 연합을 찾아야 하므로 visit 배열을 false로 모두 초기화 해준다.

그리고 연합을 찾는동안 반복문을 통해 bfs를 계속 진행해준다.

해당 땅을 방문하지 않았다면 해당 땅에서 bfs를 진행한다.

그리고 해당 땅에서 시작해서 bfs를 시작했을 때 연합 땅의 수가 1보다 크다면, 즉 연합이 존재한다면

ans 변수에 현재 day의 값을 대입해준 후에 find를 true로 바꾸고

populationMove()라는 인구이동을 시켜주는 메서드를 통해 인구를 이동시켜준다.

 

그리고 연합을 찾지 못하는 날까지 반복문을 돌다가 반복문이 끝나면 ans, 몇일까지 진행되는지를 출력한다.

 

BFS 메서드

BFS를 시작할 때, 이전에 저장했던 연합의 인구수와 연합에서 칸의 수를 0으로 초기화한다.

그리고 좌표를 저장하는 큐 q를 만들어놓고 시작좌표를 넣은 후에 시작 좌표를 방문처리한다.

큐가 비지 않을때까지 반복문을 돈다. 

현재 좌표를 curY, curX 좌표에 저장하고 현재 칸의 인구 수를 curPopulation 변수에 저장한다.

그리고 연합의 땅의 수 unionPopulationNum에 1을 더하고 unionPopulationSum에 현재 인구 수를 더해준다.

unionPoint 벡터에 현재 좌표를 저장해준다.

 

그리고 위에서 명시했던 대로, 4가지 방향에 대해서 고려해준다.

• 1 <= Y <= widthHeight / 1 <= X <= widthHeight / (Y, X)는 방문하지 않은 곳

이라면, 해당 칸의 인구 수와 현재 칸의 인구 수의 차이를 절대값으로 diff 변수에 저장해놓는다.

• minDiff <= diff <= maxDiff

라면 해당 지점을 방문처리한 후에 큐에 해당 지점의 좌표를 집어넣는다.

 

인구이동 메서드

저장된 연합들의 인구이동 메서드이다.

연합에 저장된 좌표들(땅)의 인구 수를 (총 연합의 인구 수 / 연합의 땅의 수)로 바꿔준다.

후에 인구 이동이 완료되면 연합의 좌표를 저장하는 벡터를 초기화한다.

 

위 풀이대로 풀면 360~384ms 내로 풀리는 것 같았다.

채점 현황에 가보면 시간이 100ms, 60ms로 푼 풀이도 많은 것 같았다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.