답안

1. 문제 파악 2. 풀이


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Stack;

public class Q5 {
    public static void main(String[] args) {
        HashMap<Integer, Integer[]> graph = new HashMap<Integer, Integer[]>();
        
        graph.put(100, new Integer[] {67, 66});
        graph.put(67, new Integer[] {100, 82, 63});
        graph.put(66, new Integer[] {100, 73, 69});
        graph.put(82, new Integer[] {67, 61, 79});
        graph.put(63, new Integer[] {67});
        graph.put(73, new Integer[] {66});
        graph.put(69, new Integer[] {66, 65, 81});
        graph.put(61, new Integer[] {82});
        graph.put(79, new Integer[] {82, 87, 77});
        graph.put(65, new Integer[] {69, 84, 99});
        graph.put(81, new Integer[] {69});
        graph.put(87, new Integer[] {79, 31, 78});
        graph.put(77, new Integer[] {79});
        graph.put(84, new Integer[] {65});
        graph.put(99, new Integer[] {65});
        graph.put(31, new Integer[] {87});
        graph.put(78, new Integer[] {87});

        traversal(graph, 100);
        System.out.println();
        getMax(graph, 100);
        System.out.println();
        getMin(graph, 100);
    }

    // 최댓값 구하기
    public static void getMax(HashMap<Integer, Integer[]> graph, int start) {
        ArrayList<Integer> 방문 = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(start);

        while(!stack.isEmpty()) {
            int top = stack.pop();

            if (!방문.contains(top)) {
                if (top != start) {
                    System.out.print((char)top);
                }

                방문.add(top);

                ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(graph.get(top)));
                list.removeAll(방문);

                if (list.size() == 0) {
                    break;
                }

                stack.push(Collections.max(list));
            }
        }
    } 

    // 최솟값 구하기
    public static void getMin(HashMap<Integer, Integer[]> graph, int start) {
        ArrayList<Integer> 방문 = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(start);

        while(!stack.isEmpty()) {
            int top = stack.pop();

            if (!방문.contains(top)) {
                if (top != start) {
                    System.out.print((char)top);
                }

                방문.add(top);

                ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(graph.get(top)));
                list.removeAll(방문);

                if (list.size() == 0) {
                    break;
                }

                stack.push(Collections.min(list));
            }
        }
    } 
}

1. 문제 파악

그래프는 HashMap으로 이루어져 있으며, key는 해당 노드의 데이터 값, value에는 부모 노드의 값과 자식 노드의 값이 순서대로 배열로 이루어져 있습니다.

순회를 위해 자식 노드 중 작은 값 또는 큰 값을 골라서 순회해야 하며 DFS 방식으로 순회해야 하기 때문에 stack을 사용해야 합니다.

방문여부를 확인하기 위해서 List를 선언해 방문한 노드를 추가해 줍니다.

순회 결과가 단서가 되기 때문에 아스키 코드로 인코딩해서 최종 문자열을 구해야 합니다. 이때 시작 노드는 포함하지 않습니다.

2. 풀이

방문 여부를 나타내는 리스트와 스택을 선언해서 순회를 시작합니다.


ArrayList<Integer> 방문 = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<Integer>();
stack.push(start);

DFS이기 때문에 stack이 전부 빌 때까지 순회합니다. 스택의 값을 꺼내서 방문여부를 확인하고 방문하지 않았다면 순회 과정에 포함해야 합니다. 이때 시작 노드는 제외해야 하기 때문에 시작 노드 값인지 확인해야 합니다.


if (top != start) {
    System.out.print((char)top);
}

방문 리스트에 노드 값을 추가해 방문 여부를 갱신해 주고, removeAll 메소드를 이용해서 방문 리스트의 값과 value 값의 차집합을 구해 자식 노드 값을 구합니다.


방문.add(top);

ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(graph.get(top)));
list.removeAll(방문);

순회는 단말노드까지 진행해야 하므로 더이상 자식 노드의 값이 없을 때 중단합니다.


if (list.size() == 0) {
   break;
}

자식 노드의 값들 중 작은 값 / 큰 값을 선택해서 다시 stack에 넣어 순회할 준비를 합니다. (아래의 코드는 작은 값을 선택했을 때)


stack.push(Collections.min(list));