Baekjoon 17471 게리맨더링 JAVA

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

17471번: 게리맨더링

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2017471

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 도시에 대한 인구수가 주어지고 연결 정보가 주어졌을 때

전체 도시를 두 개의 도시로 나누고 인구수의 차가 가장 적은 값을 구하는 문제다.

​

해당 문제는 부분집합, bfs를 이용해서 해결했다.

먼저 데이터를 처리하는 부분에서 연결 정보가 주어질 때

처음 입력값만큼 반복하면서 나머지 값들에 대해서 인접 행렬을 만들어 주었고

​

부분집합을 통해서 list 2개를 만들어 주었다, 이후 둘 중 하나라도 비지 않았으면

(부분집합에서 공집합과, 전체집합을 제외)

이제 각각 그룹들이 자기들끼리 연결되는지 확인하도록 하였고,

체크하는 부분에서 bfs를 이용하였으며, 여기서 체크해야 할 게 해당 부분으로 이동이 가능한지,

이미 방문하지 않았는지, 해당 부분이 다른 그룹에 속한 건 아닌지 체크를 해야 하는데

다른 그룹 속하는 부분을 어떻게 구현할지 애매해서 이야기하던 중

contains을 사용하면 되겠다 생각해서 사용했고,

최종적으로 사이즈와 카운트 값이 같으면 모두 방문 연결되었다는 소리기 때문에

true 값을 넘겨주고 그렇지 않으면 false 값을 넘겨주었다.

​

이제 두 그룹 모두 서로 연결되어 있다면 계산을 진행해서 최솟값을 넣어주는 방식으로 하였고

최종 메인문에서 ans 값이 여전히 max 값이면 -1을 그렇지 않으면 ans를 출력해서 문제를 해결했다.

​

처음에 문제를 풀고 테케만 맞고 틀렸다고 나와서 찾아보니 N 값을 넣어줘야 하는데 아무 생각 없이 숫자 6을

넣어논 곳이 2곳이나 있었고, 앞으로 좀 잘 보면서 해야겠다.