[백준 / C언어] 2617번: 구슬 찾기 (DFS 풀이)

https://www.acmicpc.net/problem/2617

2617번: 구슬 찾기

 

난이도: solved.ac 골드 4

 

알고리즘 분류

---

그래프 탐색 (DFS)

 

접근 방법 및 구현

---

무게가 중간이 될 수 없는 구슬은 해당 구슬보다 더 가볍거나 무거운 구슬의 개수가 N / 2개보다 많아야 한다.

더 가볍거나 무거운 구슬의 개수는 DFS를 이용해 구할 수 있다.

입력으로 들어오는 구슬의 관계는 2차원 배열을 이용해 방향그래프로 나타내었다.

 

아래와 같은 입력이 주어진다고 해보자.

7 8 2 1 2 5 3 2 4 3 5 1 6 2 7 4 4 6

이를 그래프로 나타내면 다음과 같다.

 

1번 노드부터 시작해 자기 자신보다 더 가벼운 구슬이 있는지 DFS로 탐색한다.

이때 더 가벼운 구슬이 있다면 변수 cnt를 이용해 하나씩 더해준다.

그리고 더 가벼운 구슬의 입장에서는 더 무거운 구슬이 하나 더 있는 것이므로 해당 구슬보다 더 무거운 구슬의 개수(w.heavy)를 하나 증가시켜 준다.

처음 시작 노드(구슬)에서의 DFS가 끝나면 cnt의 값을 해당 구슬보다 더 가벼운 것의 개수(w.light)에 넣어준다.

 

방향 그래프를 2차원 배열 graph에 입력한 것과 모든 탐색이 끝난 후의 구조체 배열 w의 모습은 아래와 같이 된다.

좌: graph, 우: w

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define MAX 100
 
typedef struct {
	int light;	// 더 가벼운 구슬의 개수
	int heavy;	// 더 무거운 구슬의 개수
} weight;
 
int graph[MAX][MAX];	// 방향 그래프
int visited[MAX];
weight w[MAX];
int N, M, cnt;
 
void DFS(int num);
 
int main() {
	scanf("%d %d", &N, &M);
	int a, b, i, j;
	while (M) {
		// a: 더 무거운 쪽, b: 더 가벼운 쪽
		scanf("%d %d", &a, &b);
		graph[a][b] = 1;
		M--;
	}
 
	for (i = 1; i <= N; i++) {
		cnt = 0;
		for (j = 1; j <= N; j++) {
			if (graph[i][j] && !visited[j]) {
				// j번 구슬보다 무거운 구슬이 하나 더 있는 것이므로
				(w[j].heavy)++;
				cnt++;	// i번 구슬보다 더 가벼운 구슬(j번 구슬)의 개수 하나 추가
				visited[j] = 1;	// 중복 방지
				DFS(j);
			}
		}
		w[i].light = cnt;
		// visited 초기화
		memset(visited, 0, sizeof(visited));
	}
 
	int ans = 0;
	// 더 무거운 구슬이나 더 가벼운 구슬의 개수가 N/2개보다 크면 중간이 될 수 없음
	for (i = 1; i <= N; i++) {
		if (w[i].light > N / 2 || w[i].heavy > N / 2)
			ans++;
	}
	printf("%d", ans);
	return 0;
}
 
void DFS(int num) {
	for (int j = 1; j <= N; j++) {
		if (graph[num][j] && !visited[j]) {
			(w[j].heavy)++;
			cnt++;
			visited[j] = 1;
			DFS(j);
		}
	}
}