알고리즘 스터디 7월 2주차 문제2 (DFS 와 BFS)

Jul 12, 2020

Post Series

문제#

링크로 대체

풀이 및 주저리..

최근에 너무 쉬운 문제만 풀고 있는 것 같아서.. DFS BFS 를 연습해보고자 백준 단계별 풀기에서 DFS/BFS 문제를 풀어본 문제이다. 문제를 풀면서 느꼈던 것은 자료구조 이해와 아직 java 개념에 대한 이해가 많이 부족하다는 것을 느꼈던 것 같다. 일단 문제를 풀어보고자하는 생각에 전역 변수들을 엄청나게 사용했고.. 그런것들이 후에 문제가 되어서 다시 재사용하는데 문제를 일으키다 보니 점점 더 코드가 복잡해지고 더러워져버린 것 같다.

가장 중요하게 기억에 남는 부분은 PriorityQueue 를 잘 알지도 못하면서 사용하다 보니 그저 for문으로 순회하면서 "왜 순서대로 나오지 않지?" 라고 고민한 부분이다. 오랜만에 부족한 면을 많이 느끼게 해준 문제였고.. 과연 나의 공부법에 문제가 있진 않은가 하는 생각도 많이 들게 만든 문제이다. 심지어 poll을 하다보니.. 깊은복사를 해야지만 DFS 와 BFS 둘다 해결할 수 있었기에 처음 자료구조 활용을 잘못 시작했다고 볼 수 있다.좀 더 꼼꼼하게 공부해야할 것 같고.. 자만하지말자.

문제 풀이로는 먼저 각 노드의 번호를 키(key)로 간선들의 연결을 값(value)으로 갖게 만들고 순회하는 방식으로 해결해 보았다.

코드

package baekjoon.algorithm.dfsbfs;

import java.util.*;

public class Problem1260 {
    static boolean[] isVisitedArr;
    static HashMap<Integer, PriorityQueue<Integer>> nodeMap;
    static HashMap<Integer, PriorityQueue<Integer>> nodeMap2;
    static StringBuilder dfsStb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int nodeStart = sc.nextInt();
        sc.nextLine();
        isVisitedArr = new boolean[n + 1];
        nodeMap = new HashMap<>();

        for (int i = 0; i < m; i++) {
            int start = sc.nextInt();
            int dest = sc.nextInt();
            sc.nextLine();

            if (!nodeMap.containsKey(start)) {
                nodeMap.put(start, new PriorityQueue<>());
            }
            if(!nodeMap.containsKey(dest)){
                nodeMap.put(dest,new PriorityQueue<>());
            }
            nodeMap.get(start).add(dest);
            nodeMap.get(dest).add(start);
        }

        nodeMap2 = new HashMap<>();
        for(Map.Entry<Integer,PriorityQueue<Integer>> entry : nodeMap.entrySet()){
            nodeMap2.put(entry.getKey(),new PriorityQueue<>(entry.getValue()));
        }

        dfs(nodeStart);

        Arrays.fill(isVisitedArr, false);

        StringBuilder bfsStb = bfs(nodeStart);

        dfsStb.deleteCharAt(dfsStb.length() -1);
        bfsStb.deleteCharAt(bfsStb.length() -1);

        System.out.println(dfsStb.toString());
        System.out.println(bfsStb.toString());

    }

    public static void dfs(int startNum) {

        if (isVisitedArr[startNum]) return;
        isVisitedArr[startNum] = true;
        dfsStb.append(startNum);
        dfsStb.append(" ");
        if (nodeMap.containsKey(startNum)) {
            PriorityQueue<Integer> childNodeQue = nodeMap.get(startNum);
            while(!childNodeQue.isEmpty()){
                dfs(childNodeQue.poll());
            }
        }

    }

    public static StringBuilder bfs(int startNum) {
        Queue<Integer> bfsQue = new LinkedList<>();
        StringBuilder stb = new StringBuilder();

        bfsQue.add(startNum);
        isVisitedArr[startNum] = true;

        while(!bfsQue.isEmpty()){
            int top = bfsQue.poll();
            if(nodeMap2.containsKey(top)){
                PriorityQueue<Integer> childNodeQue = nodeMap2.get(top);
                while(!childNodeQue.isEmpty()){
                    int l = childNodeQue.poll();
                    if(isVisitedArr[l]) continue;
                    isVisitedArr[l] = true;
                    bfsQue.add(l);
                }
            }
            stb.append(top);
            stb.append(" ");
        }

        return stb;
    }

}

기억에 남길 것!

PriorityQueue는 poll로 해야지만 정렬이 되어 나오게 된다.
깊은 복사는 되도록이면 피하자...