[BOJ] 백준 2668 숫자고르기 - Python/Java

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

2668번: 숫자고르기

 

해설

깊이 우선 탐색을 이용해서 싸이클을 판별하는 문제입니다. 아래와 같이 입력이 주어졌다고 해보겠습니다.

 

1	2	3	4	5	6	7
3	1	1	5	5	4	6

 

그러면 윗줄의 각 번호를 하나의 노드라고 생각하고, 아랫줄의 각 번호를 해당 노드에서 도착할 수 있는 노드라고 이해할 수 있습니다. 이 때, 1번 노드에서 출발한다고 하면 1 → 3 → 1 과 같은 싸이클이 만들어지는데요.

 

싸이클이 만들어진다는 것은 A → B 가 있을 때 A의 두번째 행의 값이 B의 첫번째 행의 값이 된다는 뜻이 됩니다. 따라서 A → B → C → A 라는 싸이클이 있다면 A의 두번째 행 값은 B에 존재하고, B의 두번째 행 값은 C에 존재하고, C의 두번째 행 값은 A에 존재한다는 뜻이 되므로 문제의 조건을 만족하게 되는 것이죠.

 

싸이클을 판단하는 방법은 시작 노드를 기억하고, 시작 노드로부터 출발하여 다음 노드가 시작 노드와 일치하는지의 여부를 보면 됩니다.

 

풀이는 아래와 같습니다.

 

풀이 - 파이썬

n = int(input())
arr = [0] + [int(input()) for _ in range(n)]
visited = [False] * (n+1)

for i in range(1, n+1):
    temp = set() # i번에서 출발하여 깊이 우선 탐색을 통해 도달할 수 있는 집합
    curr = i # curr를 시작 노드점 번호로 지정
    if not visited[curr]: 
        while True:
            next = arr[curr]
            if next not in temp:
                temp.add(next)
                curr = next
                if next == i: # 다음 노드가 시작 노드라면 싸이클 생성
                    for t in temp: visited[t] = True
                    break
            else: # 이미 방문한 곳을 방문하면 종료
                break                      

print(visited.count(True))
for i in range(1, n+1):
    if visited[i] == True: print(i)

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;

public class B_2668 {
    static int n;
    static int[] arr;
    static int answer;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        arr = new int[n+1];

        // 숫자 입력받기
        for(int i = 1; i <= n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        boolean[] visited = new boolean[n+1];
        for(int i = 1; i <= n; i++){
            int curr = i;
            Set<Integer> temp = new HashSet<>();
            if(!visited[curr]){
                while(true){
                    int next = arr[curr];
                    if(!temp.contains(next)){
                        temp.add(next);
                        curr = next;
                        if(next == i){ // 싸이클 생성되면 해당 집합을 정답에 포함
                            temp.forEach(t -> visited[t] = true);
                            break;
                        }
                    }else break;
                }
            }
        }
        // 결과 출력을 위한 StringBuilder
        IntStream.range(1, n+1).forEach(i -> {
            if(visited[i]){
                sb.append(i).append('\n');
                answer++;
            }
        });
        System.out.println(answer);
        System.out.println(sb);
    }
}