13023번 - ABCDE

1️⃣ DFS

 

✏️ 풀이 과정

문제에서 요구하는 관계는 특정 정점에서 시작해서 4번을 이동할 수 있는 경우가 존재하는 경우로 생각할 수 있습니다. 따라서 dfs를 돌려서 깊이가 5가 될 때 1을 출력하고 종료, dfs가 끝날 때 까지 종료되지 않았으면 0을 출력하면 됩니다.

 

여기서 주의할 점은 dfs를 한 번만 실행할 경우 시작 정점이 고정되어있기 때문에 해당 정점이 ABCDE 관계의 중간에 위치해 있을 경우 조건을 만족하는 관계가 있어도 없는 것으로 판단되어버립니다. 이를 해결하기 위해서 모든 정점을 시작점으로 해서 dfs를 N번 돌려 모든 경우의 수를 따질 수 있습니다.

 

dfs를 돌릴 때는 모든 정점의 방문이 아닌 모든 경로의 방문을 해야 하기 때문에 visited를 항상 초기화해줘야 합니다. N이 2000까지 가능하기 때문에 비트마스킹은 불가능하기 때문에 배열을 이용해서 true표시를하고 dfs를 실행한 이후 다시 false로 만들어 실행이 끝났을 때 초기화되도록 해야 합니다.   

 

⏱ 시간 복잡도

dfs의 시간 복잡도는 O(V+E)이지만 여기서와 같이 모든 경로를 탐색할 경우에는 O(ND^5) (D=M/N), 와 같이 표현될 수 있습니다. 정확한 계산은 매우 복잡하나 정점에 연결된 평균 간선을 5라고 쳐도 2000 * 3125 = 6250000으로 여유로운 편입니다. 실제로는 이보다 작을 확률이 높기 때문에 시간 내에 문제를 해결할 수 있음을 예측할 수 있습니다.

 

💻 코드

Java

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	static void dfs(int v, int N, ArrayList<Integer>[] adjList, int cnt, boolean[] visited) {
		if(cnt == 4) {
			System.out.print(1);
			System.exit(0);
		}
		for(int p : adjList[v]) {
			if(!visited[p]) {
				visited[p] = true;
				dfs(p, N, adjList, cnt+1, visited);
				visited[p] = false;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int from, to;
		ArrayList<Integer> adjList[] = new ArrayList[N];
		for(int i=0;i<N;i++)
			adjList[i] = new ArrayList<>();
		boolean[] visited;
		for(int i=0;i<M;i++) {
			from = sc.nextInt();
			to = sc.nextInt();
			adjList[from].add(to);
			adjList[to].add(from);
		}
		for(int i=0;i<N;i++) {
			visited = new boolean[N];
			visited[i] = true;
			dfs(i, N, adjList, 0, visited);
		}
		System.out.print(0);
		sc.close();
	}
}

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

class Node {
    constructor(v, link) {
        this.v = v;
        this.link = link;
    }
}

const dfs = (n, v, visited) => {
    if (n == 5) {
        console.log(1);
        process.exit(0);
    }
    for (let nd = adjList[v]; nd != null; nd = nd.link) {
        if (!visited[nd.v]) {
            visited[nd.v] = true;
            dfs(n + 1, nd.v, visited);
            visited[nd.v] = false;
        }
    }
};

const [N, M] = input[0].split(" ").map(Number);
const adjList = [];
let from, to;
for (let i = 1; i <= M; i++) {
    [from, to] = input[i].split(" ").map(Number);
    adjList[from] = new Node(to, adjList[from]);
    adjList[to] = new Node(from, adjList[to]);
}
for (let i = 0; i < N; i++) {
    const visited = [];
    visited[i] = true;
    dfs(1, i, visited);
}

console.log(0);