SW Expert Academy [Professional] 키 순서 / 백준 2458 키 순서

🅰 SW Expert Academy [Professional] 키 순서

SW Expert Academy

 

 

 

2458번: 키 순서

✏️ 문제 풀이

• 백준의 키 순서 문제와 동일한 문제이다.
• 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성해야 한다.
• 그래프 형식으로 주어지기 때문에 플로이드-와샬을 이용하여 문제를 풀었다.
• 입력 데이터를 2차원 map배열에 저장 해주고, 플로이드-와샬을 이용하여 k를 거쳐서 가는 모든 경우의 수에 대해 최신화 시켜주었다.
• 자신의 키가 몇 번째인지 알 수 있는 학생들의 수를 구하기 위해서는 자기 자신으로 들어오는 그래프 수 + 자신이 가리키는 그래프 수 = 정점수(N)-1이 되어야 한다.
• 플로이드-와샬을 이용하여 최신화 시켜준 그래프를 돌면서 cnt[]배열에 모든 정점에 대한 그래프 수의 합을 구했다.

✏️ 소스코드

package com.ssafy.swexpert.graph;

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

public class Solution_D4_5643_키순서 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			// 데이터 입력
			int N = Integer.parseInt(br.readLine());
			int M = Integer.parseInt(br.readLine());
			int map[][] = new int[N + 1][N + 1];
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if (i == j)	// 자기 자신이면
						map[i][j] = 0; // 갈수없음(0) 저장
					else
						map[i][j] = 100000; // 나머지 큰 값 저장
				}
			}
			for (int i = 1; i <= M; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				map[a][b] = 1;	// a->b 갈 수 있음(1) 표시
			}

			for (int k = 1; k <= N; k++) { // 플로이드-와샬 
				for (int i = 1; i <= N; i++) { 
					for (int j = 1; j <= N; j++) {
						// 모든 케이스에 대해 i에서 j 가는데 k를 거쳐서 가는 경우를 비교하여 더 적은 값 저장
						map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
					}
				}
			}
			
			// 키를 알 수 있는 경우를 구하기 위해서 자기 자신으로 들어오는 그래프 수와, 자기가 가리키는 그래프 수의 합이 N(정점)-1이 되어야 한다.
			int ans = 0; // 자신의 키가 몇번째 인지 아는 학생들의 수
			int cnt[] = new int[N + 1]; // 모든 학생의 들어오는 그래프, 가리키는 그래프 수의 합 저장할 배열
			int self = 0; // 자기자신이 가리키는 그래프 수를 저장할 변수
			for (int i = 1; i <= N; i++) { 
				for (int j = 1; j <= N; j++) {
					if (map[i][j] == 0 || map[i][j] == 100000) // 자기 자신과 연결되어 있지 않은 그래프는 pass
						continue;
					self++; // 자신이 가리키는 그래프 ++
					cnt[j]++; // 자신이 가리키는 그래프++ (상대 입장에서는 들어오는 그래프++)
				}
				cnt[i] += self; // 자신이 가리키는 그래프의 수를 자기자신의 배열에 저장
				self = 0;
			}
			for (int i = 1; i <= N; i++) {
				if (cnt[i] == N - 1) // 자기자신의 연결,가리키는 그래프의 합이 N-1일때 
					ans++; //ans++
			}
			System.out.println("#" + test_case + " " + ans);
		}
	}
}

 

✅ 후기

• 그래프 문제라는것은 알았지만 어떠한 방식을 이용해서 풀지에 대해 고민을 많이 했다. 이번에 그래프를 공부하면서 그래프를 푸는 방법에 대해 모두 정리하고 어느 문제에 어떤 방식을 이용해야 잘 풀 수 있을지 깨닫도록 노력해야겠다.