24480번

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

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

저번에 이어서 DFS기초 문제를 다시 풀어보았다. 저번과 같은 코드이지만 내림차순이어서 인접 리스트의 정렬을 내림차순으로 바꿔주기만 하면 된다.

너무 간단한 문제여서 오늘은 짧게 설명하겠다.

방문 여부를 판단하는 boolean배열과 순서를 담을 int배열

그리고 순서값을 셀 count 그리고 node의 갯수가 있으면, boolean배열의 T,F를 판별하여고,

방문하지 않은 노드라면 T로 바꾸어주고, 순서를 담는 배열에 넣어준다.

그 다음에 인접리스트를 내림차순으로 정렬하여 인접행렬에 접근하는 재귀함수를 돌려주면 된다.

 

정답 코드는 아래와 같다.

 

package backjoon.b24480;

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

public class b24480 {
    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);
        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 node;
    boolean[] visit;
    LinkedList<Integer>[] adj;
    int[] order;
    int count=1;
    public Graph(int node){
        this.node = node;
        visit = new boolean[node+1];
        adj = new LinkedList[node+1];
        for(int i=0; i<=node; i++){
            adj[i] = new LinkedList<>();
        }
        order = new int[node];
    }
    public void addEdge(int u, int v){
        adj[u].add(v);
        adj[v].add(u);
    }
    public void dfs(int R){
        if(visit[R]){
           return;
        }
        visit[R]=true;
        adj[R].sort((a,b)->a>b?-1:(a==b?0:1));
        order[R-1]=count++;
        for(int i:adj[R]){
            dfs(i);
        }
    }
}