[Baekjoon] 17616_등수 찾기

Gold III

문제(출처: https://www.acmicpc.net/problem/17616)

---

< 등수 찾기 >

 

문제 풀이 

 

입력을 받을 때 ArrayList 2개를 사용해서 자신보다 더 잘한 사람과 자신보다 더 못한 사람을 저장한다.

dfs를 활용하여 자신보다 잘 한 사람의 수와 자신보다 못한 사람의 수를 구해 가능한 가장 높은 등수와 가능한 가장 낮은 등수를 구한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class _17616_ { // 등수 찾기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());

		ArrayList<ArrayList<Integer>> parents = new ArrayList<>();
		ArrayList<ArrayList<Integer>> child = new ArrayList<>();
		for (int i = 0; i < n + 1; i++) {
			parents.add(new ArrayList<>());
			child.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			parents.get(b).add(a);
			child.get(a).add(b);
		}

		boolean visited[] = new boolean[n+1];
		visited[x] = true;

		int start = dfs(x, parents, 0, visited);
		int end = dfs(x, child, 0, visited);

		bw.write((start + 1) + " " + (n - end));
		bw.flush();
	}

	private static int dfs(int x, ArrayList<ArrayList<Integer>> arr, int count, boolean[] visited) {
		for (int i = 0; i < arr.get(x).size(); i++) {
			if (!visited[arr.get(x).get(i)]) {
				visited[arr.get(x).get(i)] = true;
				count+=dfs(arr.get(x).get(i), arr, 1, visited);
			}
		}
		return count;
	}
}

 

 

Main

변수)
n : 학생 수
m : 질문 수
x : 등수를 알고 싶은 학생 
parents : 자신보다 잘한 사람 저장
child : 자신보다 못한 사람 저장
a, b : 학생 a가 학생 b보다 더 잘함
visited : 방문 여부
start : x보다 잘 한 사람 수
end : x보다 못한 사람 수

 

- 학생 수(n), 질문 수(m), 등수를 알고 싶은 학생(x) 입력

- 질문 수(m)만큼 학생 a, b를 입력받아 parents에는 자신보다 잘한 사람을 저장하므로 b에 a를 저장하고, child에는 자신보다 못한 사람을 저장하므로 a에 b를 저장

- 자신보다 잘한 사람의 수와 못한 사람의 수를 구하기 위해 dfs 함수 2번 호출

- 정답 출력 [자신보다 잘한 사람의 수 +1, 학생 수 - 자신보다 못한 사람의 수]

 

dfs

- 자신과 연결된 사람들이며, 아직 방문하지 않았으면 방문 후 dfs 함수 호출

---

---