[C/C++] 백준 #2667 단지번호붙이기(깊이우선탐색)

제가 회사에서 개발자를 뽑을 때, 코테를 실시해서 그 결과를 가지고 1차에서 거르고 면접을 보게 되는데, 이 문제와 같은 유형은 단골 메뉴로 들어가 있습니다.  보통은 섬의 갯수 구하기 문제입니다.  이 문제도 거의 같지만, 섬의 크기, 여기서는 단지의 크기를 정렬하고, 그 결과를 출력하는 것만 다릅니다.

 

apartments

 

이런 문제는 너비우선탐색을 이용해서 풀어도 되겠지만, 프로그램의 복잡도상 깊이 우선탐색이 보다 편리합니다.  그리고 방문 기록을 지도에 바로 활용하면 추가적으로 필요한 저장 공간 \(O(N^2)\)을 잡지 않아도 됩니다.

 

https://www.acmicpc.net/problem/2667

 

### 주요 변수
- `q`: 각 노드가 가리키는 다음 노드를 저장하는 배열.
- `v`: 각 노드의 방문 상태를 저장하는 배열.
- `ans`: 사이클의 수를 저장하는 변수.

### 함수 `dfs`
- `dfs(int q[], int v[], int t, int c)`: 깊이 우선 탐색을 통해 사이클을 찾고 그 길이를 반환하는 함수입니다.
  - `v[t] > 0`: 이미 방문한 노드면, 현재 깊이에서 해당 노드까지의 거리를 반환합니다.
  - `v[t] < 0`: 방문했으나 사이클에 속하지 않는 노드면 0을 반환합니다.
  - `v[t] = c`: 현재 노드를 방문했음을 표시합니다.
  - `r = dfs(q, v, q[t], c+1)`: 다음 노드를 탐색합니다.
  - `v[t] = -1 - (r < 1)`: 사이클에 속하지 않는 노드로 표시합니다.
  - `return r - 1`: 사이클의 길이를 반환합니다.

### 함수 `main`
- 입력: 노드의 수 `n`과 각 노드가 가리키는 다음 노드 `s`를 입력받습니다.
- 배열 초기화: `q` 배열에 다음 노드를 저장하고, `v` 배열을 초기화합니다.
- 사이클 탐색 및 카운팅: 모든 노드를 탐색하여 사이클을 찾고, 사이클의 수를 세어 `ans`에 저장합니다.
- 출력: 사이클의 수 `ans`를 출력하고, 사이클에 속하는 노드들을 출력합니다.

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #2667
//        - by Aubrey Choi
//        - created at 2019-11-09
//----------------------------------------------------------
#include <stdio.h>

int dfs(int q[], int v[], int t, int c)
{
    if(v[t]>0) return c-v[t];
    if(v[t]<0) return 0;
    v[t]=c;
    int r=dfs(q, v, q[t], c+1);
    v[t]=-1-(r<1);
    return r-1;
}
int main()
{
    int s, n; static int q[100000], v[100000], ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++) { scanf("%d",&s); q[i]=s-1; }
    for(int i=0;i<n;i++)
    {
        if(v[i]) { if(v[i]!=-2) ans++; continue; }
        dfs(q, v, i, 1);
        if(v[i]!=-2) ans++;
    }
    printf("%d\n",ans);
    for(int i=0;i<n;i++) if(v[i]!=-2) printf("%d\n", i+1);
}