[백준 / BOJ] 9466 텀 프로젝트

문제

출처 : www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

문제 해결 강의를 신청한 학생들은 텀 프로젝트를 수행해야한다.

각 학생들마다 팀을 하고싶은 학생이 다르고, 한 학생이 한명의 학생만 선택할수있다.

학생들의 팀원선택이 사이클을 이루면 해당 학생들은 팀을 이뤘다고할때, 팀을 이루지못한 학생들의 수를 구하는 문제다.

 

풀이

학생들의 사이클을 찾으면 되는 문제인데, 시간초과를 조심해야한다.

 

풀이의 핵심은 한 학생을 기준으로 그룹을 찾을때마다, 해당 그룹안에 포함된 학생을 모두 찾아줘서 반복을 없애는것이다.

 

코드는

1. 현재 학생이 팀을 이루고 있지않다면, 재귀로 들어간다.

 

2. 이때, 사이클을 찾는다면, 사이클을 이루는 지점을 target으로 설정한다.

예를들어,재귀 시작 위치는 1이고 빨강색 글자가 사이클을 이룬다고 하자.(1 -> 2 -> 3 -> 4 -> 2) 4까지 들어갔을때 2 -> 3 -> 4 -> 2 가 사이클을 이룬다는 것을 알수있고 target을 2로 설정한다.

 

3. 재귀를 풀어가며 2 3 4의 그룹 상태를 true로 바꾼다. (그룹을 이룸) 이때, target이 2이므로 2가 나오면 2뒤의 숫자들은 false로 바꾼다. (재귀로 구현해서 해체도 순차적으로 하기때문에 target뒤의 수는 항상 사이클 밖이다.)

 

4. 재귀를 들어가다 이미 그룹을 이루고있거나, 앞의 수에의해서 방문된 숫자일경우 재귀를 해체하며 지나온 숫자들을 전부 false로 바꾼다.

 

이렇게 하면, 이미 그룹을 이룬 학생은 다시 보지않기때문에,

그룹에 포함안된 학생 찾는데 걸리는시간 : N

한 학생을 기준으로 같은 그룹에 있는 학생 찾는데 걸리는시간 : N

만큼 걸리므로 O(2N)반복으로 풀수있다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/9466%20%ED%85%80%20%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8/main.cpp

devxb/JJUNalgo