마족 찾기

1. 문제

 

2. 문제 분석

이 문제는 BFS방식으로 접근하는 것이 올바르다.

주민의 수가 너무 많아지면, DFS방식에서는 stack overflow가 나타나기 때문이다.

그러나, 여기서는 DFS방식으로도 접근을 해볼것이다.

아래의 구현에서는 Res배열을 하나 선언할 것인데, 선언하는 이유는 아래와 같다.

마을 주민이 3사람이 있다고 하자. (1,2,3 이라고 칭하겠다.)

주민 1번이 마을 주민 2,3,4 번을 지목했다고 하자.

그러면 지목을 받은 주민 2번 주민이 지목을 한다. 3.4.5번 주민을 지목한다고 하자.

그리고, 3번 주민이 지목을 한다. 3번 주민이 2,4,5번을 지목했다고 했을 때,

이미 주민2번이 주민3번을 지목했고, 다시 3번 주민이 2번 주민을 지목한 상황이 되었다.

즉, 위와 같은 상황을 막기 위해서 (중복 지목을 피하기 위해) 선언한 변수이다.

SetRandomNums 함수에서 하는 일을 큰 그림으로 먼저 설명하면 다음과 같다.

지목을 하는데, 자기 자신을 지목하는 상황을 배제해야 하고,

같은 사람을 중복으로 지목하는 상황을 제외 시키면서 데이터를 세팅하는 함수이다.

 

3. 구현

프로그램 실행결과

data.txt파일의 일부분

4. 소스 파일

main.c

0.01MB