[백준 -24480 ] java , 알고리즘 수업 - 깊이 우선 탐색 2

 

문제를 풀기 전 그래프 및 DFS 개념이 부족하다면 아래 포스팅을 먼저 읽어주세요!

https://sunro1994.tistory.com/179

[자료구조 - Graph 와 DFS] Graph와 DFS란?

---

 

문제해결중 놓친 중요한 부분 - 내림차순!

Do it 알고리즘 자바편을 통해 DFS를 공부하고 해당 코드를 변경해서 이 문제를 풀려고 했다.

책에서 제공했던 백준 문제는 아래의 문제였다.

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

11724번: 연결 요소의 개수

 

이번 문제는 위 문제와 달랐던 점이 몇 가지 있다.

첫 번째, 방문 순서를 출력할 것

두 번째, 인접 정점은 내림차순으로 정렬

 

정렬을 하지 않아 계속 [1,4,3,2,0]이 아닌 [1,4,2,3,0]으로 나오는 것이었다.

문제에서 요구하는 내용을 꾸준히 체크하고 반례를 찾아나서는 습관을 들여야겠다.

 

 

[정답코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.StringTokenizer;

public class test2 {
//인접 리스트 배열
    static ArrayList<Integer>[] A;
//방문배열 
    static boolean[] visited;
//방문 순서 담을 배열
static int[] result;
//방문 순서 카운트
static int cnt = 1;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

//1부터 시작하도록 각 필드값 초기화
        A = new ArrayList[n+1];
        visited = new boolean[n+1];
        result = new int[n + 1];



//인접리스트의 각 요소 초기화
        for (int i = 1; i < n + 1; i++) {
            A[i] = new ArrayList<Integer>();
        }
//인접리스트배열에 문제에서 주어진 값 삽입
//양방향이기때문에 각 리스트배열에도 양방향으로 추가해준다.
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s);
        }
        int cnt = 0;
//방문하지 않은 노드인경우 DFS 메서드 수행
        if (!visited[v]) {
            DFS(v);
        }
        for (int i = 1; i < n+1; i++) {
            System.out.println(result[i]);
        }

    }

    private static void DFS(int v) {
        if(visited[v]) return;

        visited[v] = true;
//첫 노드 방문 순서 삽입
        result[v] = cnt++;
//내림차순 정렬
        Collections.sort(A[v], Collections.reverseOrder());
        for (Integer i : A[v]) {
            if (!visited[i]) {
//재귀적 알고리즘 수행
                DFS(i);
            }
        }

    }
}