백준 14676번 : 영우는 사기꾼? (Java)

 문제

https://www.acmicpc.net/problem/14676

14676번: 영우는 사기꾼?

14676 영우는 사기꾼?

 

 구현 방법

건물들이 이전에 반드시 건설된 상태여야 지을 수 있으므로 위상 정렬 알고리즘을 사용했습니다.

 

문제 풀이 과정을 간략하게 적자면

1. 건물 생성 시 진입 차수가 0이 아니거나 건물 파괴 시 건물 개수가 없으면 치트키를 사용하여 건물을 건설 or 치트키를 사용하여 건설한 건물을 파괴 하는 것이므로 치트키 사용을 알 수 있음

2. 건물 생성 시, 건물 개수을 올려주고 해당 건물과 관계된 건물들의 진입 차수를 줄여줌

3. 건물 파괴 시, 건물 개수를 줄여주고 줄여준 건물 개수가 0일 때 해당 건물과 관계된 건물들의 진입 차수를 올려줌

위와 같습니다.

 

하지만 한 번 틀렸는데요 ㅠㅅㅠ

중복 건설이 가능하면서 건물 2개를 지어야 건설할 수 있는 건물 A가 있다고 가정할 때 하나의 건물만 2개를 지으면 또 다른 건물을 아직 짓지 않았음에도 불구하고 A 건물의 진입 차수가 0이 되면서 A 건물을 지을 수 있습니다.

따라서 건물을 짓고 진입 차수를 줄여줄 때 중복된 건물은 진입 차수를 줄여주면 안됩니다.

 

저는 Set 자료구조를 사용하여 삭제 되는 건물의 번호를 추가하며 중복을 확인해줬습니다!

 

주의할 점

1. 중복으로 건설했을 때 진입 차수가 중복으로 줄어들어 조건을 만족하지 않아도 건물이 지어질 수 있음 -> 진입 차수 삭제 시 중복 체크

2. 건물을 파괴하여 해당 건물이 사라지면 관련된 건물을 지으면 안됨 -> 관련된 건물 진입 차수 늘려주기

 

 구현 코드

package BOJ.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class B14676_영우는사기꾼 {
	static int N, M, K, inDegree[], buildCnt[];
	static List<List<Integer>> list = new ArrayList<>();
	static List<Set<Integer>> remove = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		inDegree = new int[N+1]; // 진입 차수
		buildCnt = new int[N+1]; // 건물 개수
		for (int i=0;i<=N;i++) {
			list.add(new ArrayList<>());
			remove.add(new HashSet<>());
		}
		for (int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			list.get(from).add(to); // 간선 저장
			inDegree[to]++; // 진입 차수 저장
		}
		
		for (int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine());
			int order = Integer.parseInt(st.nextToken());
			int now = Integer.parseInt(st.nextToken());
			if ((order == 1 && inDegree[now] != 0) || // 건물 생성 시 지으려는 건물의 진입 차수가 0이 아니다 == 건물을 지을 수 없다
					(order == 2 && buildCnt[now] == 0)) { // 건물 파괴 시 건물 개수가 0이다 == 건물을 파괴할 수 없다
				System.out.println("Lier!");
				System.exit(0);
			}
			if (order == 1) { // 건물 생성
				buildCnt[now]++;
				for (int next : list.get(now)) { // 지을 수 있는 건물들
					if (!remove.get(next).contains(now)) { // 삭제된 건물이 아니라면
						remove.get(next).add(now); // 삭제 리스트에 추가
						if (inDegree[next] == 0) continue;
						inDegree[next]--; // 진입 차수 줄여주기
					}
				}
			} else if (order == 2) { // 건물 파괴
				buildCnt[now]--; 
				if (buildCnt[now] == 0) { // 건물을 파괴하여 건물이 아예 없다면
					for (int next : list.get(now)) {
						remove.get(next).clear(); // 삭제 리스트 초기화
						inDegree[next]++; // 다시 진입 차수 늘려줌
					}
				}
			}
		}
		System.out.println("King-God-Emperor");
	}
}

 

정답!