[백준] 13023 : ABCDE

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

13023번: ABCDE

모든 노드를 시작점으로 하고 탐색해서 깊이가 4가 되는 때를 찾음.

처음 그래프를 구현할 때 배열을 썼는데 배열로 구현을 하면 시간초과가 생겨서 리스트로 다시 구현을 했다.

궁금한 점은 배열로 구현했을 땐 분기점의 노드의 상태를 true에서 false로 변환해주지 않았는데 리스트로 구현했을 땐 필요했다는 것이다.

 

내 코드

메모리 : 19840 KB

시간 : 264 ms

코드 길이 : 1532 B

 

[내 코드]

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

public class Main {
	static int N;
	static ArrayList<Integer>[] list;
	static boolean[] isVisit;
	static boolean result = false;
	

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		//사람의 수
		N = Integer.parseInt(st.nextToken());
		//관계의 수
		int M = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[N];
		for(int i = 0; i < N; i++)
			list[i] = new ArrayList<Integer>();
		
		for(int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			list[i].add(j);
			list[j].add(i);
		}
		
		for(int n = 0; n < N; n++) {
			if(result == false) {
			isVisit = new boolean[N];
			DFS(n, 0);
			}
		}
		
		if(result == true)
			sb.append(1);
		else
			sb.append(0);
		
		System.out.print(sb);

	}
	
	//깊이 우선 탐색
	public static void DFS(int node, int length) {
		if(length == 4) {
			result = true;
			return;
		}
		
		isVisit[node] = true;
		
		for(int i = 0; i < list[node].size(); i++) {
			int nextNode = list[node].get(i);
			if(isVisit[nextNode] == false) {
				//true로 변환 후
				isVisit[nextNode] = true;
				//그 상태를 기준으로 다음 탐색 시작
				DFS(nextNode, length + 1);
				//분기점인 노드인 경우 true이면 다른 분기의 노드를 탐색할 수 없으므로 false로 바꿔준다.
				isVisit[nextNode] = false;
			}
		}
	}
}

1등 코드

메모리 : 12504 KB

시간 : 156 ms

코드길이 : 1500 B

 

[상위권 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int answer = 0;
    static int N, M;
    static boolean [] visited;
    static Node[] adjList;
    static class Node {
        int vertex;
        Node link;

        public Node(int vertex, Node link) {
            this.vertex = vertex;
            this.link = link;
        }
    }

    static void dfs(int idx, int cnt) {
        visited[idx] = true;
        if (cnt == 4){
            answer = 1;
            return;
        }
        for (Node temp = adjList[idx]; temp!= null;temp = temp.link){
            if (!visited[temp.vertex])
                dfs(temp.vertex, cnt+1);
        }
        visited[idx]=false;
    }
    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());
        M = Integer.parseInt(st.nextToken());
        visited = new boolean[N];
        adjList = new Node[N];
        int from, to;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            adjList[from] = new Node(to, adjList[from]);
            adjList[to] = new Node(from, adjList[to]);
        }
        for (int i = 0; i < N; i++) {
            dfs(i, 0);
        }
        System.out.println(answer);
    }
}