Notice
Recent Posts
Recent Comments
Link
HwangHub
[자바/유니온파인드] 백준 17471. 게리맨더링 본문
문제
해석
이 문제는 조합과 그래프 탐색을 조합하여 푸는게 일반적인 방식이다.
하지만 유니온파인드로 풀어보라고 제안을 받아서 이를 이용하여 "부분집합 + 유니온파인드"로 풀었다.
정점의 개수가 N, 간선의 개수가 E라고 할 때, 유니온파인드 시간복잡도가 O(E * log N)이고, 부분집합의 시간복잡도가 선택하냐 마냐이므로 O(2^N)이다. 따라서 내가 구성한 로직은 O(2^N * E) 인데, 10! 이 약 4백만이고, N이 10까지이므로 1초 내로 구성할 수 있을 것으로 판단했다.
풀이
코드가 길고 지저분해서, 만약 코드를 보고자 하는 분은 흐름을 먼저 체크해주시길 바란다.
/*
* 1. 부분집합을 구한다.
*
* 2. 구해진 부분집합을 기준으로 선거구로 가능한지 체크한다.
* -> adj 리스트를 순회하면서 각 노드별로 연결된 노드 체크
* -> 연결되어 있는 노드가 같이 선택된 경우 union 진행
*
* 3. 선택되지 않은 노드를 기준으로 선거구로 가능한지 체크한다.
* -> 각 노드별로 adj 리스트를 순회하면서 연결된 노드 체크
* -> 연결되어 있는 노드가 존재하면 union 진행
*
* 4. 선거구가 둘다 가능한 경우에는 : 인구수 차이 구해서 ans 갱신
* */위 로직을 바탕으로 구성하고자 했고, 인접리스트를 바탕으로 선택된 선거구 중 인접리스트 상에서 연결된 것들만 union 해주면 선거구 구성 가능 여부를 판단할 수 있을 것으로 보았다.
선거구 가능 여부를 판단하는 로직은 각 노드별로 체크하여 같은 선거구로 묶이는 노드들이 모두 동일한 root 노드를 바라보고 있는지 아닌지로 체크했다.
public class Main {
/*
* 실행 시간 : 144 ms
*
* 메모리 : 15144 KB
* */
static int[] parent;
static int[] citizens;
static int N; // 정점 개수
static List<Integer>[] adj;
static int ans = (int) 1e9;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
/* 시민 수 입력 */
citizens = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
citizens[i] = Integer.parseInt(st.nextToken());
}
/* adj list 입력부 */
adj = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
adj[i] = new ArrayList<>();
st = new StringTokenizer(br.readLine());
int ea = Integer.parseInt(st.nextToken());
for (int j = 0; j < ea; j++) {
adj[i].add(Integer.parseInt(st.nextToken()));
}
}
ps(1, 0); // 1번부터 고르냐 마냐 go
System.out.println(ans == (int) 1e9 ? -1 : ans);
}
private static void ps(int depth, int visited) {
if (depth == N + 1) {
/* tree 연결관계 initialize */
parent = new int[N + 1];
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
/* 로직 수행 */
for (int i = 1; i <= N; i++) {
// 해당 노드를 골랐으면
if ((visited & 1 << i) != 0) {
List<Integer> nodes = adj[i];
for (Integer v : nodes) {
// 같이 고른 놈이면
if ((visited & 1 << v) != 0) {
// 이미 인접한 노드들만 union 가능
// 즉, 나중에 find 검사할 때 root 노드가 다른 경우에는 선거구 불가 판단 가능
union(i, v);
}
}
}
// 해당 노드를 "NOT" 골랐으면
else if ((visited & 1 << i) == 0) {
List<Integer> nodes = adj[i];
for (Integer v : nodes) {
// 같이 "NOT" 고른 놈이면
if ((visited & 1 << v) == 0) {
// 이미 인접한 노드들만 union 가능
// 즉, 나중에 find 검사할 때 root 노드가 다른 경우에는 선거구 불가 판단 가능
union(i, v);
}
}
}
} // end of 선거구 구성
// 선거구 가능여부 체크
boolean aFirst = true;
boolean bFirst = true;
int aRoot = -1;
int bRoot = -1;
for (int i = 1; i <= N; i++) {
if ((visited & 1 << i) != 0) {
if (aFirst) {
aRoot = find(i);
aFirst = false;
continue;
}
if (aRoot != find(i)) {
return;
}
} else if ((visited & 1 << i) == 0) {
if (bFirst) {
bRoot = find(i);
bFirst = false;
continue;
}
if (bRoot != find(i)) {
return;
}
}
}
// 선거구가 가능 -> 인구수 갱신
int aCitizens = 0;
int bCitizens = 0;
for (int i = 1; i <= N; i++) {
if ((visited & 1 << i) != 0) {
aCitizens += citizens[i];
} else {
bCitizens += citizens[i];
}
}
ans = Math.min(ans, Math.abs(aCitizens - bCitizens));
return;
}
ps(depth + 1, visited | 1 << depth);
ps(depth + 1, visited);
}
private static int find(int v) {
if (parent[v] == v) {
return v;
}
return parent[v] = find(parent[v]);
}
private static void union(int u, int v) {
int uRoot = find(u);
int vRoot = find(v);
if (uRoot == vRoot) {
return;
}
if (uRoot < vRoot) {
parent[vRoot] = uRoot;
} else {
parent[uRoot] = vRoot;
}
}
}친구 또한 유니온파인드를 적용하였는데, 유효한 선거구 구성인지 아닌지를 해시셋을 이용하여 판단하였다고 한다. 아이디어를 바탕으로 내 코드에 녹여서 작성해봤는데, 차이점은 "선거구 가능여부 체크" 부분부터만 보면 된다.
핵심은, 친구는 나처럼 root 노드의 일치 여부를 비교하지 않고, 전체 노드의 parent 배열 값을 해시셋에 넣어서 개수를 체크하였다고 한다. 만약 2개가 아니라면 선거구 구성이 불가능하다 판단하여 return을 해줬다고 했다. 꽤나 명료하고 깔끔한 풀이었다. 실행 시간은 동일하고, 메모리는 당연히 해시셋을 추가로 사용하니 조금 더 사용하는 코드이지만, 코드 길이가 훨씬 짧기 때문에 이를 잘 떠올렸다면 더 좋은 풀이를 구성한 것이라 할 수 있을 것 같다.
public class Main {
/*
* 실행 시간 : 144 ms
*
* 메모리 : 16132 KB
* */
static int[] parent;
static int[] citizens;
static int N; // 정점 개수
static List<Integer>[] adj;
static int ans = (int) 1e9;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
/* 시민 수 입력 */
citizens = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
citizens[i] = Integer.parseInt(st.nextToken());
}
/* adj list 입력부 */
adj = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
adj[i] = new ArrayList<>();
st = new StringTokenizer(br.readLine());
int ea = Integer.parseInt(st.nextToken());
for (int j = 0; j < ea; j++) {
adj[i].add(Integer.parseInt(st.nextToken()));
}
}
ps(1, 0); // 1번부터 고르냐 마냐 go
System.out.println(ans == (int) 1e9 ? -1 : ans);
}
private static void ps(int depth, int visited) {
if (depth == N + 1) {
/* tree 연결관계 initialize */
parent = new int[N + 1];
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
/* 로직 수행 */
for (int i = 1; i <= N; i++) {
// 해당 노드를 골랐으면
if ((visited & 1 << i) != 0) {
List<Integer> nodes = adj[i];
for (Integer v : nodes) {
// 같이 고른 놈이면
if ((visited & 1 << v) != 0) {
// 이미 인접한 노드들만 union 가능
// 즉, 나중에 find 검사할 때 root 노드가 다른 경우에는 선거구 불가 판단 가능
union(i, v);
}
}
}
// 해당 노드를 "NOT" 골랐으면
else if ((visited & 1 << i) == 0) {
List<Integer> nodes = adj[i];
for (Integer v : nodes) {
// 같이 "NOT" 고른 놈이면
if ((visited & 1 << v) == 0) {
// 이미 인접한 노드들만 union 가능
// 즉, 나중에 find 검사할 때 root 노드가 다른 경우에는 선거구 불가 판단 가능
union(i, v);
}
}
}
} // end of 선거구 구성
// 선거구 가능여부 체크
HashSet<Integer> hs = new HashSet<>();
for (int i = 1; i <= N; i++) {
hs.add(find(i));
}
if (hs.size() != 2) {
return;
}
int aCitizens = 0;
int bCitizens = 0;
for (int i = 1; i <= N; i++) {
if ((visited & 1 << i) != 0) {
aCitizens += citizens[i];
} else {
bCitizens += citizens[i];
}
}
ans = Math.min(ans, Math.abs(aCitizens - bCitizens));
return;
}
ps(depth + 1, visited | 1 << depth);
ps(depth + 1, visited);
}
private static int find(int v) {
if (parent[v] == v) {
return v;
}
return parent[v] = find(parent[v]);
}
private static void union(int u, int v) {
int uRoot = find(u);
int vRoot = find(v);
if (uRoot == vRoot) {
return;
}
if (uRoot < vRoot) {
parent[vRoot] = uRoot;
} else {
parent[uRoot] = vRoot;
}
}
}
'workspace > 알고리즘' 카테고리의 다른 글
| [자바/Simulation] 백준 23796. 2,147,483,648 게임 (1) | 2024.03.05 |
|---|---|
| [자바/Parametric-Search] 백준 2110. 공유기 설치 (1) | 2024.02.25 |
| [자바/분할정복] 백준 1992. 쿼드트리 (0) | 2024.02.15 |
| [자바/그리디] 코드트리. 최대 숫자 만들기 (0) | 2024.02.13 |
| [자바/그리디] 코드트리. 회의실 준비 구현 (1) | 2024.02.13 |
Comments