가족 찾기

가족 찾기

그래프는 아주 쉬운 문제에서부터 까다로운 문제까지 해결의 실마리를 제공한다. 유명한 외판원 문제나 최소 신장 트리 문제는 아주 어려운 문제이지만 그래프에 효과적인 알고리즘을 적용하여 해결된다. 이번 문제에서는 기본적인 그래프 탐색에 관해 학습하고 자 한다.

문제 ( 난이도 ★★☆☆☆)

 

건수네 학교에서 부모님들과 학생들이 모두 참석한 행사를 하고 있다. 행사 중 모든 사람 들이 모여서 할 수 있는 놀이 중 가족 찾기가 있다. 다만 놀이에 모든 사람이 포함되는 것은 아니고 정사각형을 만들 수 있는 일부 사람들이 놀이에 참가한다. 놀이의 규칙은 다 음과 같다

같은 가족이면 서로 좋아해야 한다. 같은 가족은 2명 이상이다 다른 가족은 서로 싫어한다.

좋아하는 사람을 표시할 때는 1을 표시하고 싫어하는 사람을 표시할 때는 0를 표시한다.

예를 들어 아래와 같이 3명을 나타내는 정사각형은 다음과 같이 해석된다.

1 0 1 첫 번째 사람은 두 번째 사람을 싫어하고 세 번째 사람을 좋아한다.

0 1 0 두 번째 사람은 첫 번째 사람을 싫어하고 세 번째 사람도 싫어한다.

1 0 1 세 번째 사람은 첫 번째 사람을 좋아하고 두 번째 사람을 싫어한다.

따라서 첫 번째 사람과 세 번째 사람은 가족이다.

위와 같은 숫자들이 주어졌을 때 가족의 수와 가족 구성원을 구하는 프로그램을 작성하

시오. 단 사람과 사람관계는 대칭성이 있어 A 가 B를 좋아하면 B도 A를 좋아하고 A가

B를 싫어하면 B도 A를 싫어한다.

프로그램의 이름은 “graph"로 한다.

입력 형식

입력 파일명은 "Input.txt"로 한다. 입력 파일의 첫째 줄에는 사람의 수(n)이 주어진다. 두

번째 줄부터 n+1 줄까지는 사람들의 관계가 숫자로 주어진다.(위 예 참조), 단 숫자 사이

는 공백으로 분리된다.

출력 형식

출력 파일명은 "Output.txt"로 한다. 출력 파일의 첫째 줄에는 가족의 수(m)을 출력하고,

두 번째 줄부터 m+1 줄까지는 가족들의 구성원을 번호로 표시한다. 출력 순서는 가족 구

성원의 숫자합(번호합)이 큰 순서부터 출력하고 각 가족 구성원은 작은 순서부터 출력한 다.

입력과 출력의 예 1

입력의 예(Input.txt)

5

1 0 0 1 1

0 1 1 0 0

0 1 1 0 0

1 0 0 1 1

1 0 0 1 1

출력의 예(Output.txt)

2

1 4 5

2 3

입력과 출력의 예 2

입력의 예(Input.txt)

3

1 0 1

0 1 0

1 0 1

출력의 예(Output.txt)

1

1 3

- 44 -

[초등부] 가족 찾기

문제의 배경 및 관련 이론

그래프(Graph)는 컴퓨터 학문에서 가장 유연한 자료 구조 중 하나이다. 실제로 다소 복잡

하긴 하지만 대부분의 다른 자료구조를 그래프로 표현 할 수 있다. 실제로 컴퓨터 네트워

크, 시스템의 상태를 표시하는 데 그래프가 유용하게 사용되고 있다.

정보 올림피아드 대회에서도 그래프 관련 문제는 자주 등장한다. 기본적으로 그래프 탐색

방법, BFS(너비 우선 탐색, bread-first search), DFS(깊이 우선 탐색, depth-first search)

등은 다양하게 응용되어 출제 되고 있다. 또한 최소 신장 트리를 구하는 Prim의 알고리즘

과 Kruskal 알고리즘, 그래프 상에서 최단 경로를 찾는 Dijkstra의 알고리즘, 휴리스틱을

이용한 외판원 문제 등은 반드시 해결 전략을 가지고 있어야 한다.

이번 문제도 그래프 탐색을 이용하여 문제를 해결할 수 있다. 문제에서 제시된 예제를 그래프로 그려보면 다음과 같다.

 

위 그래프는 각 사람을 노드로 하고 그들 간의 좋고 싫음을 에지로 표현한 것이다. 느꼈겠지만 그래프는 문제 해결을 좀 더 직관적으로 이해할 수 있게 해준다. 이번 문제 역시 위 의 그래프를 하나 하나 따라가면서 이루어지는 싸이클들을 찾아내기만 하면 된다. 물론 어려운 문제에 있어서는 그래프에 알고리즘을 적용시켜야 한다. 이 문제의 해결이 그래프 탐색을 이용한 것만은 아니다. 그래프 문제는 코딩하기 까다로운 면이 있으므로 다른 방법도 강구해 보도록 하자.

문제 해설

1. 그래프를 이용한 방법

위 그래프를 다시 이용하도록 하자

문제의 조건에서 서로 좋아하면 가족이고, 싫어하면 가족이 아니라고 했다. 또한 사람들 사이에는 대칭성이 있다고 했다 따라서 우리가 찾고자 하는 가족은 0으로 연결된 노드들 을 찾으면 된다. (그러나 대칭성이 있으므로 사실 1로 연결된 노드들을 찾으면 된다.) 이제 0 으로 연결된 노드들을 찾기로 하고, 문제에서 제시도니 규칙으로부터 우리는 다음 과 같은 과정과 규칙을 만들 수 있다. 노드 1에서부터 시작한다.

1에서 갈 수 있는 노드에서 0으로 갈 수 있는 노드를 탐색한다. 두 개인 경우 의 임의로 아무 노드나 선택한다. 도착한 노드에서 0으로 갈 수 있는 노드가 1 노드만 존재 한다면 1에서부터 지 금까지 탐색한 노드들이 하나의 가족이다.

2노드에서 다시 시작한다. 만약 2노드가 1노드의 가족이라면 3노드로 이동하 여 과정을 거친다.

모든 노드를 탐색하였다면 프로그램을 종료한다.

위와 같이 예외 처리 없이 간단한 규칙을 얻을 수 있는 이유는 문제에서 제시한 대칭성

때문이다. 따라서 가족이 발견될 때마다 탐색해야 할 노드의 수는 줄어들고 수행 시간 또

한 줄어든다.

소스파일과 테이블 :

가족 찾기.cpp

가족찾기 테이블.xls