[JAVA] SWEA 5643 키 순서

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo 

SW Expert Academy

 

1. 서론

 

그래프 문제다. dfs로 풀었는데... 플로이드 워샬로 풀 수 있는 문제란다. (나중에 풀어봐야지. 안 풀어보겠지만.)

 

2. 문제 풀이

 

학생들의 키가 어쩌고 하지만 문제의 본질을 따져보면 아주 간단한 문제다.

결론은 각 학생마다 연결된 학생들을 구하고 그 학생들이 자신을 제외한 나머지 학생들의 목록과 같으면, 즉 모든 학생의 정보가 있다면 키가 몇 번째인지 알게 되는 것이다.

 

그래서 주어진 값을 이용해서 그래프를 연결하고 각 학생별로 dfs로 방문하면서 방문하는 학생 번호를 시작한 학생 번호의 배열에 저장해줬다.

 

ex) 1번 학생이 5번 학생에게 방문하게 되면 1번학생의 배열에 5번, 5번 학생 배열에 1번을 저장

 

이처럼 서로 교류가 있는 학생을 2차원 배열에 저장해서 각 학생별로 누구와 교류가 있는지 저장한다.

그리고 자신을 제외한 나머지 학생의 정보를 가지고 있는 학생의 수를 cnt 하면 된다.

 

3. 코드 설명

 

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

public class Solution {

	static int n, m, start;
	static boolean[] visit;
	static List<List<Integer>> list, student;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        for (int p = 1; p <= T; p++) {
        	n = Integer.parseInt(br.readLine());
        	m = Integer.parseInt(br.readLine());

        	student = new ArrayList<>();
        	for (int i = 0; i < n; i++)
        		student.add(new ArrayList<>());
        	
        	for (int i = 0; i < m; i++) { //학생들 단방향 그래프 연결
        		StringTokenizer st = new StringTokenizer(br.readLine());
        		student.get(Integer.parseInt(st.nextToken()) - 1).add(Integer.parseInt(st.nextToken()) - 1);
        	}
        	
        	list = new ArrayList<>();
        	for (int i = 0; i < n; i++)
        		list.add(new ArrayList<>());
        	
        	for (int i = 0; i < n; i++) {
        		visit = new boolean[n];
        		start = i;
        		dfs(i);
        	}
        	
        	int cnt = 0;
        	for (int i = 0; i < list.size(); i++)
        		if (list.get(i).size() == n - 1)
        			cnt++;
        	
        	sb.append("#" + p + " " + cnt + "\n");
        }
        bw.write(sb.toString());
        bw.close(); br.close();
    }
    
    public static void dfs(int idx) { //학생마다 어떤 학생과 연결되어 있는지 탐색하면서 저장
    	if (visit[idx]) return;
    	visit[idx] = true;

    	if (idx != start) {
    		list.get(start).add(idx + 1);
    		list.get(idx).add(start + 1);
    	}
    	
    	for (int i = 0; i < student.get(idx).size(); i++) {
    		int x = student.get(idx).get(i);
    		dfs(x);
    	}
    }
}

 

주어진 값을 통해 2차원 리스트로 그래프를 연결한다.

그리고 학생별로 dfs를 돌리는데 이때 자기자신을 제외하고 지나는 경로들을 학생의 배열에 저장한다.

그리고 이때의 학생의 배열 값이 n - 1, 즉 자신을 제외한 나머지 인원의 수와 같으면 모든 학생의 정보를 알고 있는 것이므로 cnt 한다.