[백준 2458] 키 순서(Java)

최민길(Gale)·2023년 5월 24일
1

문제 링크 : https://www.acmicpc.net/problem/2458

이 문제는 dfs를 이용하여 풀 수 있습니다. 이 문제에서 요구하는 내용을 정리하면 다음과 같습니다. 자신의 키가 몇 번째인지 알 수 있는 학생이라면 자신의 노드에서 시작해서 모든 노드로 접근이 가능하다는 것을 의미합니다. 이 때 자기 자신에서 출발하는 방향과 자기 자신으로 향하는 방향으로 dfs를 시행했을 때 방문하는 노드의 수가 전체 학생 수와 같은 경우 자신의 키가 몇 번째인지 알 수 있습니다.

문제 푸는 전략은 다음과 같습니다. 우선 자기 자신에서 출발하는 그래프와 자기 자신으로 도착하는 그래프 2개를 설정합니다. 각 그래프에 노드와 간선을 설정한 후 dfs를 이용하여 i번 노드에서 두 그래프를 각각 진행 시 몇 개의 노드를 방문하는지를 체크합니다. 이 때 방문한 노드와 전체 학생 수가 같으면 정답을 증가시키는 방식으로 구현할 수 있습니다.

다음은 코드입니다.

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

class Main{

    static boolean[] check;
    static void dfs(ArrayList<Integer>[] graph, int curr){
        if(!check[curr]) check[curr] = true;

        ArrayList<Integer> list = graph[curr];

        for(int i=0;i<list.size();i++){
            if(!check[list.get(i)]) dfs(graph,list.get(i));
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 자기 자신으로 들어오는 경로
        ArrayList<Integer>[] in = new ArrayList[N+1];
        // 자기 자신에서 나가는 경로
        ArrayList<Integer>[] out = new ArrayList[N+1];

        for(int i=1;i<=N;i++){
            in[i] = new ArrayList<>();
            out[i] = new ArrayList<>();
        }

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int fin = Integer.parseInt(st.nextToken());

            out[start].add(fin);
            in[fin].add(start);
        }

        int res = 0;
        for(int i=1;i<=N;i++){
            check = new boolean[N+1];

            dfs(out,i);
            dfs(in,i);

            int val = 0;
            for(int j=1;j<=N;j++)
                if(check[j]) val++;
            if(val == N) res++;
        }
        System.out.println(res);
    }
}
profile
저는 상황에 맞는 최적의 솔루션을 깊고 정확한 개념의 이해를 통한 다양한 방식으로 해결해오면서 지난 3년 동안 신규 서비스를 20만 회원 서비스로 성장시킨 Software Developer 최민길입니다.

0개의 댓글