#10451 순열 사이클

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

10451번: 순열 사이클

실버2 문제이다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int N,cnt;
int map[1001][1001];
int graph[1001];
int visit[1001];

void dfs(int x){
  visit[x]=1;
  for(int i=1;i<=N;i++){
    if(visit[i]==0 && map[x][i]==1){
      dfs(i);
    }    
  }
}

int main(){
  int t;
  cin>>t;
  while(t--){
    cnt=0;
    memset(graph,0,sizeof(graph));
    memset(visit,0,sizeof(visit));
    memset(map,0,sizeof(map));
    cin>>N;
    
    for(int i=1;i<=N;i++){
      cin>>graph[i];
    }

    for(int i=1;i<=N;i++){
      map[i][graph[i]]=1;
    }
   
    for(int i=1;i<=N;i++){
      if(visit[i]==0&&map[i][graph[i]]==1){
        dfs(i);
        cnt++;
      }
    }
    cout<<cnt<<'\n';
  }
}

정답 코드는 위와 같다. 문제의 예시를 입력 받는 부분에서 약간 애를 먹었다. 인덱스와 배열안의 값을 연결 한다는 생각을 해놓고도 조금 헤맸다. 결국 map[i][graph[i]] 이렇게 구성해서 i는 인덱스로, graph[i]는 그 해당하는 값으로 하고, map이라는 2차원 배열에 두 수를 연결하였다면 1을 저장, 그렇지 않다면 0으로 초기화 했다. (memset이용)

그리고, 처음에는 map을 전체를 돌면서 1 이 있다면 dfs를 돌리는 것인가 생각했었는데, 그게 아니었다.

인덱스값과 배열 안의 값이 연결되어 있기 때문에 for문을 한번만 돌려도 가능했다. 인덱스 값을 통해서 map의 두번째 인덱스 까지 쓸 수 있기 때문! (나만 이해하는 말 일듯)

 

암튼 한번에 맞춘 문제여서 기분이 좋았다 ^_^