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

 

2668번: 숫자고르기

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절

www.acmicpc.net

 

문제해설

DFS 문제입니다.

각 사이클을 구할떄 DFS를 통해서 계속해서 파고 들어가다가 해당 인덱스가 다시 나오면 사이클이 발생했다고 판단하면 되는 문제입니다.

헷갈리는 문제였습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N;
	public static int[][] map;
	public static boolean[] visited;
	public static ArrayList<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new int[2][N+1];
    	visited = new boolean[N+1];
    	for(int i=1;i<=N;i++) {
    		map[0][i] = i;
    		map[1][i] = Integer.parseInt(br.readLine());
    	}
    	
    	for(int i=1;i<=N;i++) {
    		visited[i] = true;
    		DFS(i, i);
    		visited[i] = false;
    	}
    	
//    	Collections.sort(list); 어처피 map[0][N+1] 은 모두 1 2 3 4 5 6 7 .. 이렇게 오름차순 되어있으므로 Sort를 안해도됩니다.
    	System.out.println(list.size());
    	for(int i = 0;i<list.size();i++) {
    		System.out.println(list.get(i));
    	}
    	
    } 
    
    public static void DFS(int start, int target) {
    	if(visited[ map[1][start] ] == false) {
    		visited[ map[1][start]] = true;
    		DFS( map[1][start] , target);
    		visited[ map[1][start]] = false;
    	}
    	if(map[1][start] == target) list.add(target);
    }
    
    
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 5547 일루미네이션 - BFS(너비우선탐색) + 아이디어(Idea) JAVA  (0) 2023.06.24
[백준] 13023 ABCDE - DFS, 시간초과 JAVA  (0) 2023.06.24
[백준] 17836 공주님을 구해라! - BFS JAVA  (0) 2023.06.21
[백준] 13549 숨바꼭질 3 - BFS JAVA  (0) 2023.06.20
[백준] 7569 토마토 - BFS  (0) 2023.06.19

+ Recent posts

티스토리툴바