[SWEA] 키 순서

👀 문제 설명

문제

로그인해야 문제를 볼 수 있다.

 

✍🏻풀이

* 백준의 키 순서 문제와 같다.

 

heightInfo 배열을 사용해 부모와 자식의 관계를 나타내줬다.

heightInfo[i][j]가 1이라면, i의 부모가 j라는 뜻으로, i보다 j가 키가 크다는 뜻이고,

heightInfo[i][j]가 2라면, i의 자식이 j라는 뜻으로, i보다 j가 키가 작다는 뜻이다.

 

관계를 나타내준 후, 각각 i 값에 접근하여 BFS를 사용해서 문제를 풀면 된다.

먼저, 접근 가능한 부모를 모두 방문하고,

이후에 접근 가능한 자식을 모두 방문한다.

모두 방문했으면, visit 배열에서 방문하지 않은 값이 있는지 확인하고, 방문하지 않은 값이 있다면, 해당 사람의 키 순서를 알 수 없다는 뜻이므로 false를, 아니라면 true를 리턴한다.

 

코드

package swea;

// [Professional] 키 순서 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo&categoryId=AWXQsLWKd5cDFAUo&categoryType=CODE&problemTitle=5643&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 )

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

public class SWEA_5643 {
	
	private static int N, M;
	private static int[][] heightInfo; // heightInfo[i][j] = 1이면, i의 부모가 j이다. heightInfo[i][j] = 2이면, i의 자식이 j이다.
	private static boolean[] visit;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T;

		T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			M = Integer.parseInt(br.readLine());
			
			heightInfo = new int[N + 1][N + 1];
			visit = new boolean[N + 1];
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				heightInfo[a][b] = 1;
				heightInfo[b][a] = 2;
			}
			
			int cnt = 0;
			for (int student = 1; student <= N; student++) {
				if (isOkay(student)) cnt++;
			}
			
			bw.write("#" + tc + " " + cnt + "\n");
		}

		bw.flush();
		bw.close();
	}
	
	private static boolean isOkay(int start) {
		boolean ans = true;
		Arrays.fill(visit, false);
		visit[start] = true;
        
		// 부모를 탐색
		Deque<Integer> deque = new ArrayDeque<>();
		deque.add(start);
		
		while (!deque.isEmpty()) {
			int cur = deque.poll();
			
			for (int i = 1; i <= N; i++) {
				if (heightInfo[cur][i] == 1 && !visit[i]) {
					visit[i] = true;
					deque.add(i);
				}
			}
		}
		
		deque.add(start);
		// 자식을 탐색
		while (!deque.isEmpty()) {
			int cur = deque.poll();
			
			for (int i = 1; i <= N; i++) {
				if (heightInfo[cur][i] == 2 && !visit[i]) {
					visit[i] = true;
					deque.add(i);
				}
			}
		}
		
		for (int i = 1; i <= N; i++) {
			if (!visit[i]) ans = false;
		}
		
		return ans;
	}
	
}