[Java] 백준 BOJ / 24484번: 알고리즘 수업 - 깊이 우선 탐색 6

알고리즘 수업 - 깊이 우선 탐색 6

문제

---

문제 설명

시작 정점 R이주어졌을 때 DFS로 정점들을 방문하였을 때 방문된 노드들에 대하여 i번 노드의 깊이 배열 d 와 i번 노드의 방문순서 t 에 대하여 di × ti 값의 합을 구하는 문제이다.

인접 정점을 내림차순으로 방문한다는 점에 유의해서 풀어야한다.

---

구현

일단 Integer 를 저장하는 ArrayList 배열을 만들어주고 들어오는 입력에 대해 양방향 간선을 저장해주면 된다.

그 후 방문정점에 대해 각 node 배열들을 내림차순으로 정렬해준다.

nodes = new ArrayList[n + 1];

for (int i = 1; i <= n; i++) {
	nodes[i] = new ArrayList<>();
}

for (int i = 0; i < m; i++) {
	st = new StringTokenizer(br.readLine());
	int u = Integer.parseInt(st.nextToken());
	int v = Integer.parseInt(st.nextToken());
	nodes[u].add(v);
	nodes[v].add(u);
}

for (int i = 1; i <= n; i++) {
	Collections.sort(nodes[i], Collections.reverseOrder());
}

그리고 메인 로직인 DFS 함수에는 현재 방문 노드를 저장할 변수 cur 과 현재의 높이를 저장할 depth 변수를 넘겨줘야 한다.

DFS의 로직 순서대로 현재 정점을 방문처리 하고 depth 배열인 d의 cur 인덱스에 depth를 저장하고 방문순서 배열인 t의 cur 인덱스에 0부터 쌓아 올려진 seq++ 을 저장한다.

visited[cur] = true;
d[cur] = depth;
t[cur] = seq++;

그 후 재귀적으로 현재 위치의 정점에서 방문할 수 있는 정점들 중 방문하지 않은 정점들을 방문해주면 된다.

for (Integer next : nodes[cur]) {
	if (!visited[next]) {
		dfs(next, depth + 1);
	}
}

그리고 결과를 출력해주면 되는데 result의 자료형을 long으로 해주어야 한다.

문제에서 주어진 조건을 보면 정점의 수가 100,000 이고 간선의 수가 200,000 인데 int의 범위를 넘어갈 수 도 있기 때문에 long으로 선언해주어야 한다.

---

코드

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

public class Main_24484 {
    static int n, m, r;
    static ArrayList<Integer>[] nodes;
    static boolean[] visited;
    static int[] t;
    static int[] d;
    static int seq = 1;
    static long result = 0;
    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());
        r = Integer.parseInt(st.nextToken());

        nodes = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        t = new int[n + 1];
        d = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            nodes[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            nodes[u].add(v);
            nodes[v].add(u);
        }

        for (int i = 1; i <= n; i++) {
            Collections.sort(nodes[i], Collections.reverseOrder());
        }


        dfs(r, 0);

        for (int i = 1; i <= n; i++) {
            if(t[i] != 0)
                result += (long) t[i] * d[i];
        }

        System.out.println(result);
    }

    public static void dfs(int cur, int depth) {
        visited[cur] = true;
        d[cur] = depth;
        t[cur] = seq++;
        for (Integer next : nodes[cur]) {
            if (!visited[next]) {
                dfs(next, depth + 1);
            }
        }
    }
}