16234_인구이동

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 꽤나 헤맸었던 문제다.. 처음에는 유니온파인드로 풀까 하다가 결국 같은 집합을 만들어도 그들의 합으로 또 해당그룹의 수를 바꾸려면 두번 일해야한다는걸 깨닫고 그냥 bfs를 사용해서 그때그때 집합을 만들어 구현하였다. 시간초과나 메모리초과때문에 엄청 고생했는데 bfs를 맵에서 검사할때 한바퀴돌때 이미 집합에 넣어서 검사할 필요가 없는부분은 bfs를 검사하면 안되었었고, 특히 bfs안에..