백준 13023번, ABCDE - (Java, DFS)

어떤 알고리즘?

문제는 DFS를 사용하면 풀 수 있다.

 

친구를 노드로 관계를 엣지로 하는 그래프로 나타낼 수 있겠다는건 쉽게 생각할 수 있다.

그러면 DFS를 사용해야겠다는 생각은 어디에서 힌트를 얻을 수 있을까

 

 

주어진 친구 관계를 나타내보면 A-B-C-D-E 이렇게 일직선상인 것을 알 수 있다.

인접한 노드를 따라 최대한 깊이 들어가고 더이상 갈 곳이 없으면 이전 정점으로 돌아가는 DFS를 떠올릴 수 있겠다.

 

 

쉽게 말하자면 DFS는 세로로 한줄씩 읽어 내려가니깐 A-B-C-D-E를 찾기에 적합하다고 볼 수 있다.

 

 

 

 

 

 

 

 

구현은?

구현은 어떻게 할 것인가?

DFS를 사용하되 count를 해야 할것이다.

A-B-C-D-E 이렇게 5개의 노드가 직선이여야 하니깐

인접한 노드를 찾으면서 들어갈때마다 count를 1씩 증가시키면 되겠다.

 

여기서 조심해야할 점은 더이상 인접한 노드가 없을때 방문했다는 사실을 false로 만들어야 할것이다.

 

예를 들어 0 -> 1 -> 2 순서로 방문하였는데 2부터 더이상 인접한 노드가 없어서 1로 돌아가야 할때는

2를 방문했다는 사실을 false 상태로 두어야한다는 것이다.

왜그럴까? 필자는 직관적으로 이해가 안되서 그림을 그려보았다. 

 

 

그래프가 다음과 같다고 하자

0 -> 1 -> 2 를 방문하고 false 상태로 되돌리지 않으면

0->4->3->1->2 와 같이 5개 노드가 직선인 경우가 존재하는데도

0->4->3 에서 1 과 2는 방문 노드이기 때문에 더이상 탐색을 하지 않을 것이다.

 

따라서 더이상 인접한 노드가 없는 경우는 false 상태로 만들고 돌아가야 한다.

 

 

 

 

구현한 코드는 아래와 같다.

import java.util.*;
import java.io.*;

public class Main{
    static boolean isLine = false;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        boolean[] visited = new boolean[n];
        LinkedList<LinkedList<Integer>> adjacent = new LinkedList<>();

        for(int i = 0; i<n; i++){
            adjacent.add(new LinkedList<>());
        }


        for(int i = 0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            adjacent.get(a).add(b);
            adjacent.get(b).add(a);
        }


        for(int i = 0; i<n; i++){
            Arrays.fill(visited, false);
            dfs(i,adjacent,visited,1);
            if(isLine){
                break;
            }
        }

        bw.write(isLine? "1":"0");
        bw.flush();
        bw.close();
        br.close();
    }


    static void dfs(int index,  LinkedList<LinkedList<Integer>> adjacent, boolean[] visited, int cnt){
        if(cnt == 5){
            isLine = true;
            return;
        }
        visited[index] = true;
        for(int i : adjacent.get(index)){
            if(!visited[i]){
                dfs(i,adjacent,visited,cnt+1);
            }
            if(isLine){
                return;
            }
        }
        visited[index] = false;

    }
}

 

 

내 오답

필자는 시간초과로 틀렸는데 

그 이유가 처음에 DFS를 인접 리스트가 아닌 인접 행렬로 구현했기 때문이다.

 

노드가 n개라고 할 때

DFS를 인접 행렬(2차원 배열)로 구현을 하면 

DFS 1회당 n번이 탐색이 있을 것이고 n개의 노드를 모두 방문하니깐

O(n^2)의 시간복잡도를 가지는 반면에

 

인접 리스트는

DFS 1회당 해당하는 노드의 간선의 개수만큼 탐색이 있을것이기에

O(n+e)의 시간복잡도를 가진다.

 

그렇기에 DFS는 인접 리스트를 쓰는걸 추천한다.