[백준 2668] 숫자 고르기

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

 

DFS 문제입니다. 

입력을 받아 문제와 같은 형태를 만들기 위한  2차원 배열 arr

방문 확인을 위한 배열 visited

을 사용했습니다. 

1부터 입력받은 N까지 DFS를 하면서

방문횟수가 2라면 DFS를 끝내고,

그게 아니라면 방문횟수를 늘려줍니다. 그리고 1 -> 2로 됫을경우 cnt를 1증가.(출력용 변수)

그리고 자기 밑에쪽으로 DFS.

 

	public class Q2668 {
	static int cnt = 0;
	static int[] visited;
	static int[][] arr;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int num = Integer.parseInt(br.readLine());
	arr = new int[num+1][2];
	visited = new int[num+1];
	for(int i=1; i<arr.length; i++) {
	arr[i][0] = i;
	arr[i][1] = Integer.parseInt(br.readLine());
	}
	for(int i=1; i<arr.length; i++) {
	if(visited[i]==2) {
	continue;
	}
	DFS(i);
	init();
	}
	System.out.println(cnt);
	for(int i=1; i<visited.length; i++) {
	if(visited[i]==2) {
	System.out.println(i);
	}
	}
	}
	public static void DFS(int x) {
	if(visited[x]==2) {
	return;
	}
	visited[x]++;
	if(visited[x]==2) {
	cnt++;
	}
	DFS(arr[x][1]);
	}
	public static void init() {
	for(int i=0; i<visited.length; i++) {
	if(visited[i]!=2) {
	visited[i] = 0;
	}
	}
	}
	}

view raw Q2668.java hosted with ❤ by GitHub

앞으로 몇문제는 DFS를 풀어야겠습니다... 오랜만에 하니까 잘 안되네요