문제풀이3_BFS) 인구이동

Intro

코딩테스트 대비 두번째 기출문제 풀이이다.

bfs 를 이용한 방식인데, queue로 구현했다.

문제 설명은 역시 백준 사이트 링크를 첨부한다.

https://www.acmicpc.net/problem/16234

Conclusion

1. 처음에 전체 배열을 탐색하면서 군집을 나눈다.

 1-1. 배열의 현재 칸, 2차원 배열이므로 i,j번 방을 노드로 삼아 bfs를 구현한다.

 1-2. 현재 노드를 기준으로 조건을 만족한다면 같은 군집으로 설정하는 방식.

2. 군집을 나눴다면 각 군집별로 인구수 합과 군집에 속하는 나라의 갯수? 를 구한다.

3. 이후 배열을 update!

4. 군집에 속하는 나라가 한개뿐이라면 값이 update되지 않으므로, update가 되지 않을 때까지 계속 반복한다.

위와같은 순서로 구현을 했는데, 메모리 초과 에러가 나서 새벽 내내 한참을 고민했지만 풀지못하고,,,,

아침에 일어나서 커피한잔하며 다시풀이!

위 순서 중 1번 2번을 동시에 진행하는것으로 바꿨더니 문제를 해결할 수 있었다....

즉, 군집을 나누면서 동시에 값도 누적하도록 하는 것.

시간초과도 아니고, 메모리초과는 해결법을 찾기 힘든 것같다..

Code

코드를 첨부한다.

코드에 탭이너무 큰데(?),, 수정방법을 모르겠다,,

Solution

얻은 교훈은 고쳐도 안풀리면 붙들고있지말고 깔끔하게 다시풀자!