[SWEA] 5643 키순서

1. 문제

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

SW Expert Academy

2. 접근방법

내 위치에서

자식들만 쭉 ~~ 따라가보고

부모들만 쭉 ~~ 따라갔을때

 

모든 친구들을 만날 수 있다면

그 친구는 자신이 몇번 째인지 정의가 가능하다.

 

먼저 4의 경우를 보면

부모는 2, 6

자식은 1,3,5

즉 모든 친구와 본인의 관계를 증명해낼수 있다.

-----------------

5의 경우를 보면

부모를 찾아갈 때 2,4,6

자식은 1

이렇게 되면 3과 본인의 관계를 증명할 방법이 없으니 몇번째 수인지 확실히 구할 수 없다.

 

이 개념으로 구현을 하면 된다.

 

3. 자바

코드

package algo;

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

public class P5643키순서 {
	static int N,M;
	static List<Integer> [] big;
	static List<Integer> [] small;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc = 1 ; tc<=T ; tc++) {
			N = Integer.parseInt(br.readLine());
			M = Integer.parseInt(br.readLine());
			big = new ArrayList [N+1];
			small = new ArrayList [N+1];
			for(int i = 0 ; i <= N ; i++) {
				big[i] = new ArrayList<Integer>();
				small[i] = new ArrayList<Integer>();
			}
			for(int i = 0 ; i < M ; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int smallNum = Integer.parseInt(st.nextToken());
				int bigNum = Integer.parseInt(st.nextToken());
				big[smallNum].add(bigNum);
				small[bigNum].add(smallNum);
			}
			int result = 0;
			for(int i = 1 ; i <= N ; i++) {
				int mycnt = count(i);
				if(mycnt == N-1)
					result++;
			}
			System.out.println("#"+tc+" "+result);
			
		}
		
	}
	
	static int count(int num) {
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(num);
		boolean visited[] = new boolean[N+1];
		visited[num] = true;
		int cnt = 0;
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int i : big[now]) {
				if(visited[i])
					continue;
				visited[i] = true;
				cnt++;
				que.offer(i);
			}
		}
		que.offer(num);
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int i : small[now]) {
				if(visited[i])
					continue;
				visited[i] = true;
				cnt++;
				que.offer(i);
			}
		}
		return cnt;
	}

}

4. 마치며

꽤나 신선한 개념을 요구해서 재밌게 풀이한 문제였다.