Do it! 알고리즘 코딩 테스트 (52번 ~ 53번)

52번 거짓말

---

내가 떠올린 풀이 해설

파티에 참석한 사람들을 1개의 집합으로 생각하고, 각각의 파티마다 union연산을 이용해 사람들을 연결하는 것이 중요하다. 이 작업을 하면 1개의 파티에 있는 모든 사람들은 같은 대표 노드를 바라보게 된다. 이후 각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find연산을 이용해 확인함으로써 과장된 이야기를 할 수 있는지 판단할 수 있다. 진실을 아는 사람 데이터, 파티 데이터, 유니온 파인드를 위한 대표 노드 자료구조를 초기화한다. union연산을 수행해 각 파티에 참여한 사람들을 1개의 그룹으로 만든다. find 연산을 수행해 각 파티의 대표 노드와 진실을 아는 사람들이 같은 그룹에 있는지 확인한다. 파티 사람 노드는 모두 연결돼 있으므로 아무 사람이나 지정해 find 연산을 수행하면 된다. 모든 파티에 관해 과정을 반복해 수행하고, 모든 파티의 대표 노드가 진실을 아는 사람들과 다른 그룹에 있다면 결괏값을 증가시킨다. 과장할 수 있는 파티의 개수를 결괏값으로 출력한다.

---

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek1043 {
	static int[] trueP;
	static ArrayList<Integer>[] party;
	static int[] parent;
	static int result = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(st.nextToken());
		trueP = new int[t];
		for(int i = 0; i < t; i++) {
			trueP[i] = Integer.parseInt(st.nextToken());
		}
		
		party = new ArrayList[m];
		for(int i = 0; i < m; i++) {
			party[i] = new ArrayList<>();
			st = new StringTokenizer(br.readLine());
			int people = Integer.parseInt(st.nextToken());
			for(int j = 0; j < people; j++) {
				party[i].add(Integer.parseInt(st.nextToken()));
			}
		}
		parent = new int[n + 1];
		for(int i = 0; i <= n; i++) {
			parent[i] = i;
		}
		for(int i = 0; i < m; i++) {
			int firstPeople = party[i].get(0);
			for(int j = 1; j < party[i].size(); j++) {
				union(firstPeople, party[i].get(j));
			}
		}
		for(int i = 0; i < m; i++) {
			boolean isPossible = true;
			int cur = party[i].get(0);
			for(int j = 0; j < trueP.length; j++) {
				if(find(cur) == find(trueP[j])) {
					isPossible = false;
					break;
				}
			}
			if(isPossible) {
				result++;
			}
		}
		System.out.println(result);
	}
	private static int find(int a) {
		if(a == parent[a]) {
			return a;
		}
		else {
			return parent[a] = find(parent[a]);
		}
	}
	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
		}
	}
}

---

53번 줄 세우기

---

내가 떠올린 풀이 해설

학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제이다. 특히 답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다는 것을 알 수 있다. 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트한다. 위상 정렬 수행 과정은 진입 차수가 0인 노드를 큐에 저장한다 큐에서 데이터를 poll 해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 한다. 큐가 빌 때까지 반복한다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek2252 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		for(int i = 0; i <= n; i++) {
			list.add(new ArrayList<>());
		}
		int insert[] = new int[n + 1];
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			list.get(s).add(e);
			insert[e]++;
		}
		Queue<Integer> que = new LinkedList<>();
		for(int i = 1; i <= n; i++) {
			if(insert[i] == 0) {
				que.offer(i);
			}
		}
		while(!que.isEmpty()) {
			int now = que.poll();
			System.out.println(now );
			for(int next : list.get(now)) {
				insert[next]--;
				if(insert[next] == 0) {
					que.offer(next);
				}
			}
		}
	}
}

---

오늘의 회고

오늘은 union문제와 위상 정렬의 개념을 학습하고 위상 정렬을 적용하는 문제를 풀고 최근에 푼 문제부터 Do it! 알고리즘 코딩 테스트 (32번 ~ 35번) 까지 복습을 진행하였습니다. 반복해서 위상 정렬의 다른 문제가 나와도 막힘 없이 해결해 나아갈 수 있게 학습하겠습니다. 주말에 친구들과 시간을 보내고 쉬었으니 이번 주도 꾸준하게 공부하겠습니다.