백준 - 2458 키순서

www.acmicpc.net/problem/2458

2458번: 키 순서

1. 유형

그래프, 구현

 

2. 자료구조

딱히 쓴거 없음

 

3. 풀이

• 그래프 리스트형식으로 구현
• 조건에 맞게 구현

문제를 보고 맨처음 든 생각은 dfs풀이법 입니다. 플로이드와샬 풀이로 많은 사람이 풀었던데 저는 생각하지 못했습니다.

 

나보다 작은애들 + 나보다 큰애들 = 사람수-1 

 

위에서 사람수 -1 을 한 이유는 나 자신은 빼야하기 때문입니다.

 

1) dfs풀이

 

1번 노드부터 dfs를 돌려서 각 노드에 도착하면 카운트배열을 1 증가시킨다.

 

그렇다면 아래 그림처럼 각 노드의 방문 횟수를 알 수 있습니다.

빨간색 숫자가 의미하는 바는 현 노드를 몇번 방문당했는지 입니다.

 

4번 노드를 예로 들자면, 1번, 3번, 5번이 방문할 수 있으므로 카운트는 3 입니다.

 

2번 노드는 1번, 3번, 4번, 5번이 방문 가능 합니다. 따라서 카운트는 4번 입니다.

 

여기까지가 나보다 작은 애들의 수를 구한겁니다.

 

나보다 큰 애들은 dfs의 리턴값을 사용했습니다.

리턴값이 어려우시면

 

위 처럼 리턴값를 안쓰고, 입력을 받을때, 정방향 그래프, 역방향 그래프를 2개 만들고

 

각각 따로 dfs를 돌려서 카운트하는 방법도 있습니다.

 

2) 플로이드와샬

아직 안풀었당

 

4. 디버깅 실수

문제를 잘 읽어야합니다.

 

입력값에서 M이 간선의 갯수 입니다. M만큼 입력받아야 하는데, 

 

이것을 못보고 계속 N만큼 입력을 받다가 1시간 날렸습니다. ㅠ

 

5. 코드

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

public class Main {
	static int N, M, cnt[];
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static ArrayList<Integer> list[];
	static boolean visited[];
	
	static int dfs(int cur_node) {
		int candy = 0;
		for (int next_node : list[cur_node]) {
			if (visited[next_node]) {
				continue;
			}
			cnt[next_node]++;
			visited[next_node] = true;
			candy += dfs(next_node);
		}
		return candy + 1;
	}
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());
		list = new ArrayList[N + 1];

		cnt = new int[N + 1];
		for (int i = 0; i < list.length; i++) {
			list[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int u = Integer.valueOf(st.nextToken());
			int v = Integer.valueOf(st.nextToken());
			list[u].add(v);// 단방향
		}
		int big[] = new int[N + 1];
		for (int i = 1; i < N + 1; i++) {
			visited = new boolean[N + 1];
			big[i] = dfs(i) - 1;
		}
		int answer = 0;
		for (int i = 1; i < N + 1; i++) {
			if ((cnt[i] + big[i]) == N - 1) {
				answer++;
			}
		}
		System.out.println(answer);
	}

	
}