[문제][알고스팟] EDITORWARS (에디터 전쟁)
2018. 5. 27. 19:23ㆍ[개발] 지식/알고리즘 문제풀이
난이도 '중'이고, Union-Find 문제라는걸 알면서도 헤맸다.
그리고 못풀고 답안을 보며 이해했다. ㅜㅜ
언제쯤 혼자 풀 수 있을까
아래는 삽질한 나의 첫번째 코드이다.
Union-Find를 적용했지만, 상응되는 적대집합과의 쌍 관리를 하지 못했다.
(해야한다는 생각이 들었지만 어떻게 해야할지 감이 안왔다.)
Relation이라는 클래스를 만들어 입력값을 관리했고, 이를 다시 돌면서 Union-Find를 돌렸다.
지금보면 굳이 새로운 클래스를 만들 필요는 없었지만, 당시에는 코딩과 동시에 생각하는 과정이었으므로 그럴 수 있었겠다 싶다.
이 코드에서 해결하지 못한건 위에서 말했듯 적대 집합과의 쌍관리를 하지 못한것이다. 그리고 그로인해 각각의 컴포넌트 별 최대 집합 크기를 구하지 못했다.
내 첫번째 코드
package apss;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
// 알고스팟
// ID : EDITORWARS
// 알고리즘 : Union-Find
// 난이도 : 중
// 상태 : 푸는중
public class EditorWars {
public static class Relation {
public int idx;
public int u;
public int v;
public int type;
public Relation(int idx, int u, int v, int type) {
this.idx = idx;
this.u = u;
this.v = v;
this.type = type;
}
}
public static int N, M;
public static int[] parent, rank;
public static Relation relation[];
public static boolean isShow[];
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
System.setIn(new FileInputStream("D:\\sample_input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parent = new int[N];
rank = new int[N];
relation = new Relation[M];
isShow = new boolean[N];
UnionFind();
// TODO String 타입의 크기비교가 가능한지 알아볼것
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int type = "ACK".equals(st.nextToken()) ? 0 : 1;
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
isShow[u] =true;
isShow[v] = true;
relation[i] = new Relation(i+1, u, v, type);
}
// ACK -> DIS 순으로 오름차순 정렬
Arrays.sort(relation, new Comparator<Relation>() {
@Override
public int compare(Relation a, Relation b) {
// TODO Auto-generated method stub
return a.type - b.type;
}
});
boolean isPossible = true;
int impossibleIdx = -1;
for (int i = 0; i < relation.length; i++) {
if (relation[i].type == 0) { // 같은 그룹일때 합친다
merge(relation[i].u, relation[i].v);
} else { // 이제부터 다른그룹이여야 한다
int uParent = find(relation[i].u);
int vParent = find(relation[i].v);
// 다른그룹이여야하는데, 그룹이 같다?
if (uParent == vParent) { // 모순 -> 빠져나간다
isPossible = false;
impossibleIdx = relation[i].idx;
break;
}
}
}
bw.flush();
if (!isPossible) { // 모순일경우
bw.write("CONTRADICTION AT " + impossibleIdx + "\n");
} else { // 가능한 최대 인원은?
int showCnt = 0;
int cnt[] = new int[N];
for (int i = 0; i < N; i++) {
cnt[parent[i]]++;
if(isShow[i]) {
showCnt++;
}
}
int max = 0;
for(int i=0; i<cnt.length; i++) {
if(cnt[i] > 1) {max += cnt[i];}
// max = Math.max(max, cnt[i]);
}
bw.write("MAX PARTY SIZE IS " + (max+(N-showCnt)) + "\n");
}
}
bw.close();
}
public static void UnionFind() {
for (int i = 0; i < N; i++) {
parent[i] = i;
}
}
public static int find(int u) {
if (u == parent[u])
return u;
return find(parent[u]);
}
public static boolean merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v)
return false;
if (rank[u] > rank[v]) {
parent[v] = u;
} else {
parent[u] = v;
}
if (rank[u] == rank[v])
++rank[v];
return true;
}
}
문제에서는 결국 두 개의 집합밖에 나올 수 없다.
핵심은 호의적인 개체들을 하나의 집합으로 Union(이하 merge) 하고, 동시에 적대적인 개체들을 merge한다.
모든 개체들을 merge 하면 결국 1개의 집합과 그 집합의 적대집합으로 나누어질것이다. 혹은 적대집합이 없을 수도 있다(공집합).
어쨌든 쌍으로 이루어진 각각의 컴포넌트에 대해(컴포넌트는 루트로 분별한다) 둘 중 더 큰 사이즈를 합치면 가능한 최대 집합의 크기가 나오게 된다. 중복된 쌍을 계산함을 방지하기 위해서 for문 안에 enemy의 번호가 현재 탐색중인 개체(node) 번호보다 큰 경우는 패스함에 유의한다.
정답 코드
package apss;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
// 알고스팟
// ID : EDITORWARS
// 알고리즘 : Union-Find
// 난이도 : 중
// 상태 : 풀이완료(답안)
public class EditorWars_Solution {
public static int N, M;
public static int[] parent, rank, size, enemies;
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
System.setIn(new FileInputStream("C://dev/sample_input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parent = new int[N];
rank = new int[N];
size = new int[N];
enemies = new int[N];
// 초기화
UnionFind();
boolean isPossible = true;
int impsIdx = -1;
// TODO String 타입의 크기비교가 가능한지 알아볼것
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int type = "ACK".equals(st.nextToken()) ? 0 : 1;
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
if(!isPossible){
continue;
}
if(type == 0){ // ACK
isPossible = ack(u,v);
}else{
isPossible = dis(u,v);
}
if(!isPossible){
impsIdx = i+1;
}
}
bw.flush();
if(isPossible){
bw.write("MAX PARTY SIZE IS " + maxParty() + "\n");
}else{
bw.write("CONTRADICTION AT " + impsIdx + "\n");
}
}
bw.close();
}
public static void UnionFind() {
Arrays.fill(enemies, -1);
Arrays.fill(size, 1);
for (int i = 0; i < N; i++) {
parent[i] = i;
}
}
public static int find(int u) {
if (u == parent[u])
return u;
return find(parent[u]);
}
public static int merge(int u, int v) {
int rtVal = 0;
// u나 v가 공집합인 경우 나머지 하나를 반환한다.
if(u == -1 || v == -1) return Math.max(u,v);
u = find(u);
v = find(v);
// 이미 둘이 같은 트리에 속한 경우
if (u == v)
return u;
if (rank[u] > rank[v]) { // v를 u에 편입시킨다
parent[v] = u;
size[u] += size[v];
rtVal = u;
} else { // u를 v에 편입시킨다
parent[u] = v;
size[v] += size[u];
rtVal = v;
}
if (rank[u] == rank[v])
++rank[v];
return rtVal;
}
public static boolean dis(int u, int v){
u = find(u);
v = find(v);
// 같은 집합에 속해 있으면 모순!
if(u == v) return false;
// 적의 적은 나의 동지
int a = merge(u, enemies[v]);
int b = merge(v, enemies[u]);
enemies[a] = b;
enemies[b] = a;
return true;
}
public static boolean ack(int u, int v){
u = find(u);
v = find(v);
// 두 집합이 서로 적대 관계라면 모순!
if(enemies[u] == v) return false;
// 동지의 적은 나의 적
int a = merge(u, v);
int b = merge(enemies[u], enemies[v]);
enemies[a] = b;
if(b != -1) enemies[b] = a;
return true;
}
public static int maxParty(){
int ret = 0;
for(int node=0; node<N; node++){
if(parent[node] == node){ // 루트일경우
int enemy = enemies[node];
// 같은 모임쌍을 두 번 세지 않기 위해, enemy < node인 경우만 센다.
// enemy == -1인 경우도 정확히 한 번씩 세게 된다.
if(enemy > node) continue;
int mySize = size[node];
int enemySize = (enemy == -1 ? 0 : size[enemy]);
// 두 집합 중 큰 집합을 더한다.
ret += Math.max(mySize, enemySize);
}
}
return ret;
}
}
회고
1. 끝까지 고민하지 못했다. 해결방안이 무엇인지 알고있었음에도 그걸 해결하기를 겁냈다. 또는 귀찮아했다.
2. 항상 입력값을 끝까지 받아야 다음 입력값을 제대로 받을 수 있음을 잊지 말아야한다. 이런 사소한 실수 때문에 많은 시간을 허비했다.
(break를 사용해 버렸다. 입력을 끝까지 안받았는데도.. 결국 런타임 에러의 원인이 뭔지 계속 생각해야했다)
3. 답안 풀이를 보면 항상 몇가지 조건을 만들고 그 조건에 따라 프로그래밍하는 깔끔함을 볼 수 있다. 물론 책이니까 결국 풀어버린 코드를 가지고 깔끔하게 정리할 수 있었겠지만, 실제로 문제를 풀기시작하면 저런 조건을 만드는게 힘들다. 직관적으로 와닿지 않는다고 할까? 이건 아직 내가 느끼지 못한 영역일지, 원래 그렇게 될 수 없는건지 항상 의문이다.
4. 회고과정이 필요하다는 생각이 들었다. 그래서 이런 섹션을 이번부터 추가했다. 회고하지 않으면 똑같은 실수를 반복할것 같아서이다.
'[개발] 지식 > 알고리즘 문제풀이' 카테고리의 다른 글
| [문제][알고스팟] PICNIC (0) | 2018.08.13 |
|---|---|
| [문제][알고스팟] 근거리네트워크 (LAN) (1) (0) | 2018.06.06 |
| [문제][Algospot] PROMISES(선거공약) (0) | 2018.04.22 |
| [문제] 감시 카메라 설치 (GALLERY) (0) | 2017.11.11 |
| [문제] SORTGAME (0) | 2017.10.13 |
<