[ SWEA ] 5643 키 순서 D4 (JAVA)

---

---

문제 이해

• 각 학생 별로 키를 비교해야한다.
• 비교 결과에 따라 특정 학생은 자신이 몇 번째 순서인지 알거나 알 수없다.
• 키를 비교한 결과를 토대로 자신의 키가 몇 번째인지 알 수 있는 학생의 수를 구한다.

아이디어

• 자신의 키가 몇 번째인지 알려면 자기를 제외한 모든 학생들(노드라고치면)과 연결되어 있어야한다.
• 리스트 배열로 작은 키에서 큰 키로 나아가는 배열, 큰 키에서 작은 키로 나아가는 배열을 만들어 관리한다.
• 인접리스트를 생각했을 때 가로방향(행)이 작은 키고, 세로방향(열)이 큰 키를 나타낸다.
• 작은->큰 키로 나아갈 때의 연결 개수 + 큰 -> 작은 키로 나아갈때의 연결 개수 가 전체 학생수 -1 이면 그 학생은 자기가 몇번 째인지 알 수 있다.

코드

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

public class Main {
	static ArrayList<ArrayList<Integer>> ctop = new ArrayList<>();
	static ArrayList<ArrayList<Integer>> ptoc = new ArrayList<>();
	static int N;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for(int tc = 1; tc<=T;++tc) {
			N = Integer.parseInt(br.readLine()); 
			ctop.clear();
			ptoc.clear();
			for(int i=0;i<N+1;++i) {
				ctop.add(new ArrayList<>());
				ptoc.add(new ArrayList<>());
			}
			int M = Integer.parseInt(br.readLine()); 
			for(int i=0;i<M;++i) {
				StringTokenizer st = new StringTokenizer(br.readLine()," ");
				int small = Integer.parseInt(st.nextToken());
				int big = Integer.parseInt(st.nextToken());
				ctop.get(small).add(big);
				ptoc.get(big).add(small); 
			}
			int result = 0;
			for(int i=1;i<=N;++i) {
				result = (count(i) == N-1) ? result + 1 : result;
			}
			sb.append("#").append(tc).append(" ").append(result).append('\n');
		}
		System.out.println(sb);
	}
	
	static int count(int idx) {
		Queue<Integer> q = new LinkedList<>();
		boolean isVisited[]=new boolean[N+1];
		int cnt = 0;
		// 자식에서 부모로 ( 작은거에서 큰거로 )
		q.offer(idx);
		while(!q.isEmpty()) {
			int current = q.poll();
			for(int i=0;i<ctop.get(current).size();++i) {
				int val = ctop.get(current).get(i);
				if(!isVisited[val]) {
					isVisited[val] = true;
					q.offer(val);
					cnt++;
				}
			}
		}
		// 부모에서 자식으로 ( 큰거에서 작은거로 )
		q.offer(idx);
		while(!q.isEmpty()) {
			int current = q.poll();
			for(int i=0;i<ptoc.get(current).size();++i) {
				int val = ptoc.get(current).get(i);
				if(!isVisited[val]) {
					isVisited[val] = true;
					q.offer(val);
					cnt++;
				}
			}
		}
		return cnt;
	}
}

 

 

---

CPDM