[백준(Python/Java)] 2458_키 순서

https://www.acmicpc.net/problem/2458

2458번: 키 순서

 

* 프로그래머스에 있는 [순위] 문제와 완전히 동일한 문제인데요. 해당 문제의 링크는 아래에 있습니다.

코딩테스트 연습 - 순위

 

우선 이 문제에서 "자신의 키가 몇 번째인지 정확히 알 수 있는 사람"은 자신을 제외한 나머지 사람들이 자신보다 키가 큰지, 작은지를 모두 아는 사람입니다. 만약 다른 사람 한 명의 키가 나보다 큰지, 작은지 불분명하다면 자신의 키가 몇 번째인지 알 수 없습니다.

 

따라서, 모든 사람에 대해 DFS로 완전 탐색을 하면 문제를 해결할 수 있는데요. 이 문제에서 간선의 방향은 키가 큰 사람 -> 키가 작은 사람으로 연결되어 있기 때문에 A라는 사람에서 출발하여 거친 모든 사람(노드)는 A보다 작은 사람이 됩니다. 그리고 이를 반대로 생각하면 해당 노드들은 A가 자신보다 키가 크다는 것을 알 수 있죠. 그러면 각 시점마다 키가 더 큰 사람과 작은 사람의 리스트 혹은 딕셔너리에 반대 사람을 넣어주고, 최종적으로 자신의 리스트 혹은 딕셔너리에 N-1명의 사람이 있으면 됩니다.

 

풀이는 아래와 같습니다.

[풀이 - 파이썬]

from collections import defaultdict
import sys
input = sys.stdin.readline


def dfs(start, currNode, visited):
    visited[currNode] = True
    for nextNode in graph[currNode]:
        if not visited[nextNode]:
            height[start].add(nextNode)
            height[nextNode].add(start)
            dfs(start, nextNode,visited)


# 각 학생별로 자신보다 키가 큰 사람, 작은 사람을 저장하는 딕셔너리
height = defaultdict(set)
answer = 0
n, m = map(int, input().split())

# 키가 큰 사람에서 작은 방향으로 향하는 간선 그래프
graph = [[] for _ in range(n+1)] 
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

# 자신을 시작점으로 깊이 우선 탐색
# 시작점에서 출발하면서 거친 모든 노드는 시작점보다 키가 작다.
for i in range(1, n+1):
    visited = [False] * (n+1)
    dfs(i, i, visited)

# 자신보다 키가 큰 사람 + 작은 사람의 정보가 N-1명이면 가능
for i in range(1, n+1):
    if len(height[i]) == n-1:
        answer += 1
print(answer)

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class B_2458 {
    static int n, m, answer;
    static List<Integer>[] graph;
    static Map<Integer, List<Integer>> height;

    static void dfs(int start, int currNode, boolean[] visited){
        visited[currNode] = true;
        for(Integer nextNode : graph[currNode]){
            if(!visited[nextNode]){
                height.putIfAbsent(start, new ArrayList<>());
                height.get(start).add(nextNode);
                height.putIfAbsent(nextNode, new ArrayList<>());
                height.get(nextNode).add(start);
                dfs(start, nextNode, visited);
            }
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        height = new HashMap<>();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new ArrayList[n+1];

        for(int i = 0; i < n+1; i++){
            graph[i] = new ArrayList<>();
        }
        // 키가 큰 사람에서 작은 방향으로 향하는 간선 그래프
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
        }
        // 자신을 시작점으로 깊이 우선 탐색
        // 시작점에서 출발하면서 거친 모든 노드는 시작점보다 키가 작다.
        for(int i = 1; i < n+1; i++){
            boolean[] visited = new boolean[n+1];
            dfs(i, i, visited);
        }

        // 자신보다 키가 큰 사람 수 + 작은 사람의 수 == N-1
        for(Map.Entry<Integer, List<Integer>> ee : height.entrySet()){
            if(ee.getValue().size() == n-1){
                answer++;
            }
        }
        System.out.println(answer);
    }
}