24479번

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

DFS를 까먹지 않기위해서 다시 관련 문제를 풀어보았다.

이 문제는 순서대로 노드 값을 출력하는 것이 아니라 각 노드를 순서대로 출력하는 문제이다.

logic은 같지만 각 노드의 순서를 출력하는 것에 대해서는 조금 다시 생각해 볼 수 있었다.

처음에는 재귀함수 안에서 count값을 파라미터로 전달해봤다. 하지만 이렇게 되면 깊이를 판별 할 수는 있지만, 깊이가 같은 경우가 생긴다. 그렇기 때문에 순서를 출력 할 수는 없었다. 그래서 count값을 클래스의 필드변수로 만들어서 증가시키는 방법으로 이 문제를 해결했다.

나머지는 dfs자체 logic이기 때문에 설명은 생략하겠다.

 

정답은 아래의 코드와 같다. 이 문제에서 간선의 총 갯수를 주는데 굳이 필요없는 변수라서 입력은 받았지만 사용하진 않았다.

 

추가로 오름차순으로 접근하라고 주어져서 매번 인접노드리스트를 정렬했는데 한번에 모든 노드를 정렬하고 하는 것이 더 효율적일 것 같다.

package backjoon.b24479;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class b24479 {
    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 R = Integer.parseInt(st.nextToken());

        Graph g = new Graph(N,M);
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            g.addEdge(u,v);
        }
        g.dfs(R);
        StringBuilder sb = new StringBuilder();
        for(int i:g.order){
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }
}
class Graph{
    int n;
    LinkedList<Integer> adj[];
    int count=1;
    boolean[] visit;
    int[] order;
    public Graph(int n, int edge){
        this.n=n;
        visit = new boolean[n+1];
        adj=new LinkedList[n+1];
        for(int i=0; i<=n; i++){
            adj[i] = new LinkedList<>();
        }
        order = new int[n];
    }
    public void addEdge(int u, int v){
        adj[u].add(v);
        adj[v].add(u);
    }
    public void dfs(int R){
        if(!visit[R]){
            visit[R]=true;
            order[R-1]=count++;
            adj[R].sort(Integer::compareTo);
            for(int i : adj[R]){
                dfs(i);
            }
        }

    }
}