[Silver II/JAVA] 24479, 24480 알고리즘 수업 - 깊이 우선 탐색 1, 2

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

 

 

• 문제의 조건

정점의 수 : N
간선의 수 : M
시작 정점 : R
인접 정점은 오름차순 방문 (24479번 문제)
인접 정점은 내림차순 방문 (24480번 문제)

 

• 필요한 것

ArrayList (이차원 Array는 N*N이라 시간초과 발생함) 
-> 실제 연결된 간선만 저장하는 ArrayList를 사용하는 것이 메모리 낭비를 줄일 수 있음

 

- 이차원 배열의 시간 복잡도 : O(N)

- 인접 리스트의 시간 복잡도 : O(E), 여기서 E는 간선의 개수. 인접리스트는 간선의 개수와 시간복잡도가 비례한다.

 

• 입력받기

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");

int N = Integer.parseInt(str[0]); // 정점의 수
int M = Integer.parseInt(str[1]); // 간선의 수
int R = Integer.parseInt(str[2]); // 시작 정점

 

- Scanner보다 BufferedReader를 사용하는 것이 훨씬 성능이 좋다.

- BufferedReader는 문자열을 반환하기 때문에 형변환이 필요하다.

- 입력을 공백단위로 끊어서 스트링 배열에 담아서 읽는다.

 

• visited 배열, graph 배열 초기화하기

// 방문 체크 배열 초기화
visited = new int[N + 1];

// 그래프 초기화
for (int i = 0; i < N + 1; i++) {
    graph.add(new ArrayList<>());
}

 

- 문제를 보면 '정점 번호는 1번부터 N 번...' 이라고 되어 있기 때문에 인덱스를 1부터 사용하기 위해 N+1 크기로 선언했다.

- visited 배열은 정점의 방문을 기록하는 역할이다.

- graph 배열은 정점 번호마다 별도의 연결리스트를 초기화한다.

 

• 간선 정보 입력받기

// 그래프에 간선 정보 저장
for (int i = 0; i < M; i++) {
    str = br.readLine().split(" ");
    int u = Integer.parseInt(str[0]);
    int v = Integer.parseInt(str[1]);

    // 무방향 그래프
    graph.get(u).add(v);
    graph.get(v).add(u);
}

 

- 간선의 수 M만큼 반복문을 돌며 간선을 입력받는다.

- 예를 들어 입력이 1 4 이면 정점 1과 정점 4를 연결했다는 뜻이다. 무방향 그래프에서 이는 정점 4와 정점 1을 연결했다는 뜻과도 같기 때문에 양방향 관계를 표현한다.

 

• 정점 번호를 오름차순으로 방문

// 인접 리스트 오름차순 정렬
for (int i = 1; i < N + 1; i++) {
    Collections.sort(graph.get(i));
}

 

- 자바 Collections의 sort() 메서드를 이용하면 오름차순 정렬을 간단히 할 수 있다.

 

• 정점 번호를 내림차순으로 방문

// 인접 리스트 내림차순 정렬
for (int i = 1; i < N + 1; i++) {
    Collections.sort(graph.get(i), Collections.reverseOrder());
}

 

- reverseOrder() 메서드는 내림차순 정렬이다.

 

• DFS 깊이 우선 탐색 

// DFS 탐색
private static void dfs(int node) {
    visited[node] = count; // 방문 순서 기록

    for (int i = 0; i < graph.get(node).size(); i++) {
        int nextNode = graph.get(node).get(i);
        if (visited[nextNode] == 0) { // 방문하지 않았다면
            count++;
            dfs(nextNode);
        }
    }
}

 

- 위에서 모든 준비가 끝났다면 DFS 탐색을 재귀적으로 반복한다.

- 출력하고자 하는 것은 방문순서이다.

 

 

전체코드

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

public class Main{
    
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] visited;
    static int count;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        int R = Integer.parseInt(str[2]);
        
        //방문체크할 배열
        visited = new int[N+1];
        
        //graph 초기화
        for(int i=0; i<N+1; i++){
            graph.add(new ArrayList<>());
        }
        
        //graph에 값 저장
        for(int i=0; i<M; i++){
            str = br.readLine().split(" ");
            int u = Integer.parseInt(str[0]);
            int v = Integer.parseInt(str[1]);
            
            //무방향그래프
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        //오름차순 정렬 (24479번 문제)
        for(int i=1; i<N+1; i++){
            Collections.sort(graph.get(i));
        }
        
        //내림차순 정렬 (24480번 문제)
        for(int i=1; i<N+1; i++){
            Collections.sort(graph.get(i), Collections.reverseOrder());
        }
        
        //방문 카운트
        count = 1;
        //시작정점부터 탐색
        dfs(R);
        
        //출력
        for(int i=1; i<=N; i++){
            System.out.println(visited[i]);
        }
    }
    
    //DFS 탐색
    private static void dfs(int node){
        visited[node] = count;
        
        for(int i=0; i<graph.get(node).size(); i++){
            int nextNode = graph.get(node).get(i);
            if(visited[nextNode] == 0){ //방문한적 없으면
                count++;
                dfs(nextNode);
            }
        }
    }
}