백준 10451번

10451번: 순열 사이클

index	1	2	3	4	5	6	7	8	9
수열	7	3	2	1	5	4	6	9	8

문제가 조금 헷갈려서 이해하는데 조금 시간이 걸렸다.

위와 같은 수열이 주어지면 index -> 수열은 연관관계가 있다고 생각하면 된다. 

1부터 시작하면 1 -> 7 -> 6 -> 4 -> 1

2부터 시작하면 2 -> 3 -> 2

index와 주어진 수열은 하나의 그래프라고 생각하면 되고 수열로 이루어진 그래프는 반드시 사이클을 만들게 된다.

 

코드

public static void dfs(int startIndex)
{
    visited[startIndex] = true;
    if(visited[arr[startIndex]]==false)
    {
        dfs(arr[startIndex]);
    }else {
        return;
    }
}

DFS를 이용하여 구현한 코드이다. index 1일때 부터의 로직을 따라가면서 정리해 보겠다.

 

visited [1] = true를 해주면서 index 1에 방문했다는 것을 체크한다.

다음은 이제 index 1에 들어있는 값에 방문 여부를 확인한다. index 1번째 원소의 값은 현재 7이다.

visited [7]은 아직 방문하지 않아서 false값이 들어있기 때문에 7과 연결된 값을 찾기 위해

dfs 함수룰 재귀 호출한다.

 

index 7에 방문했다는 것을 체크하기 위해 visited[7] = true를 해준다

index 7번째 원소의 값인 6의 방문 여부를 visited [arr [7]]로 확인한다. false이기 때문에 dfs함수를 또다시 재귀 호출에

6번째 원소의 값과 연관된 값을 찾는다. 

이와 같은 과정을 반복하다가 4번째 원소의 값 1의 방문여부를 체크한다. 이때 처음에 visited [1]= true를 해주었기 때문에

dfs함수를 탈출할 수 있게 된다.

 

이와 같은 순서를 통해 연결된 모든 값들을 찾고 dfs함수가 호출될 때마다 count의 값을 증가시켜 준다.

 

public static void bfs(int index)
{
    Queue<Integer>queue = new LinkedList<>();
    queue.offer(index);
    visited[index] = true;
    while(!queue.isEmpty())
    {
        int n  = queue.poll();
        if(visited[arr[n]]==false)
        {
            queue.offer(arr[n]);
            visited[arr[n]] = true;
        }
    }
}

DFS로도 한번 구현을 해보았다.

큐를 이용해 아직 방문하지 않은 원소들의 index값을 큐에 추가해 주고 index값들을 하나씩 꺼내가면서 연결된 원소를 계속 찾아나간다.

재귀 호출보다는 나는 bfs가 더 편한 거 같네요...

 

전체 코드

import java.util.*;
public class Main{
    static boolean[] visited;
    static int[] arr;
    static int testCase;
    static int n;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        testCase = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while(testCase > 0) {
            n = sc.nextInt();
            arr = new int[n+1];
            visited = new boolean[n+1];
            int count = 0;
            for (int i = 1; i <= n; ++i)
            {
                arr[i] = sc.nextInt();
            }
            for (int i = 1; i <= n; ++i)
            {
                if (visited[i] == false)
                {
                    bfs(i);
                    ++count;
                }
            }
            sb.append(count+"\n");
            --testCase;
        }
        System.out.println(sb);
    }

    public static void dfs(int startIndex)
    {
        visited[startIndex] = true;
        if(visited[arr[startIndex]]==false)
        {
            dfs(arr[startIndex]);
        }else {
            return;
        }
    }

    public static void bfs(int index)
    {
        Queue<Integer>queue = new LinkedList<>();
        queue.offer(index);
        visited[index] = true;
        while(!queue.isEmpty())
        {
            int n  = queue.poll();
            if(visited[arr[n]]==false)
            {
                queue.offer(arr[n]);
                visited[arr[n]] = true;
            }
        }
    }
}