swea 5643 <[Professional] 키 순서>

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

SW Expert Academy

이문제는 DFS, BFS를 하는 심화과정의 문제이다. 신선한 문제이므로 한번 풀어보는 것을 추천한다.

 

이문제를 푸는 방법은 2가지가 있다.

 

이 문제의 핵심은 자기보다 작은 것이 몇 개인지, 그리고 자신보다 큰 것들이 몇 개 있는지를 판단하는

문제이다.

첫번째 방법

자신보다 큰 인원들을 담는 ArrayList와 자신보다 작은 인원을 담는 ArrayList 두 개를 이용해서 각각 dfs, bfs

두 번째 방법

자신보다 큰 인원을 담는 ArrayList를 선언하고 자신보다 작은 것들 중에 자신을 방문하면 count를 증가시켜주는 법

 

이렇게 두 가지가 있는데 나는 두 번째 방법을 선택하기로 했다. 이 방법이 메모리와 시간을 적게 잡아먹기 때문이다.

 

풀이 방법

1. 자신이 몇 개의 형제 정보를 알 수 있는지 기록 하기 num 위한 배열을 만든다. 그리고 자신보다 큰 인월을 담기 위한 List를 만든다.
2. 각각의 점에서 dfs를 하면서 방문한 점의 num 배열의 count를 증가시킨다.
3. 자신을 포함해서 방문한 점의 수를 자신의 num배열에 count 시킨다.
4. num배열의 개수가 n인 것을 count 한다.

 

 

이 과정을 거친 후 num의 값이 n인 것의 개수를 구해주면 된다.

 

은근히 생각을 요하는 문제이기 때문에 풀어보는 것이 좋다.

 

전체 코드

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

public class Solution {

	static int t, n,m,sum;
	static ArrayList<Integer> a[];
	static boolean visit[];
	static int num[];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for (int tc = 1; tc <= t; tc++) {
			n = Integer.parseInt(br.readLine());
			m = Integer.parseInt(br.readLine());
			num = new int[n+1];
			a=new ArrayList[n+1];
			for(int i=0;i<=n;i++) {
				a[i]=new ArrayList<Integer>();
			}
			for (int i = 0; i < m; i++) {
				st=new StringTokenizer(br.readLine());
				int pre=Integer.parseInt(st.nextToken());
				int next=Integer.parseInt(st.nextToken());
				a[pre].add(next);
			}
			for(int i=1;i<=n;i++) {
				sum=0;
				visit=new boolean[n+1];
				visit[i]=true;
				dfs(i);
				num[i]+=sum;
			}
			int result=0;
			for(int i=1;i<=n;i++) {
				if(num[i]==n) {
					result++;
				}
			}
			System.out.println("#"+tc+" "+result);
		}
	}

	private static void dfs(int k) {
		// TODO Auto-generated method stub
		sum++;
		for(int i=0;i<a[k].size();i++) {
			if(visit[a[k].get(i)]) {
				continue;
			}
			visit[a[k].get(i)]=true;
			num[a[k].get(i)]++;
			dfs(a[k].get(i));
		}
	}
}