[백준]4196번 도미노 문제풀이

이미지를 클릭하면 문제 링크로 연결됩니다

 

풀이

고려해야할 점

• 여러 개의 테스트 케이스가 존재하며 각 테스트 케이스는 최대 100000개의 도미노가 주어진다. 시간 복잡도를 고려하면 O(n)이나 O(nlogn) 사이로 구현해야 한다.
• 도미노는 순서대로 넘어지므로 이 순서를 바탕으로 처음 넘어뜨려야 하는 도미노를 찾아야 한다. 
• 보통 도미노의 시작 지점을 찾아서 넘어뜨릴 것이나, 도미노가 루프 형태를 가질 경우 시작 지점이 존재하지 않을 수도 있다. (예외 케이스)
• 예외 1: 루프 형태 

• 예외 2: 올가미 형태  

 

문제 풀이 아이디어

• 먼저 모든 도미노의 연결 관계를 저장한다. (자신을 넘어뜨릴 수 있는 도미노는 부모, 자신이 넘어뜨리는 도미노는 자식으로 설정하여 연관관계를 저장)
• 부모가 없는 도미노의 경우 사람이 직접 넘어뜨려야 하므로 해당 도미노를 시작으로 연결된 도미노를 전부 넘어뜨린다. (방문 체크 배열로 넘어진 도미노 표시)
• 남은 도미노 중 자식이 2개 존재하는 배열을 찾는다. (올가미 형태의 도미노) 그리고 해당 도미노를 넘어뜨리면 연결되어 있는 모든 도미노가 넘어진다. 
• 남은 도미노 중  넘어뜨리지 않은 도미노가 있을 경우 넘어뜨린다. (루프 형태의 도미노) 루프 형태는 아무 도미노를 넘어뜨려도 연결된  도미노 모두 넘어진다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int T  = Integer.parseInt(br.readLine()); // 테스트 케이스 수 입력
		
		// 테스트 케이스 수 만큼 반복
		for(int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken()); // 노드 수
			int m = Integer.parseInt(st.nextToken()); // 간선 수
			
			int[] parent = new int[n+1];      // 각 노드의 부모 수를 저장하는 배열
			int[] decendent = new int[n+1];   // 각 노드의 자식 수를 저장하는 배열
			boolean[] visited = new boolean[n+1]; // 방문 여부를 저장하는 배열
			ArrayList<Integer>[] al = new ArrayList[n+1]; // 인접 리스트
			
			for(int i = 0; i <= n; i++)
				al[i] = new ArrayList<>(); // 인접 리스트 초기화
			
			// 간선 정보 입력 및 인접 리스트 구성
			for(int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				parent[b]++;    // b의 부모 노드 개수 증가
				decendent[a]++; // a의 자식 노드 개수 증가
				al[a].add(b);   // a에서 b로 가는 간선 추가
			}
			
			int count = 0; // 제거할 노드 그룹 수를 카운트
			
			// 부모가 없는 노드 그룹 제거
			for(int i = 1; i <= n; i++) {
				if(!visited[i] && parent[i] == 0) {
					count++;
					bfs(i, visited, al);
				}
			}
			
			// 자식이 2개 이상인 노드 그룹 제거
			for(int i = 1; i <= n; i++) {
				if(!visited[i] && decendent[i] > 1) {
					count++;
					bfs(i, visited, al);
				}
			}
			
			// 루프가 있는 노드 그룹 제거 (자식이 1개인 노드)
			for(int i = 1; i <= n; i++) {
				if(!visited[i] && decendent[i] == 1) {
					count++;
					bfs(i, visited, al);
				}
			}
			sb.append(count).append("\n"); // 테스트 케이스별 결과 추가
		}
		System.out.print(sb); // 전체 결과 출력
	}
	
	// BFS 함수: 노드 그룹을 탐색하며 방문 처리
	public static void bfs(int start, boolean[] visited, ArrayList<Integer>[] al) {
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		visited[start] = true;
		
		while(!q.isEmpty()) {
			int now = q.poll();
			for(int next : al[now]) {
				if(!visited[next]) {
					visited[next] = true;
					q.add(next);
				}
			}
		}
	}
}