9466 텀 프로젝트

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

1.접근

문제의 표를 보면 꼬리를 무는 사이클을 찾아야하는 것을 알 수 있다. 따라서 DFS나 while문을 통해 돌면서 사이클이 생기는 곳을 체크해주면 되겠다.

 

2.풀이

문제의 사이클에 대해서 생각해보자. 어느 부분에서라도 DFS를 통해 들어갔을때 꼬리를 물어서 사이클이 생기지 않는다면 방문했던 곳들은 어디서 들어가도 사이클이 생기지 않을 것이다. 하지만 어느 부분에서라도 사이클이 생기는 곳이라면 들어갔을 때 자기자신까지 돌것이다. 이 문제에서 가장 중요하다고 생각되는 것은 DFS나 while문을 돌 때 사이클이 되는 곳과 사이클이 되지않는 곳을 분류하는 것이다.

예를 들어서 1>>2, 2>>3, 3>>4, 4>>3 를 가르킨다고 해보자. DFS를 1에서 시작했다고 가정하면 1->2->3->4->3의 과정으로 3,4가 사이클을 만든다는 것을 알 수 있고 여기서 또 1,2는 사이클을 만들지 못한다는 정보까지 알 수 있다.

따라서 이 과정에서 나는 두번의 while문을 통하여 반복이 시작된 3이 나올때까지의 count를 해서 사이클이 되지않는 곳을 찾았다.

 

3.코드

 

4.배운점

• 배열의 상태가 여러 상태로 분류될수 있을때는 맘먹고 visited배열과 같은 상태를 나타내는 배열을 하나 더 선언하자.(visietd배열로 숫자놀이하는 것 보다 속 편함)

• 중복되는 부분을 찾으려면 배열에 순서대로 넣어서 처음으로 다시나온 배열의 인덱스를 체크하는 방법이나 while문을 사용하여 한번더 돌아봐서 중복되는 부분이 나올때까지의 count를 해주면 되었다.

• 문제를 풀고 다른 사람들의 풀이를 보니 최근에 배운 위상정렬느낌으로 문제를 풀어가도 되었다. 사이클이 없는 곳이 향하는 간선을 지워주는 느낌