[JAVA][백준 1260] DFS와 BFS - 인접 리스트로 풀기

사이트명	백준
문제 링크	www.acmicpc.net/problem/1260
주요 알고리즘	그래프, DFS, BFS
사용 언어	Java 자바
설명이 장황합니다.. 도움되는 것만 파악하세요 :-)

1. 문제

2. 입력 / 출력

---

3. 풀이

3-1. 생각 노트

이전에 인접 행렬로 푼 문제인데, DFS/BFS를 다시 공부할 겸 이번엔 인접 리스트로 풀려고 도전했다.

인접 리스트가 인접 행렬보다 시간도 적게 걸리는 이유도 있고, 리스트 형식으로 푸는 걸 연습하고 싶었다.

 

*참고로 시간복잡도는 다음과 같다.
인접 행렬 : 간선 개수와 무관하게, O(V^2)
인접 리스트 : O(V+E)

---

풀이 과정은 기본적으로 다음과 같다.

 

1. 간선 리스트 배열 생성 -> 초기화

2. 간선 리스트에 양방향으로 노드 넣기

3. DFS 실행

4. 초기화

5. BSF 실행

 

특히, 이 과정에서 정렬 때문에 애를 좀 먹었다.. 문제 조건에 방문할 수 있는 노드가 많은 경우, 최소 번호부터 방문하라는 조건이 있다.

이를 판별하기 위해서 2중 for문을 돌면서 최소값을 판단했다. (이 때문에 시간과 메모리가 더 소모되었다)

for (int i = 0; i < n; i++) {
    Collections.sort(nodeList[i]);
}

위 코드를 DFS, BFS 전에 미리 해주면, 정렬이 된 상태로 시작하기 때문에 2중 for문의 사용을 줄일 수 있다..

 

3-2. 변수명

변수명	설명
ArrayList<Integer>[] nodeList	간선의 리스트를 표시하기 위한 nodeList
boolean[] isVisited	방문 여부를 나타내는 isVisited배열

 

3-3. 코드 보기

import java.util.*;

// 연결 리스트로 풀기

public class BOJ1260_DFS_BFS_리스트 {

    static int N, M;
    static ArrayList<Integer>[] nodeList;
    static boolean[] isVisted;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();    // 정점 수
        M = sc.nextInt();    // 간선 수
        int V = sc.nextInt();    // 시작 정점

        nodeList = new ArrayList[N+1];    // 정점수대로 배열 생성
        isVisted = new boolean[N+1];         // 방문 여부를 판단

        // 간선 리스트 초기화
        // 1번 정점부터 리스트를 만들어서 배열에 넣기
        for (int i = 1; i <= N; i++) {
            nodeList[i] = new ArrayList<>();
        }

        // 간선수대로 반복하며 연결 리스트 생성
        for (int i = 0; i < M; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();

            // 양방향
            nodeList[from].add(to);
            nodeList[to].add(from);
        }

        DFS(V);

        Arrays.fill(isVisted, false);
        System.out.println();

        BFS(V);


    }

    private static void DFS(int V) {
        if(isVisted[V]) return;

        System.out.print(V + " ");
        isVisted[V] = true;

        // 해당 노드에 존재하는 노드 수만큼 반복
        for (int i = 0; i < nodeList[V].size(); i++) {
            int MIN = 1001;

            // 해당 노드가 가장 낮은 수인지 모두 방문하여 검증
            for (int j = 0; j < nodeList[V].size(); j++) {
                int cur = nodeList[V].get(j);

                if(!isVisted[cur]) {
                    MIN = Math.min(MIN, cur);
                }
            }

            if(MIN == 1001) break;

            DFS(MIN);
        }
    }

    private static void BFS(int V) {
        Queue<Integer> q = new LinkedList<>();

        q.add(V);
        isVisted[V] = true;

        while(!q.isEmpty()) {
            int node = q.poll();
            System.out.print(node + " ");

            // 해당 노드에 존재하는 노드 수만큼 반복
            for (int i = 0; i < nodeList[node].size(); i++) {
                int MIN = 1001;

                // 해당 노드가 가장 낮은 수인지 모두 방문하여 검증
                for (int j = 0; j < nodeList[node].size(); j++) {
                    int cur = nodeList[node].get(j);

                    if(!isVisted[cur]) {
                        MIN = Math.min(MIN, cur);
                    }

                }

                if(MIN == 1001) break;

                q.add(MIN);
                isVisted[MIN] = true;
            }

        }

    }

}

 

3-4. 마무리

문제의 조건을 명확히 파악하고, 어떻게 시간을 줄일 수 있는지 방법을 고민하는게 중요하다.

Math.min() 등의 사용보단, 시간을 줄일 수 있는 정렬의 활용을 생각해보자!