문제 바로가기

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

문제 소개 및 재정의

1. 1~n번의 학생들이 있다.
2. 각 학생들의 키는 모두 다르다.
3. 학생들을 둘씩 짝지어 키 크기를 비교한 M개의 데이터가 주어진다.
4. 보다 작은 키를 가진 학생의 번호 보다 큰 키를 가진 학생의 번호
5. M개의 데이터를 토대로 자신의 키가 몇등인지 알수있는 학생의 수를 구한다.

문제 패턴

M개의 데이터는 학생 두명을 한정해서 그 둘의 키를 오름차순으로 나열한 데이터로 방향을 가진다.
이렇게 방향이 일정한 노드(학생)쌍을 데이터로 제공하는 것이 위상정렬 문제의 패턴이다.
방향이 일정한 노드쌍을 토대로 그래프를 표현하면 DAG가 되기 때문이다.
DAG (directed acyclic graph:유향 비순환 그래프)

하지만 이 문제는 위상정렬 문제가 아니다.

어떻게 풀까? - BFS | DFS

해결 방법

한 학생을 기준으로

진출간선을 타고 다른 노드로 가는 BFS|DFS 탐색시
자신보다 큰 사람이 누군지와 몇명(taller)있는지 알 수 있다.

진입간선을 역으로 거슬러 올라가서 다른 노드로 가는 BFS|DFS 탐색시
자신보다 작은 사람이 누군지와 몇명(shorter)있는지 알 수 있다.

taller + shorter = N-1 일때 자신이 몇등인지 알수있다.
다시 말해서, DAG를 정방향 역방향으로 구현 후. (인접리스트 사용)
DFS/BFS로 모든 노드 방문 성공시 자신이 몇등인지 알수있다.

시간복잡도

노드별 시간복잡도 : O(N) (모든 노드를 방문해야 하므로)
노드의 개수 = N개
총 시간 복잡도 = O(N*N) = O(N^2)
문제에서의 O(N) = 500
문제에서의 총 시간 복잡도 = 25,000

코드

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

public class SWEA_5643_키_순서 {
	
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static StringBuilder output = new StringBuilder();
	
	
	// 세팅
	static int N;
	static int M;
	static ArrayList<ArrayList<Integer>> fromToNodeList;
	static ArrayList<ArrayList<Integer>> toFromNodeList;
	
	static int globalCount;		// 테케별 초기화
	static boolean[] visited;	// 사이클별 초기화
	
	// 메소드
	static void DFS(int node, final ArrayList<ArrayList<Integer>> nodeList) {
		// 방문시 방문처리
		visited[node] = true;
		
		// 바닥 조건
		if(nodeList.get(node).size()==0) { // 다음 노드로 가는 간선이 없으면 맨 마지막까지 도달한 것
			return;
		}
		
		// 재귀 파트
		for (int i = 0; i < nodeList.get(node).size(); i++) {
			int next = nodeList.get(node).get(i);
			if(visited[next]) { // 이미 방문한 노드면 지금 차례 점프
				continue;
			}
			DFS(next, nodeList);// 미방문 노드만 이 시점에 도달가능
		}
	}
	static void BFS(int node, final ArrayList<ArrayList<Integer>> nodeList) {
		// init
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(node);
		visited[node] = true;
		// 반복
		while(q.isEmpty()==false) {
			int nowNode = q.poll();
			for (int i = 0; i < nodeList.get(nowNode).size(); i++) {
				int nextNode = nodeList.get(nowNode).get(i);
				if(visited[nextNode]) {
					continue;
				}
				q.offer(nextNode);
				visited[nextNode] = true;
			}
		}
	}
	
	// 메인
	public static void main(String[] args) throws Exception {
		
		int T = Integer.parseInt(input.readLine());
		for (int t = 0+1; t < T+1; t++) {
			// 테케별 입력
			N = Integer.parseInt(input.readLine());
			M = Integer.parseInt(input.readLine());
			
			//// 방향별 DAG 인접리스트 초기화
			fromToNodeList = new ArrayList();
			toFromNodeList = new ArrayList();
			for (int i = 0; i < N; i++) {
				fromToNodeList.add(new ArrayList());
				toFromNodeList.add(new ArrayList());
			}
			//// 인접리스트에 저장
			for (int i = 0; i < M; i++) {
				tokens = new StringTokenizer(input.readLine());
				int from = Integer.parseInt(tokens.nextToken())-1; // 노드번호 => 인덱스 번호로 만들기 위해서 -1 해주기
				int to = Integer.parseInt(tokens.nextToken())-1;
				fromToNodeList.get(from).add(to);
				toFromNodeList.get(to).add(from);
			}
			
			// 테케별 세팅
			visited = new boolean[N];
			globalCount = 0;
			
			// 테케별 작업
			for (int node = 0; node < N; node++) {
				Arrays.fill(visited, false);
				
//				DFS(node, fromToNodeList);
//				DFS(node, toFromNodeList);
				
				BFS(node, fromToNodeList);
				BFS(node, toFromNodeList);
				
				boolean isOK = true;
				for (int i = 0; i < N; i++) {
					isOK = isOK && visited[i];
				}
				if(isOK) {
					globalCount++;
				}
			}
			
			// 테케별 출력
			output.append("#").append(t).append(" ").append(globalCount).append("\n");
			
		}// 모든 테케 종료
		// 정답 출력
		System.out.println(output);
	}// 메인 종료

}

퍼포먼스 비교

BFS 탐색 : ["98,320"KB | "2,483"ms]

DFS 탐색 : ["91,476"KB | "2,197"ms]