SWEA_5643 키 순서(자바) / BFS , DFS , 플로이드 워셜

문제 링크

SW Expert Academy

이 문제의 경우는 각각의 학생이 키에 대한 값정보는 주지 않고 누가 누구보다 큰지에 대한 정보만을 줍니다.

 

이때 몇명의 학생이 자신의 키가 몇번째 인지를 알 수 있는 사람에 대해서 결과를 출력하는 문제입니다.

 

이 문제의 경우 여러 방법으로 풀 수 있습니다.

 

이 문제는 연습하기 좋은 문제입니다..

 

BFS를 이용한 문제풀이

package com.Expert;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Expert_5643 {
	static int N,M,map[][];
	static int link,ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int testCase = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <=testCase; tc++) {
			N = Integer.parseInt(br.readLine());
			M = Integer.parseInt(br.readLine());
			map = new int[N+1][N+1];
			for (int i = 1; i <= M; i++) {
				st = new StringTokenizer(br.readLine()," ");
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				map[x][y]=1;
			}
			ans=0;
			for (int i = 1; i <= N; i++) {
				link=0;
				bfs(i);
				if(link==N-1)ans++;
			}
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	private static void bfs(int k) {
		Queue<Integer> q = new LinkedList<>();
		boolean[] visited = new boolean[N+1];
		q.add(k);
		visited[k]=true;
		//나보다 큰 사람
		while(!q.isEmpty()) {
			int temp = q.poll();
			for (int i = 1; i <= N; i++) {
				if(map[temp][i] == 1 && !visited[i]) {
					q.add(i);
					visited[i]= true;
					link++;
				}
			}
		}
		visited = new boolean[N+1];
		q.add(k);
		visited[k]=true;
		//나보다 작은 사람
		while(!q.isEmpty()) {
			int temp = q.poll();
			for (int i = 1; i <= N; i++) {
				if(map[i][temp] == 1 && !visited[i]) {
					q.add(i);
					visited[i]= true;
					link++;
				}
			}
		}
	}
}

 

DFS를 이용한 문제풀이

package com.Expert;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Expert_5643 {
	static int N,M,map[][];
	static int link,ans;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int testCase = Integer.parseInt(br.readLine());
		
		
		for (int tc = 1; tc <=testCase; tc++) {
			N = Integer.parseInt(br.readLine());
			M = Integer.parseInt(br.readLine());
			map = new int[N+1][N+1];
			for (int i = 1; i <= M; i++) {
				st = new StringTokenizer(br.readLine()," ");
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				map[x][y]=1;
			}
			ans=0;
			for (int i = 1; i <= N; i++) {
				link=0;
				visited = new boolean[N+1];
				dfsR(i);
				visited = new boolean[N+1];
				dfsL(i);
				if(link==N-1)ans++;
			}
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	private static void dfsR(int cur) {
		visited[cur] = true;
		// 나보다 큰 사람
		for (int i = 1; i <= N; i++) {
			if (map[cur][i] == 1 && !visited[i]) {
				dfsR(i);
				link++;
			}
		}
	}
	private static void dfsL(int cur) {
		visited[cur] = true;
		// 나보다 큰 사람
		for (int i = 1; i <= N; i++) {
			if (map[i][cur] == 1 && !visited[i]) {
				dfsR(i);
				link++;
			}
		}
	}
}