[Baekjoon] 2617_구슬 찾기

Gold IV

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

---

< 구슬 찾기 >

 

문제 풀이 

 

ArrayList 2개를 사용해서 n번 구슬보다 무거운 구슬 번호를 저장하고, n번 구슬보다 가벼운 구슬 번호를 저장한다.

그 후 n번 구슬보다 무거운 구슬이 몇 개인지, 가벼운 구슬이 몇 개인지 dfs를 활용하여 구한다. 각 개수가 총 구슬의 개수의 절반이 넘으면 무게가 중간이 될 가능성이 없다.

 

 

 my solution (Java)

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

public class _2617_ { // 구슬 찾기

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

		int n = Integer.parseInt(st.nextToken());
		int m = 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];

		int answer = 0;

		for (int i = 1; i <= n; i++) {
			init(visited);
			visited[i] = true;

			int left = dfs(i, parents, visited, 0);
			if (left > n / 2) {
				answer += 1;
				continue;
			}
			int right = dfs(i, child, visited, 0);
			if (right > n / 2) {
				answer += 1;
				continue;
			}
		}
		System.out.println(answer);
	}

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

	private static void init(boolean[] visited) {
		for (int i = 0; i < visited.length; i++) {
			visited[i] = false;
		}
	}
}

 

Main

변수)
n : 구슬의 개수
m : 저울에 올려 본 쌍의 개수
parents : 구슬보다 무거운 구슬 번호
child : 구슬보다 가벼운 구슬 번호
a, b : a 구슬이 b 구슬보다 무거움
visited : 방문 여부
answer : 무게가 중간이 될 수 없는 구슬의 수

 

- 구슬의 개수(n), 저울에 올려 본 쌍의 개수(m) 입력

- 저울에 올려 본 쌍의 개수(m)만큼 a, b를 입력받아 parents에는 자신보다 무거운 구슬 번호를 저장하므로 b에 a를 저장하고, child에는 자신보다 가벼운 구슬을 저장하므로 a에 b를 저장

- 모든 구슬을 탐색

: visited 배열 초기화 및 시작 구슬 방문 표시

: 자신보다 무거운 구슬의 개수 찾기 위해 dfs 함수 호출 후 그 개수가 전체 구슬 개수의 절반보다 넘으면 무게가 중간이 될 수 없으므로 answer+1 후 다음 구슬로 넘어감

: 자신보다 가벼운 구슬의 개수를 찾기 위해 dfs 함수 호출 후 그 개수가 전체 구슬 개수의 절반보다 넘으면 무게가 중간이 될 수 없으므로 answer+1 후 다음 구슬로 넘어감

- answer 출력

 

dfs

- 매개변수로 들어온 구슬과 연결되어 있으며, 아직 방문하지 않았으면 방문 후 dfs 함수 호출

 

init

- visited 배열 초기화

---

---