2668번 - 숫자고르기

1️⃣ DFS

 

✏️ 풀이 과정

배열의 인덱스 1~N을 정점의 번호라고 생각하고 아래의 숫자를 해당 정점에 대해 방향을 가진 경로가 있는 것으로 보면 탐색 문제로 볼 수 있습니다.

 

여기서 문제의 조건을 만족하는 경우는 그래프가 사이클을 만드는 경우입니다. 정점마다 하나의 간선만 갖기 때문에 사이클을 한 번 발견하면 더 이상 길이가 늘어나거나 하지 않습니다. 그래프 내의 모든 사이클을 찾고 사이클들을 구성하는 원소의 개수와 오름차순으로 정렬된 목록을 띄우면 해결됩니다.

다른 정점이 관여되더라도 사이클을 이루는 정점의 개수는 바뀔 수가 없습니다.

 

여기서는 DFS를 이용해서 그래프를 탐색하면서 사이클을 찾았습니다. 사이클은 한 번 방문한 정점을 다시 방문했을 때 찾을 수 있습니다. 여기서 모든 정점에 대해 탐색을 처음부터 하게 되면 중복탐색이 많기 때문에 방문 표시를 배열 하나로(비트마스킹을 하면 N이 32를 넘어갈 수 있기 때문에 오버플로우가 납니다.) 끝내고 싶어 지지만 이럴 경우 새로 DFS를 할 때 이전에 방문했던 정점을 마주칠 때 사이클이 만들어진 것으로 판정되어 잘못된 로직이 됩니다.

 

그래서 여기서는 전체 방문 여부를 따지는 배열(중복 제거)과 하나의 DFS에서 방문 여부를 따지는 배열(사이클 여부 판단) 두 개를 사용해서 문제를 해결했습니다. 이전 탐색들에서 방문한 적 없는데 이번 탐색에서 중복되는 정점이 나타날 경우 사이클로 판단하고 해당 정점부터 DFS를 돌면서 ArrayList에 연결된 모든 원소들을 넣습니다.

 

모든 정점에 대해 DFS가 완료되면 모든 사이클이 발견되고 나머지는 ArrayList를 오름차순으로 정렬하고 사이즈 및 원소들을 출력하면 끝이 납니다.

 

💻 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	
	// 입력 저장 배열
	static int[] arr;
	// 결과 저장 리스트
	static ArrayList<Integer> list;
	
	static boolean[] outer;
	static boolean[] inner;
	
	static void dfs(int n) {
		if(outer[n] && !inner[n]) {
			return;
		}
		if(inner[n]) {
			// 끝
			boolean[] in = new boolean[101];
			addList(n, in);
			return;
		}
		outer[n] = true;
		inner[n] = true;
		dfs(arr[n]);
	}
	
	static void addList(int n, boolean[] in) {
		if(in[n]) {
			return;
		}
		list.add(n);
		in[n] = true;
		addList(arr[n], in);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arr = new int[N+1];
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		list = new ArrayList<>();
		outer = new boolean[N+1];
		for (int i = 1; i <= N; i++) {
			if(outer[i]) {
				continue;
			}
			inner = new boolean[N+1];
			dfs(i);
		}
		list.sort(null);
		System.out.println(list.size());
		for(int n:list) {
			System.out.println(n);
		}
		br.close();
	}
}

JavaScript

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
let list = [];
let outer = [];
let inner;

function dfs(n) {
  if (outer[n] && !inner[n]) {
    return;
  }
  if (inner[n]) {
    let visited = [];
    addList(n, visited);
    return;
  }
  outer[n] = true;
  inner[n] = true;
  dfs(input[n]);
}

function addList(n, visited) {
  if (visited[n]) {
    return;
  }
  list.push(n);
  visited[n] = true;
  addList(input[n], visited);
}

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  input = input.map(Number);
  for (let index = 1; index <= input[0]; index++) {
    if (outer[index]) {
      continue;
    }
    inner = [];
    dfs(index);
  }
  list.sort((a, b) => a - b);
  console.log(`${list.length}\n${list.join("\n")}`);
  process.exit();
});