일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
- D4
- 실버1
- 스프링
- 트리의지름
- SW역량평가
- swea
- Spring
- BFS
- 백엔드
- 1251
- Framework
- 알고리즘
- 코딩테스트
- 순열
- Floyd
- 중복순열
- 완전탐색
- 그래프
- 최단경로탐색
- SW역량테스트
- 최단경로
- java
- 최소신장트리
- 백준
- dp
- 골드5
- 골드3
- professional
- BOJ
- backend
- Today
- Total
공부 기록장
[백준-17471] 게리맨더링 본문
이 문제는 백준 골드 5레벨 문제이다.
사실 처음에 이 문제를 봤을때는 어떡해야하나.. 싶었는데 부분집합을 이용해서 A와 B집합에 들어갈 구역을 나눠주고, bfs를 이용해서 그 구역들이 연결되어 있는지 확인해보면 될 것 같았다. 근데 자꾸 인덱스초과가 나길래 도대체 나는 틀린곳이 없는데 왜 그런가.. 답답했었는데, 역시 내가 틀린거였다^^!
부분집합 구하는 부분에서 return값을 잘못줘서 그런 것이었다.
이 코드는 크게 3 부분으로 나눌 수 있는데,
1. 입력받기 (main 문)
2. 부분집합 구하기 (powerset 부분)
3. 연결 되어있는지 확인 (bfs)
입력부터 살펴보자면,
LinkedList를 이용해서 입력을 받아주었다.
Point라는 클래스를 만들어서 그 안에 from, to, pop (나 자신, 연결 된 노드, 인구) 를 받아주고, 배열에 저장해주었다.
입력에서 가장 중요한 부분은, 아무곳에도 연결되지 않은 노드도 혼자서 지역을 가질 수 있기 때문에 자기 자신을 향하는 노드를 하나 추가해 준 것이다.
부분집합 구하기는
다른 부분집합 구하기와 크게 다르지 않다. boolean 배열과 재귀를 이용했다.
마지막으로 내가 원하는 만큼 다 뽑았으면 if문에서 처리를 해주는데, 처음에 이 부분에서 return을 잘못해서 계속해서 오류가 났었다.
이 부분에서 내가 뽑은 배열들을 가지고 bfs를 돌려본다. bfs를 돌려서 연결 된 그래프라면 인구의 총 합이 나오고, 연결되지 않았다면 -1를 리턴해준다.
bfs
이 부분도 지금까지 해왔던 bfs랑 크게 다르지 않다. 조금 다른 점이 있다면, 내가 뭘 뽑았는지 받아주고 뽑은 애들끼리 다 연결되어 있는지 확인해 주는 부분이 조금 다르다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class 게리맨더링_17471 { //백준 골드5
static int N, ans;
static LinkedList<Point>[] list;
static int[] population;
static boolean[] visited;
static boolean[] check;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
ans = 100000;
list = new LinkedList[N+1];
population = new int[N+1];
check = new boolean[N+1];
list[0] = new LinkedList<Point>();
for(int i=1; i<N+1; i++) {
list[i] = new LinkedList<Point>();
population[i] = sc.nextInt(); //노드 별 인구 수 받아주기
}
for(int i=1; i<N+1; i++) {
int n = sc.nextInt(); //연결 된 노드 수
for(int j=0; j<n; j++) {
int to = sc.nextInt(); //연결된 노드
list[i].add(new Point(i,to,population[i]));
}
}
//아무곳에도 연결되지 않은 노드도 혼자서 지역을 가질 수 있기 때문에 추가.
for(int i=1; i<N+1; i++) {
list[i].add(new Point(i,i,population[i]));
}
powerset(0);
if(ans == 100000)
System.out.println("-1");
else
System.out.println(ans);
}
static void powerset(int cnt){
if(cnt == N+1) {
LinkedList<Integer> A = new LinkedList<>();
LinkedList<Integer> B = new LinkedList<>();
for(int i=1; i<cnt; i++) {
if(check[i])
A.add(i);
else
B.add(i);
}
//최소 1개 이상은 들어있어야 함.
if(A.size() == 0 || B.size() == 0 )
return;
int a = bfs(A);
if(a == -1) //만약 A부터 실패라면 B는 고려하지 않아도 됨.
return;
int b = bfs(B);
if(b == -1)
return;
if(Math.abs(a-b) < ans) {
ans = Math.abs(a-b);
// System.out.println(ans);
}
return;
}
check[cnt] = true;
powerset(cnt+1);
check[cnt] = false;
powerset(cnt+1);
}
//검사하기
static int bfs(LinkedList<Integer> l) {
Queue<Point> q = new LinkedList<>();
visited = new boolean[N+1];
visited[l.peek()] = true;
q.addAll(list[l.peek()]); //l에 들어있는 첫 숫자부터 시작.
int cnt = 0;
while (!q.isEmpty()) {
Point p = q.poll();
for(int i : l) {
if(p.to == i && !visited[p.to]) {
visited[p.to] = true;
q.addAll(list[p.to]);
}
}
}
for(int i: l) {
if(!visited[i]) //방문 안한곳이 있다면 연결 X
return -1;
else {
cnt += list[i].peek().pop;
}
}
return cnt;
}
static class Point{
int from, to, pop;
Point(int from, int to, int pop){
this.from = from;
this.to = to;
this.pop = pop;
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준-16985] Maaaaaaaaaze (0) | 2021.04.21 |
---|---|
[백준-16973] 직사각형 탈출 (0) | 2021.04.16 |
[백준-9466] 텀 프로젝트 (0) | 2021.04.12 |
[백준-1167] 트리의 지름 (0) | 2021.04.08 |
[백준-1967] 트리의 지름 (0) | 2021.04.08 |