SW Expert - 1267 작업 순서

dfs 문제입니다.

 

선행 조건이 있는 방향 트리가 주어졌을 때,

순차적으로 탐색할 수 있는 순서를 구하는 문제입니다.

 

문제 접근 방법은 다음과 같습니다.

1. 각 시점에서 시작한다.
2. 연결된 노드로 이동한다.
   1. 선행 조건을 만족하지 않으면 이동하지 않는다.
   2. 선행 조건을 만족하면 이동한다.
3. 현재 노드에서 더이상 이동할 게 없으면, 선행 조건이 완료된 노드로 이동한다.
4. 모든 노드가 연결되면 전부 종료한다.

 

코드 이해를 돕기위해 리팩토링을 하지 않은, 날것의 코드로 공유합니다.

 

[구현 코드]

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

public class Solution {
    private static int v;
    private static List<Integer> answer;
    private static Map<Integer, Set<Integer>> preConditions;
    private static List<List<Integer>> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz;

        int t = 10;

        for (int testCase = 1; testCase <= t; testCase++) {
            stz = new StringTokenizer(br.readLine());
            v = Integer.parseInt(stz.nextToken());
            int e = Integer.parseInt(stz.nextToken());
            answer = null;

            graph = new ArrayList<>();
            for (int i = 0; i < v; i++) {
                graph.add(new ArrayList<>());
            }

            preConditions = new HashMap<>();
            stz = new StringTokenizer(br.readLine());
            for (int i = 0; i < e; i++) {
                int a = Integer.parseInt(stz.nextToken()) - 1;
                int b = Integer.parseInt(stz.nextToken()) - 1;
                graph.get(a).add(b);

                Set<Integer> in = preConditions.getOrDefault(b, new HashSet<>());
                in.add(a);
                preConditions.put(b, in);
            }

            List<Integer> startNodes = new ArrayList<>();
            for (int i = 0; i < v; i++) {
                if (!preConditions.containsKey(i)) startNodes.add(i);
            }

            // 1. 각 시점에서 시작한다.
            for (int onlyOutNode : startNodes) {
                boolean[] visited = new boolean[v];
                visited[onlyOutNode] = true;

                List<Integer> order = new ArrayList<>();
                order.add(onlyOutNode);

                dfs(onlyOutNode, visited, order);
            }

            StringBuilder sb = new StringBuilder();
            sb.append("#").append(testCase).append(" ");
            for (int ans : answer) {
                sb.append(ans + 1).append(" ");
            }
            System.out.println(sb.toString());
        }

        br.close();
    }

    private static void dfs(int current, boolean[] visited, List<Integer> order) {
        // 4. 모든 노드에 연결되면 전부 종료한다.
        if (answer != null) return;
        if (order.size() == v) {
            answer = new ArrayList<>(order);
            return;
        }

        // 2. 연결된 노드로 이동한다.
        for (int i = 0; i < graph.get(current).size(); i++) {
            int nn = graph.get(current).get(i);

            // 2.1 선행 조건을 만족하지 않으면 이동하지 않는다.
            if (visited[nn] || !isMeetTheCondition(visited, nn)) continue;

            // 2.2 선행 조건을 만족하면 이동한다.
            visited[nn] = true;
            order.add(nn);
            dfs(nn, visited, order);

            visited[nn] = false;
            order.remove(order.size() - 1);
        }

        // 3. 현재 노드에서 더이상 이동할 게 없으면, 선행 조건이 완료된 노드로 이동한다.
        for (int i = 0; i < v; i++) {
            if (visited[i] || !isMeetTheCondition(visited, i)) continue;

            visited[i] = true;
            order.add(i);
            dfs(i, visited, order);

            visited[i] = false;
            order.remove(order.size() - 1);
        }
    }

    private static boolean isMeetTheCondition(boolean[] visited, int i) {
        if (preConditions.containsKey(i)) {
            Set<Integer> preConditionNode = preConditions.get(i);
            for (int pre : preConditionNode) {
                if (!visited[pre]) return false;
            }
        }
        return true;
    }
}