[DFS/BFS][Java][BOJ] #1260. DFS와 BFS

#DFS #BFS  #Silver2

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

🌷 문제 설명

✏️ 백준 연습문제: #1260. DFS와 BFS
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

⌨️ 입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

🖨️ 출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

입출력 예

입력	출력
4 5 1 1 2 1 3 1 4 2 4  3 4	1 2 4 3 1 2 3 4
5 5 3 5 4 5 2 1 2 3 4  3 1	3 1 2 5 4 3 1 4 2 5

 

💡 해결 포인트

1.  DFS
- Stack

2. BFS
- Queue

 

🌷 내 코드

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

public class BOJ_1260 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("example.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 번째 줄 입력
        String[] firstLine = br.readLine().split(" ");
        int N = Integer.parseInt(firstLine[0]); // 정점의 갯수
        int M = Integer.parseInt(firstLine[1]); // 간선의 갯수
        int V = Integer.parseInt(firstLine[2]); // 탐색을 시작할 정점의 번호

        // 인접 리스트 생성
        int[][] graph = new int[N + 1][N + 1]; // 0번 인덱스는 사용하지 않음
        for (int i = 0; i < M; i++) { 
            String[] edge = br.readLine().split(" "); // 간선 정보
            int a = Integer.parseInt(edge[0]); // 간선의 시작 정점
            int b = Integer.parseInt(edge[1]);
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        // DFS
        boolean[] visited = new boolean[N + 1];
        Stack<Integer> stack = new Stack<>(); // 스택 생성
        stack.push(V);

        while (!stack.isEmpty()) {
            int v = stack.pop(); // 정점을 꺼내서
            if (!visited[v]) { // 방문하지 않은 정점이라면
                visited[v] = true; // 방문 
                System.out.print(v + " "); // 출력
                for (int i = N; i > 0; i--) {
                    if (graph[v][i] == 1 && !visited[i]) {
                        stack.push(i);
                    }
                }
            }
        }
        
        System.out.println(); // 줄바꿈
        
        // BFS
        visited = new boolean[N + 1];
        Queue<Integer> queue = new LinkedList<>(); // 큐 생성
        queue.add(V); // 시작 정점을 큐에 넣음 
        visited[V] = true; // 방문 표시

        while (!queue.isEmpty()) { // 큐가 빌 때까지
            int v = queue.poll(); // 큐에서 정점을 꺼내서
            System.out.print(v + " "); // 출력
            for (int i = 1; i <= N; i++) {
                if (graph[v][i] == 1 && !visited[i]) {
                    queue.add(i); // 방문하지 않은 정점을 큐에 넣음
                    visited[i] = true; // 방문 표시
                }
            }
        }

    }
}

 

 

🌷 코멘트

아... 진짜 그래프... 난 진짜 일일히 쓰는거 아니면 이해가 아직도 안됨. 낼 반차인 김에 각잡고 앉아서 정리하던지 해야지ㅠㅠ 분명 자료구조 들을 때는 내가 이해한 줄 알았는데 또 이렇게 머릿속이 백지가 되고 말았다...

그리고 야 자바 넌 뭐 큐랑 스택일 때 쓰는 메서드까지 다르고 그러니ㅠ 진짜 왜 자바왕국인거야??? 스프링 니가몬데!!!!!

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!
~대가리 꽃밭인 디지털 노마드가 꿈이예요~
🧚‍♀️ Gyumin Lee
📧 gyumin.q.lee@gmail.com