Baekjoon - 1043

문제

Solved.ac Class4

개념 - UnionFind

부모를 노드로 연결하는 개념이다.

노드	1	2	3	4
부모	1	2	3	4

이렇게 특정 노드와 이들이 부모를 가르키게 한다. 처음에는 자기 자신을 가리키다가 연결을 시키면

노드	1	2	3	4
부모	1	1	3	4

이런식으로 같은 부모를 가리키게 한다.
1,2는 같은 부모를 두고 있다.

필요 매서드

이 과정에서 2가지가 필요한데
1.

public static int find(int x) {
	if(parent[x] == x) return x;
	return find(parent[x]);
}

이렇게 부모를 찾는 과정이다.
아래와 같은 경우 3번노드의 부모는 1번이다.
3번과 3번에 있는 값 2는 다르고 이걸 반복해서 부모를 찾는 과정이다

노드	1	2	3	4
부모	1	1	2	4

public static boolean union(int x, int y) {
		x = find(x);
		y = find(y);

		if(x == y) return false;

		if(x <= y) parent[y] = x;
		else parent[x] = y;
		return true;
	}

이렇게 합치는 것도 필요하다. 부모 노드의 값으로 대체하는 과정이다.

1차시도

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int peopleCount = Integer.parseInt(split[0]);
		int partyCount = Integer.parseInt(split[1]);
		boolean[] isKnownPeople = new boolean[peopleCount + 1];
		int[] parents = new int[peopleCount + 1];
		Set<Integer>[] party = new HashSet[partyCount + 1];
		int count = 0;

		for (int i = 1; i < peopleCount + 1; i++) {
			parents[i] = i;
		}
		for (int i = 1; i < partyCount + 1; i++) {
			party[i] = new HashSet<Integer>();
		}

		String[] knownPeopleData = br.readLine().split(" ");
		int knownPeopleCount = Integer.parseInt(knownPeopleData[0]);
		for (int i = 1; i < knownPeopleCount + 1; i++) {
			isKnownPeople[Integer.parseInt(knownPeopleData[i])] = true;
		}

		for (int i = 1; i < partyCount + 1; i++) {
			String[] data = br.readLine().split(" ");
			int size = Integer.parseInt(data[0]);
			if (size == 1) {
				party[i].add(Integer.parseInt(data[1]));
				continue;
			}
			for (int j = 1; j < size; j++) {
				int now = Integer.parseInt(data[j]);
				int next = Integer.parseInt(data[j + 1]);
				if (parents[now] != parents[next]) {
					union(parents, now, next);
				}
				party[i].add(now);
				party[i].add(next);
			}
		}

		for (int i = 1; i < peopleCount + 1; i++) {
			if (isKnownPeople[i]) {
				int root = find(parents, i);
				for (int j = 1; j < peopleCount + 1; j++) {
					if (find(parents, j) == root) {
						isKnownPeople[j] = true;
					}
				}
			}
		}

		for (int i = 1; i < partyCount + 1; i++) {
			boolean isUnknown = false;
			for (int people : party[i]) {
				if (isKnownPeople[people]) {
					isUnknown = true;
					break;
				}
			}
			if (!isUnknown) {
				count++;
			}
		}

		System.out.println(count);

	}

	private static int find(int[] parents, int index) {
		if (parents[index] == index) {
			return index;
		}
		return find(parents, parents[index]);
	}

	private static void union(int[] parents, int now, int next) {
		int findParents = find(parents, next);
		parents[findParents] = parents[now];
	}
}

StackOverflowException

2차시도

public class Main {
	private static int[] parents;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int personCount = Integer.parseInt(split[0]);
		int partyCount = Integer.parseInt(split[1]);
		int count = 0;

		parents = new int[personCount + 1];
		boolean[] truthPeople = new boolean[personCount + 1];
		Set<Integer>[] party = new HashSet[partyCount + 1];

		for (int i = 1; i < partyCount + 1; i++) {
			party[i] = new HashSet<>();
		}
		for (int i = 1; i < personCount + 1; i++) {
			parents[i] = i;
		}


		String[] truthData = br.readLine().split(" ");
		int truthCount = Integer.parseInt(truthData[0]);
		for (int i = 1; i < truthCount + 1; i++) {
			truthPeople[Integer.parseInt(truthData[i])] = true;
		}

		for (int i = 1; i < partyCount + 1; i++) {
			String[] data = br.readLine().split(" ");
			int attendCount = Integer.parseInt(data[0]);
			if (attendCount == 1) {
				party[i].add(Integer.parseInt(data[1]));
			}
			for (int j = 1; j < attendCount; j++) {
				int now = Integer.parseInt(data[j]);
				int next = Integer.parseInt(data[j + 1]);
				int nowParent = find(now);
				int nextParent = find(next);
				if (nowParent != nextParent) {
					if(now <= next) parents[next] = now;
					else parents[now] = next;
				}
				party[i].add(now);
				party[i].add(next);
			}
		}

		for (int i = 1; i < personCount + 1; i++) {
			if (truthPeople[i]) {
				int rootValue = find(i);
				for (int j = 1; j < personCount + 1; j++) {
					if (find(j) == rootValue) {
						truthPeople[j] = true;
					}
				}
			}
		}

		for (int i = 1; i < partyCount + 1; i++) {
			boolean isUnknown = true;
			for (int person : party[i]) {
				if (truthPeople[person]) {
					isUnknown = false;
					break;
				}
			}
			if (isUnknown) {
				count++;
			}
		}


		System.out.println(count);
	}

	private static int find(int num) {
		if (parents[num] == num) {
			return num;
		}
		return find(parents[num]);
	}

}

어디서 넘쳤는지 감이 오지 않아. 다시 작성했다.

실패

3차시도

public class Main {
	private static int[] parents;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int personCount = Integer.parseInt(split[0]);
		int partyCount = Integer.parseInt(split[1]);
		int count = 0;

		parents = new int[personCount + 1];
		boolean[] truthPeople = new boolean[personCount + 1];
		Set<Integer>[] party = new HashSet[partyCount + 1];

		for (int i = 1; i < partyCount + 1; i++) {
			party[i] = new HashSet<>();
		}
		for (int i = 1; i < personCount + 1; i++) {
			parents[i] = i;
		}


		String[] truthData = br.readLine().split(" ");
		int truthCount = Integer.parseInt(truthData[0]);
		for (int i = 1; i < truthCount + 1; i++) {
			truthPeople[Integer.parseInt(truthData[i])] = true;
		}

		for (int i = 1; i < partyCount + 1; i++) {
			String[] data = br.readLine().split(" ");
			int attendCount = Integer.parseInt(data[0]);
			if (attendCount == 1) {
				party[i].add(Integer.parseInt(data[1]));
			}
			for (int j = 1; j < attendCount; j++) {
				int now = Integer.parseInt(data[j]);
				int next = Integer.parseInt(data[j + 1]);
				int nowParent = find(now);
				int nextParent = find(next);
				if (nowParent != nextParent) {
					//excahnge
					exchange(now, next);
				}
				party[i].add(now);
				party[i].add(next);
			}
		}

		for (int i = 1; i < personCount + 1; i++) {
			if (truthPeople[i]) {
				int rootValue = find(i);
				for (int j = 1; j < personCount + 1; j++) {
					if (find(j) == rootValue) {
						truthPeople[j] = true;
					}
				}
			}
		}

		for (int i = 1; i < partyCount + 1; i++) {
			boolean isUnknown = true;
			for (int person : party[i]) {
				if (truthPeople[person]) {
					isUnknown = false;
					break;
				}
			}
			if (isUnknown) {
				count++;
			}
		}


		System.out.println(count);
	}

	private static int find(int num) {
		if (parents[num] == num) {
			return num;
		}
		return find(parents[num]);
	}

	private static void exchange(int now, int next) {
		if (parents[next] != next) {
			exchange(now, parents[next]);
		}
		parents[next] = now;
	}

}

예외를 찾던 중 오류를 발견했다.
2번째 시도의 경우 가장 높이 연결되어 있는 노드를 바꾸면 문제가 없지만. 내가 부모 노드가 아닌 경우(나와 내가 가르키는 root값이 다른경우) 내가 가르키는 위쪽 값들은 변경되지 않는 오류가 있다.
따라서 exchange매서드를 통해 이를 해결해 주었다.

성공

ToKotlin

var parents: IntArray? = null

fun main() {
    val split = readln().split(" ")
    val personCount = split[0].toInt()
    val partyCount = split[1].toInt()
    var count = 0

    parents = IntArray(personCount + 1)
    val truthPeople = BooleanArray(personCount + 1)
    val party: Array<HashSet<Int>?> = arrayOfNulls(partyCount + 1)
    for (i in 1..partyCount) {
        party[i] = HashSet()
    }

    for (i in 1..personCount) {
        parents!![i] = i
    }

    val truthData = readln().split(" ")
    val truthCount = truthData[0].toInt()
    for (i in 1..truthCount) {
        truthPeople[truthData[i].toInt()] = true
    }

    for (i in 1..partyCount) {
        val data = readln().split(" ")
        val attendCount = data[0].toInt()

        if (attendCount == 1) {
            party[i]?.add(data[1].toInt())
        }
        for (j in 1..<attendCount) {
            val now = data[j].toInt()
            val next = data[j + 1].toInt()
            val nowParent = find(now)
            val nextParent = find(next)
            if (nowParent != nextParent) {
                exchange(now, next)
            }
            party[i]?.add(now)
            party[i]?.add(next)
        }
    }

    for (i in 1..personCount) {
        if (truthPeople[i]) {
            val rootValue = find(i);
            for (j in 1..personCount) {
                if (find(j) == rootValue) {
                    truthPeople[j] = true;
                }
            }
        }
    }

    for (i in 1..partyCount) {
        var isUnknown = true;
        for (person in party[i]!!) {
            if (truthPeople[person]) {
                isUnknown = false
                break
            }
        }
        if (isUnknown) {
            count++;
        }
    }

    println(count)
}

fun find(num: Int) :Int{
    if (parents!![num] == num) {
        return num;
    }
    return find(parents!![num]);
}

fun exchange(now: Int, next: Int) {
    if (parents!![next] != next) {
        exchange(now, parents!![next]);
    }
    parents!![next] = now;
}