[BOJ] 9466번: Term Project

유튜브 링크 https://www.youtube.com/watch?v=yPuow6aACvE

 

문제의 첫 번째 예시는 그림으로 나타내면 이렇습니다. 화살표는 함께하고 싶은 학생을 향해 뻗어갑니다. 이 그림은 조금 알아보기 힘듭니다. 그림을 조금 바꿔보겠습니다.

 

이렇게 그래프로 나타내면 훨씬 더 직관적으로 알아보기 편합니다. 문제에서

 

---

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

---

 

라고 설명이 되어있는 부분은 이 그림에서 (3) 혹은 (6 4 7)로 이루어진 사이클을 의미합니다. 사이클에 포함되지 않은 2, 1, 5가 바로 어느 프로젝트 팀에 속하지 않은 학생의 수입니다.

 

이 문제의 임의의 입력을 그래프로 나타낸다고 치면 이렇게 사이클이 있고, 사이클 주변에는 일방적으로 사이클로 들어오는 선들이 있는 형태가 됩니다. 왜 이런 형태가 되는지 납득이 잘 가지 않는다면 다음 슬라이드를 확인해봅시다.

 

아무 학생이나 시작으로 잡아서 프로젝트를 함께하고 싶은 학생으로 계속 이어나가면 위와 같은 그림이 됩니다. 계속 새로운 학생이 나오다가 기존에 나왔던 학생이 나오는 순간 사이클이 만들어지고 전 슬라이드에서 나온 상황이 만들어집니다.

 

만약 비슷한 상황에서 다른 사이클에 포함된 학생이 나온다면 일방적으로 사이클로 들어오는 선이 나오게 됩니다. 그렇기 때문에 이 문제의 상황을 그래프로 나타냈을 때 사이클이 있고, 사이클 주변에는 일방적으로 사이클로 들어오는 선들이 있는 형태가 됩니다.

 

먼저 O(N^2) 풀이부터 고민해봅시다. 빨간색 학생은 사이클에 포함되어 있지 않고 또 파란색 학생은 사이클에 포함되어 있다는걸 구분하는 방법을 생각해내야 하는데, 이렇게 그래프를 한 눈에 볼 수만 있다면 굉장히 쉽지만 우리는 알고리즘으로 이걸 해결해야하니 고민이 필요합니다.

 

사실 시간복잡도에 크게 연연하지 않는다면 구분은 굉장히 쉽습니다. 사이클에 포함되어있지 않은 빨간색 학생에서 출발해 계속 다음 학생으로 가봅시다. 그러면 그림에서 볼 수 있듯 언젠가는 사이클 안에 자연스럽게 진입하고, 사이클 안을 돌다가 이미 방문한 학생을 또 방문하게 됩니다. 이렇게 최초로 다시 방문하는 학생은 자기 자신이 아니게 됩니다.

 

반면 사이클에 포함된 파란색 학생에서 출발해 계속 다음 학생으로 간다면 최초로 다시 방문하는 학생이 자기 자신이 됩니다.

 

학생의 수가 N명일 때 만약 사이클에 포함된 학생에서 출발을 해 계속 다음 학생으로 간다면 사이클의 크기는 최대 N이기 때문에 N번 이내에 자기 자신으로 돌아옵니다. 반면 사이클에 포함되지 않은 학생에서 출발을 해 계속 다음 학생으로 간다면 아무리 많이 진행을 해도 자기 자신으로 돌아올 수 없습니다. 위의 그림에서 본 것 처럼 방문 체크를 통해 최초로 다시 방문하는 학생이 자기 자신인지를 이용해서 코드를 작성해도 되고 그냥 마음 편하게 N번 이내에 자기 자신으로 돌아오는지 여부를 확인해도 됩니다. 후자가 더 구현이 편하니 후자로 코드를 작성해보겠습니다.

 

iscycle 함수는 위에서 언급한 것과 같이 N번 이내에 자기 자신으로 돌아오는지 여부를 이용해 idx번째 학생이 사이클에 들어있는지를 판단하는 함수입니다.

 

이렇게 구현을 하면 답은 잘 나오지만 시간복잡도는 O(N^2)입니다. 예를 들어 크기 N의 사이클이 있는 상황이라면 모든 학생이 N번 이동을 진행해야 하니 쉽게 시간 초과를 만들어낼 수 있습니다.

 

 

지금의 O(N^2) 풀이는 이미 방문한 루트를 또 다시 방문한다는 문제점이 있습니다. 예를 들어 빨간색 학생에서 출발해서 사이클 여부를 확인하기 위해서 이동을 하는 계산을 해서 사이클이 아니라는걸 알았다고 해봅시다. 그 이후에 보라색 학생은 사실 이동을 하다가 빨간색을 만난 순간 이미 사이클이 아님을 알 수 있습니다. 그러나 O(N^2) 풀이에서는 그런걸 신경쓰지 않고 이미 빨간색이 지나온 길을 그대로 또 다시 진행합니다.

 

그렇기 때문에 O(N)으로 발전시키기 위해서는 이전의 방문을 이용하는 아이디어가 필요합니다. 이 방문을 이용하기 위해서는 방문 체크가 필요하고, 방문 체크를 사용하기 때문에 제가 이 문제를 BFS 단원에 넣어뒀었습니다.

 

다시 한 번 빨간색 학생에서 다음 학생으로 이동하는 상황을 생각해봅시다. 이번에는 방문 표시를 남기면서 진행해봅시다.

 

그 과정에서 빨간 별이 있는 칸과 같이 이전에 방문했던 학생을 또 방문하는 일이 발생한다면 우리는 빨간색 학생이 사이클에 포함되어 있지 않음을 알 수 있습니다. 이 정보를 이용해 O(N^2)에 풀이를 해낼 수 있었지만 빨간색 학생이 사이클에 포함되어 있지 않다는 것에서 그치지 않고 추가적인 정보를 얻을 수 있다는 점을 알아낼 수 있어야 합니다.

 

이전에 방문했던 학생을 다시 방문했다면 그 학생은 사이클에 포함된 학생입니다. 그 학생에서 출발해 다시 한 번 다음 학생으로 이동하는 작업을 하는데, 이번에는 지금 방문하는 학생들이 전부 사이클에 포함된 학생이라는 표시를 남기면서 이동합니다. 이렇게 하면 우리는 사이클을 찾아낼 수 있습니다.

 

이후 남아있는 학생들에 대해 사이클에 포함되어 있지 않은 학생이라는 표시를 남기면 됩니다. 이건 빨간색 학생에서 사이클에 포함된 학생을 만날 때 까지 다시 한 번 다음 학생으로 이동하는 작업을 해주면 됩니다.

 

이렇게 표시를 남기고 나면 표시를 이용해서 효율적으로 문제를 풀 수 있습니다. 하단에 있는 초록색 학생에서 다음 학생으로 이동하는 작업을 해보면 어떻게 될지 고민을 해봅시다.

 

이렇게 진행을 하다가 사이클에 포함된 학생에 도달을 한 순간 지금까지 방문한 학생은 사이클에 포함되어 있지 않음을 알 수 있습니다.

 

그렇기 때문에 두 학생을 사이클에 포함되어있지 않은 학생으로 바꾸면 됩니다.

 

왼쪽의 주황색 학생에 대해서도 마찬가지 상황입니다. 진행을 하다가 사이클에 포함되어 있지 않은 학생에 도달한 순간 자신이 사이클에 포함되어 있지 않은 학생임을 알 수 있습니다.

 

그렇기 때문에 사이클에 포함되지 않은 학생이라고 값을 매깁니다.

 

 

임의의 학생 x에서 시작해 다음 학생으로 계속 이동할 때
1. 사이클에 포함된 학생 혹은 사이클에 포함되지 않은 학생을 재방문했을 경우 x는 사이클에 포함되지 않은 학생이다. 지금까지 방문한 학생들을 사이클에 포함되지 않은 학생으로 분류한다.

2. x가 아닌 다른 방문한 학생 y를 재방문했을 경우 x는 사이클에 포함되지 않고 y는 사이클에 포함되어 있다. y에서 출발해 이동하며 다시 y에 도달할 때 까지 만나는 학생들을 사이클에 포함된 학생으로 만들고, x에서 출발해 이동하며 y에 도달할 때 까지 만나는 학생들을 사이클에 포함되지 않은 학생으로 만든다.

3. x를 재방문했을 경우 x는 사이클에 포함된 학생이다. x에서 출발해 이동하며 다시 x에 도달할 때 까지 만나는 학생들을 사이클에 포함된 학생으로 만든다.

 

입니다. 이미 방문한 노드에 또 방문할 경우 탐색이 종료되고 이후 방문 표시를 남기는 작업을 진행하기 때문에 각 노드는 최대 2번 방문되어 O(N)입니다.

 

이 상황을 곧이곧대로 구현하면 통과가 가능합니다. (http://boj.kr/8a77114d44b54802b232993a79d10e5e)

 

그런데 보시다시피 구현이 조금 깁니다. 방문 체크를 조금 다른 방식으로 하면 케이스를 덜 나눠도 됩니다. 우리는 '사이클에 포함되지 않은 학생' 값을 별도로 두지 않고 구현하고 싶습니다. 그러기 위해서는 각 run 함수에서 이전에 방문한 값 y를 방문했을 때 y가 이번 run 함수에서 방문된 값인지, 이전의 run 함수에서 방문된 값인지를 구분할 수 있어야 합니다.

 

만약 y가 이번 run 함수에서 방문된 값이라면 2번 혹은 3번 케이스가 될 것이고 이전 run 함수에서 방문된 값이라면 1번 케이스가 됩니다. 이를 판별하기 위해 run 함수의 state에 방문 표시를 남길 때 그냥 VISITED = 1과 같은 동일한 값을 쓰는게 아니라 x를 씁니다.

 

빨간색 학생이 1번 학생이었다고 할 때, 이렇게 값을 쓰면 별 표시가 되어있는 학생을 만났을 때 이번 run 함수에서 방문된 값임을 깨닫고 사이클을 찾아낼 수 있습니다.

 

이후 사이클을 돌면서 비슷한 작업을 해줍니다.

 

보라색 학생이 7번 학생이라고 할 때 이 경우는 어떻게 처리가 될지 생각해봅시다.

 

진행을 하다가 state의 값이 7이 아닌 1인 학생을 만나게 되고, 바로 1번 케이스임을 알 수 있습니다.

 

이와 같이 BFS를 여러 시작점에 대해서 진행해야 할 때 visited 배열을 매번 새로 만들거나 초기화를 시키면 O(N^2)이 되지만 visited 여부를 체크하는 값을 매번 다른 값을 넣어 O(N)으로 만드는 테크닉이 유용할 때가 있어서 알아두시면 좋습니다.

 

이 방법 대신 그냥 맨 처음 언급한 O(N) 풀이로 작성을 해도 되지만 지금 이 풀이로 코딩을 하면 오로지 이번 방문에서 지나간 학생에 도달했는지, 이전 방문에서 지나간 학생에 도달했는지만 신경을 쓰면 되어서 케이스 분류가 조금 덜 복잡해지고 코드가 간결해집니다. 

 

코드를 참고해보세요. http://boj.kr/65dc47124e3c4f53a9e5e710e78fa881

 

이렇게 문제 풀이가 끝났습니다. 적당히 어려우면서 괜찮은 문제라고 생각합니다. 특히 BFS를 여러 시작점에 대해서 진행해야 할 때 visited 배열을 매번 새로 만들거나 초기화를 시키면 O(N^2)이 되지만 visited 여부를 체크하는 값을 매번 다른 값을 넣어 O(N)으로 만드는 테크닉은 알아두시면 언젠가 좀 어려운 문제를 풀 때 쓰일수도 있으니 좋을 것 같습니다.