[Swea - 5643] 키 순서

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo&

SW Expert Academy

1. 유형

그래프

 

2. 풀이

 

인접리스트를 만든다.

 

이때, 주어진 그래프대로 인접리스트를 만들고, 그 반대 방향 인접리스트를 만든다.

 

이런 식으로 주어진 입력값과 반대 방향 리스트를 만든다.

 

4번 노드를 예를 들어보면, 나보다 작은 값은 3개가 있고, 큰 값은 2개가 있다.

 

3+2 =5 즉, 5는 전체 사이즈에서 나를 뺀 값이다. 

 

그러므로 1부터 N번 노드를 돌면서 그래프를 탐색해서 나보다 큰값과 작은 값들의 합이 N-1이 되는 것을 찾으면 된다.

 

보다 쉽게 나보다 작은값과 큰 값을 찾기위해 리스트를 2개를 만든 것이다.

 

3. 코드

package swea;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Swea_5643키순서 {
	static int N,M,sum,sum2;
	static ArrayList<Integer> list[],rev[];
	static boolean visit[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int T = Integer.valueOf(st.nextToken());
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.valueOf(in.readLine());
			M = Integer.valueOf(in.readLine());
			list = new ArrayList[N+1];
			rev = new ArrayList[N+1];
			for(int i=0;i<=N;i++) {
				list[i]= new ArrayList<>();
				rev[i] = new ArrayList<>();
			}
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				int a = Integer.valueOf(st.nextToken());
				int b = Integer.valueOf(st.nextToken());
				list[a].add(b);
				rev[b].add(a);
			}
			int ans=0;
			for(int i=1;i<=N;i++) {
				visit = new boolean[N+1];
				sum=0;
				findUp(i);
				visit = new boolean[N+1];
				sum2=0;
				findDown(i);
				if(sum+sum2==N-1) {
					ans++;
				}
			}
			System.out.println("#"+tc+" "+ans);
		}
	}
	static void findUp(int cur) {
		visit[cur] = true;
		for(int next : list[cur]) {
			if(visit[next]) continue;
			sum++;
			findUp(next);
		}
	}
	static void findDown(int cur) {
		visit[cur] = true;
		for(int next : rev[cur]) {
			if(visit[next]) continue;
			sum2++;
			findDown(next);
		}
	}
}
/*
나보다 작은것 큰것 합쳤을때 합이 size-1이 나와야함
입력받을 때, 2번 받기, 위 아래
down up 배열 선언 나중에 더해서 사이즈-1 이면 답이다

반복문 N만큼
현지점에서 나보다 큰 애들 몇명인지
	재귀사용하기
현지점에서 나보다 작은 애들 몇명인지
	재귀사용하기
두개를 더해서 사이즈-1이면 증가
*/