[SWEA] 5643 키 순서 (D4 / 플로이드 워셜) - Java

링크

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

SW Expert Academy

 

 

 

문제 해석

키 정보는 A라는 학생과 B라는 학생의 키가 크고 작음을 나타냄

 

키를 비교할 N명이 존재하고, M개의 키 정보가 주어졌을 때,

자신의 키 순서가 몇 번째인지 알 수 있는 학생의 수를 구하라

 

 

- 설명

키 순서가 몇 번째 인지를 확인한다는 것은 바꿔 말하자면,

나보다 키가 큰 사람이 몇 명인지, 그리고 나보다 키가 작은 사람이 몇 명인지를 알 수 있으면 확인 가능합니다.

 

 

 

- 입력

첫 번째 줄 : N  # 학생 수

두 번째 줄 : M  # 관계 수

나머지 줄 : i j  # i에서부터 j까지로의 관계 표현

 

- 출력 

키 순서를 아는 학생 수 출력

 

 

 

코드

package day05;

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

public class 키순서 {

	static int N, M;

	static int[][] map; // 인접 행렬

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

		int T = Integer.parseInt(st.nextToken());
		for (int test_case = 1; test_case <= T; test_case++) {
			// 첫 번째 줄
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			// 두 번째 줄
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());

			int INF = 99999; // 무한한 값

			map = new int[N][N];
			for (int i = 0; i < N; i++) {
				Arrays.fill(map[i], INF);
			}

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int start = Integer.parseInt(st.nextToken()) - 1;
				int end = Integer.parseInt(st.nextToken()) - 1;
				map[start][end] = 1;
			}

			// 플로이드 워셜 : 경출도
			for (int k = 0; k < N; k++) {
				for (int i = 0; i < N; i++) {
					// 경우-출발이 동일한 경우
					if (k == i)
						continue;
					for (int j = 0; j < N; j++) {
						if (i == j || j == k)
							continue;
						if (map[i][j] > map[i][k] + map[k][j]) {
							map[i][j] = map[i][k] + map[k][j];
						}
					}
				}
			}

			int answer = 0;
			int[] count = new int[N];
			// i와 관계가 있는 인원을 찾음
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					// 행에 연관된 값이 있는 경우 : i보다 큰 j가 존재하는 경우
					if (map[i][j] != INF) {
						count[i] = count[i] + 1;
					}
					// 열에 연관된 값이 있는 경우 : j보다 작은 i가 존재하는 경우
					if (map[j][i] != INF) {
						count[i] = count[i] + 1;
					}
				}
			}

			// i와 관계 있는 인원이 N-1이라면 i는 모든 인원과 관계를 가지는 것임
			for (int i = 0; i < N; i++) {
				if (count[i] == N - 1) {
					answer++;
				}
			}

			System.out.println("#" + test_case + " " + answer);
		}
	}

	private static void print(int[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

 

 

 

코드 해석

플루이드 워셜을 통해서 사람의 관계를 표현하였습니다.

 

99999 2 99999 2 1 3 
99999 99999 99999 99999 99999 99999 
99999 2 99999 1 99999 2 
99999 1 99999 99999 99999 1 
99999 1 99999 1 99999 2 
99999 99999 99999 99999 99999 99999 

 

첫 번째 테스트 케이스를 플루이드 워셜로 돌렸을 때 나오는 결과입니다.

 

 

플루이드 워셜로 결과를 도출 했을 때 map[i][j]는 i보다 j가 크다라는 것을 의미합니다.

반대로 map[j][i]는 j보다 i가 크다 (== i가 j보다 작다)라는 것을 의미합니다.

 

 

위와 같은 내용을 인식하고,

0번째 행을 보시면 1, 3, 4, 5번 행의 사람이 INF가 아닌 값을 가지며, 이는 0번째 사람보다 큰 사람들을 의미합니다.

(1이면 나보다 큰 것을 직접적으로 알 수 있는 경우, 2이상이면 나보다 큰 것을 간접적으로 알 수 있는 경우)

 

반대로 0번째 열을 보시면 모두 INF 값으로 되어 있으므로, 나보다 키가 작은 사람은 없다 or 알 수 없다는 것을 의미합니다. 

 

0번째 사람과 관계를 가지는 사람의 수(나보다 작은 사람 + 나보다 큰 사람)가 N-1이라면 모든 사람과의 관계를 알 수 있다는 의미가 되므로 answer를 증가시켜줍니다.

 

 

발생한 문제 & 해결 방안

열의 관계가 있을 때(map[j][i] != INF) count[i]를 증가시켜 주었어야 했는데 count[j]를 증가시키면서 오류가 발생하였다.

 

결과적으로 i와 연관된 키가 작은 인원을 찾는 것이라 count[i]의 결과값을 증가시켜주는 것이 맞다.

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice