[c++] 백준 텀프로젝트(9466), BFS, 반례추가

문제 https://www.acmicpc.net/problem/9466

• 팀을 이루지 못하는 학생 수  구하기.
• 팀을 이루는 조건
  1 -> 3 -> 5 -> 1  :  자기 자신으로 돌아와야 함.
  1 -> 1  :  혼자 팀
• 팀을 못 이루는 조건
  1 -> 3 -> 5 -> 3  :  1은 팀 x
  1 -> 3 -> 5 -> 5  :  1,3은 팀 x

 

풀이

• 위의 조건에서와 같이 현재 n에서 탐색을 할 때, 팀을 이루든 이루지 못하든 무조건 순환루프에 걸리게 되어 있습니다.
• 순환루프에 걸렸을 때, 팀을 이루는 사람과 이루지 못하는 사람을 분리해서 표시를 해주면 됩니다.
• n번째에서 표시를 마치고, n+1번째에서 탐색을 할 시, 1~n번째에서 표시한 사람을 가르킨다면 이 또한 팀을 이루지 못한다고 할 수 있습니다. 이미 앞에서는 구분이 끝나있기 때문에요. 팀을 이룬 그룹에는 더 이상 들어갈 자리가 없습니다(순환이 안되니). 팀을 이루지 못하는 사람도 마찬가지입니다.
• 다시 정리하면,
  1~n까지 사람을 한명씩 팀을 이루는 지 탐색하고, 방문여부를 체크하면서, 팀을 이루는 그룹은 따로 표시를 해줍니다.
  즉, 방문여부는 3가지로 나뉨. (방문 x , 팀 소속 x, 팀 소속 o) 이를 시간초과를 고려해서 코딩해야 합니다.
  탐색이 끝나면 팀을 이루지 못한 사람들만 count합니다. 

 

반례

3 2 3 3 1

5 2 3 4 5 4 3

4 2 3 4 2 2

5 1 1 1 1 1 4

 

코드

• 조건 3가지 체크  :  방문x = 0,  팀 포함x = 번호(i),  팀 포함o = -1 
• 1~n까지의 사람들 각각에 대해서 탐색하여 위의 3가지를 구분하고, 이를 체크합니다.
• 방문하지 않았더라면 run()함수에 반복문을 돌게 되고, 순환루프를 찾습니다.
• 현재 번호 i를 모든 방문여부에 대입하여 체크합니다. 이는 팀 포함x를 우선 체크해두는 것입니다.
• 그리고 또 사이 방문했을시(순환루프), 해당 번호들을 그룹(팀)이 됩니다. 따라서 다르게 체크하기 위해서 -1을 넣어줍니다.
• 이렇게 1~n까지  조건 3가지를 체크했다면, 팀이 없는 사람만 count해주면 됩니다.

더 자세한 설명을 원하신다면 아래 블로그를 참고하세요
https://blog.encrypted.gg/499

[BOJ] 9466번: Term Project

 

알게 된 점

• 여러 조건들을 함축시킬 수 있는 상위 조건을 생각하는게 매우 어려웠습니다.
• 너무 세세하게 코딩을 짜려고 하니 main stream을 놓치는 것 같았고, 문제의 주된 목적과 풀이방향을 잘 설정해야 한다는 것을 알았습니다.

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%ED%85%80%20%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8(9466)%20%EC%9E%AC%EC%8B%9C%EB%8F%84.cpp