[백준 1260] DFS와 BFS(Java)

[백준 1260] DFS와 BFS(Java)

1260번: DFS와 BFS

1260번: DFS와 BFS

 

 

해결 방법

1트

처음에 엄청 쉽다고 생각해서 기계적으로 DFS, BFS를 구현했습니다.
그런데 틀렸습니다….😭

이유가 뭘까… 생각하고 다시 문제를 읽어보았습니다.

정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,

 

문제의 조건이 있었습니다..

 

2트

정점 번호가 작은 것부터 방문하려면 어떻게 해야할까…

고민한 결과
DFS는 모든 노드를 탐색하고,
그 경로를 우선 순위 큐에 담아 반환하는 형식을 생각했습니다.!!

public static void dfs(int start, int depth, String path) {

        if(visited[v]) {
            // 우선순위 큐에 삽입
            pq.offer(path);
            return;
        }

        // 인접 노드 탐색
        for(Integer node : lists[start]) {
            if(!visited[node]) {
                // 방문
                visited[node] = true;
                // dfs 수행
                dfs(node, depth + 1, path + "->" + node);
                // 방문 이력 삭제
                // 전체 경로를 탐색하기 위함
                visited[node] = false;
            }
        }

}

 

BFS는 노드, 경로, 깊이를 정의하는 클래스를 선언하고, 이를 우선 순위 큐를 이용하여 해결하려고 했습니다.
우선 순위 큐의 정렬 조건은 다음과 같이 생각했습니다.
만약 깊이가 같은 경우 노드를 기준으로 오름차순!
그외는 깊이를 기준으로 오름차순!

Queue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                  // 깊이가 같으면 정점 번호가 작은 것 부터 방문해야 한다.
                if(o1.getDepth() == o2.getDepth()) {
                    return Integer.compare(o1.getNode(), o2.getNode());
                }
                // 그외 깊이를 기준으로 오름차순
                return Integer.compare(o1.getDepth(), o2.getDepth());
            }
        });

 

결과는….
메모리 초과…😭

 

3트

메모리 초과를 해결하지 못하고, 결국 다른 사람들의 풀이를 보았습니다. 😳

생각보다 문제는 간단했습니다.🤷🏻‍♂️

정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하라고 했으니,
정점을 담은 인접 리스트를 인접 노드를 기준으로 오름차순으로 정렬해주면 됩니다.!

// 오름차순 정렬
for(int i = 1; i <= n; i++) {
    Collections.sort(lists[i]);
}

 

그러면 자연스럽게 정점이 작은 것부터 탐색하게 됩니다!!

풀이

public class Quiz1260 {
      // 메모리 사용을 줄이기 위함
    static int n;
    static int m;
    static int v;
    static List<Integer>[] lists;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    // 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        lists = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            lists[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            // 양방향
            lists[node1].add(node2);
            lists[node2].add(node1);
        }

        // 오름차순 정렬
        for(int i = 1; i <= n; i++) {
            Collections.sort(lists[i]);
        }

        // 방문 이력 배열 초기화
        visited = new boolean[n+1];
        visited[v] = true;
        sb.append(v).append(" ");
        // dfs 수행
        dfs(v, 0, String.valueOf(v));

        // 방문 이력 배열 초기화
        visited = new boolean[n+1];
        bfs(v);

        // 출력~
        System.out.print(sb);
        sb.setLength(0);
        br.close();
    }

    private static void bfs(int v) {
        Queue<Integer> queue = new ArrayDeque<>();
        // 초기화
        queue.offer(v);
        sb.append("\n");

        while (!queue.isEmpty()) {
            // 노드를 꺼낸다.
            Integer poll = queue.poll();
            // 방문 이력이 없으면
            if(!visited[poll]) {
                // 방문
                visited[poll] = true;
                // 경로 저장
                sb.append(poll).append(" ");

                // 인접 노드 탐색
                for (Integer node : lists[poll]) {
                    queue.offer(node);
                }
            }
        }
    }

    private static void dfs(int start, int depth, String path) {
        // 인접 노드 탐색
        for(Integer node : lists[start]) {
            // 방문 이력이 없으면
            if(!visited[node]) {
                // 방문 처리
                visited[node] = true;
                // 경로 저장
                sb.append(node).append(" ");
                // dfs 수행
                dfs(node, depth + 1, String.valueOf(node));
            }
        }
    }
}

 

DFS, BFS를 응용할 수 있는 문제는 무궁무진 한 것 같다…😭
일단 많이 풀어서 경험치를 쌓는게 좋은것 같다.
화이팅!