백준 14674. 영우는 사기꾼?

문제

14676번: 영우는 사기꾼?

 

문제풀이

• 건물을 짓는데 순서가 필요하기 때문에 위상정렬을 사용하였습니다. 
• 명령어가 1일 경우 것물을 짓을 수 있는지 indegree배열을 확인하여 체크 하였습니다.
• 명령어가 2일 경우 build 배열을 확인하여 0이하면 파괴할 수 없으므로 Lier!출력 아니면 1을 감소 시킵니다.

소스코드(Java)

baek/baek14676.java · master · kastori / algo

package baek;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 영우는 사기꾼?
 * https://www.acmicpc.net/problem/14676
 */
public class baek14676 {
	public static void main(String[] args) throws Exception {
		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());
		int K = Integer.parseInt(st.nextToken());

		int[] indegree = new int[N + 1];
		int[] build = new int[N + 1];
		List<Integer>[] adj = new ArrayList[N + 1];

		for (int i = 0; i <= N; i++) {
			adj[i] = new ArrayList<>();
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			adj[x].add(y);
			indegree[y]++;
		}
		String answer = "King-God-Emperor";

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			// 건설
			if (x == 1) {
				//건설 불가능
				if (indegree[y] > 0) {
					answer = "Lier!";
					break;
				} else {
					build[y]++;
					if (build[y] == 1 && adj[y].size() > 0) {
						for (Integer next : adj[y]) {
							indegree[next]--;
						}
					}
				}
			}
			// 파괴
			else {
				// 건설한 적이 없는 건물
				if (build[y] == 0) {
					answer = "Lier!";
					break;
				} else {
					build[y]--;
					if (build[y] == 0 && adj[y].size() > 0) {
						for (Integer next : adj[y]) {
							indegree[next]++;
						}
					}
				}
			}
		}
		System.out.println(answer);
	}

}