[백준] 2617번 : 구슬 찾기

문제

 

 

접근 방식

각각의 구슬을 정점, 두 구슬의 대소 관계를 간선이라고 했을 때

정점 X에서 Y로 갈 수 있다면 구슬 X가 구슬 Y보다 무겁다는 것을 알 수 있다.

 

하지만 단방향 그래프로 인접 행렬을 표현하니 대소 관계가 제대로 처리가 되지 않고

일반적인 양방향으로 표현하자니 어느 구슬이 무거운지를 알 수가 없는 문제가 있었다.

 

그래서 인접 행렬을 만들 때 구슬 X가 Y보다 무겁다면

정점 X에서 Y로 갈 수 있는 것을 표시할 때 1로 표시를 해주고

구슬 X가 Y보다 가볍다면 -1로 표시를 해주었다.

 

그 후 각 구슬마다 DFS로 탐색을 해주면서

다음 방문할 정점이 1인지 -1인지에 따라

각 수마다 더 큰 수와 작은 수의 개수를 카운트 해주고

모든 정점에 대한 탐색이 끝나면 카운트를 저장해둔 배열을 순회하며

X보다 무겁거나 가벼운 구슬의 개수가 (n+1)/2 이상이면

중간값이 될 수 없다는 것을 알 수 있다.

 

풀이

public class Main {

	private static int n;
	private static int next;
	private static int[][] near;
	private static int[][] count;
	private static boolean[] isVisited;

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

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

		near = new int[n + 1][n + 1];
		count = new int[n + 1][2];

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			near[x][y] = 1;
			near[y][x] = -1;
		}

		for (int i = 1; i <= n; i++) {
			isVisited = new boolean[n + 1];
			dfs(i, i, 0);
		}

		int max = 0;
		int mid = (n + 1) / 2;

		for (int i = 1; i <= n; i++) {
			if(count[i][0] >= mid || count[i][1] >= mid) max++;
		}

		System.out.println(max);
	}



	private static void dfs(int start, int cur, int x) {
		isVisited[cur] = true;
		if(x != 0) count[start][x == 1 ? 0 : 1]++;

		for (int i = 1; i <= n; i++) {
			next = near[cur][i];
			if (isVisited[i] || next == 0) continue;
			if (x != 0 && next != x) continue;
			dfs(start, i, next);
		}
	}
}