[Java] 백준 1260번 : DFS와 BFS <Silver 2>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

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

1260번: DFS와 BFS

Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    void run() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] input = bf.readLine().split(" ");

        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        int V = Integer.parseInt(input[2]);

        boolean[][] graph = new boolean[N][N];

        for(int i = 0; i < M; i++){
            input = bf.readLine().split(" ");
            graph[Integer.parseInt(input[0])-1][Integer.parseInt(input[1])-1] = true;
            graph[Integer.parseInt(input[1])-1][Integer.parseInt(input[0])-1] = true;
        }

        DFS(graph,V);
        System.out.println();
        BFS(graph, V);
    }

    void DFS(boolean[][] graph, int Start){
        boolean[] visited = new boolean[graph.length];
        visited[Start - 1] = true;
        DFSUtil(graph, visited, Start);
    }

    void DFSUtil(boolean[][] graph, boolean[] visited, int Start){
        System.out.print(Start + " ");
        for(int i = 0; i < visited.length; i++){
            if(visited[i] == false && graph[Start-1][i] == true){
                visited[i] = true;
                DFSUtil(graph,visited,i+1);
            }
        }
    }

    void BFS(boolean[][] graph, int Start){
        boolean[] visited = new boolean[graph.length];
        visited[Start - 1] = true;
        Queue<Integer> queue = new LinkedList<>();
        int num = Start;

        queue.offer(Start);

        while(!queue.isEmpty()){
            num = queue.poll();
            System.out.print(num + " ");
            
            for(int i = 0; i < visited.length; i++){
                if(visited[i] == false && graph[num-1][i] == true){
                    visited[i] = true;
                    queue.offer(i+1);
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        Main my = new Main();
        my.run();
    }
}

---

Code 필수 요소

1. DFS 구현

2. BFS 구현

 

// DFS

재귀 호출 방식을 사용했다.

조건에 일치하는 값을 발견하면 해당 값으로 함수를 호출한다. 반복하다가 호출 할 값이 없어지면 재귀가 종료되며 모든 값 탐색을 종료한다.

원래라면 나온 값들을 어디 저장하거나 하겠지만 이건 단순 출력 문제여서 바로 출력했다.

 

// BFS

큐를 사용하는 방식을 했다.

조건에 일치하는 값을 발견하면 큐에 넣고, 스택에서 값을 하나씩 꺼내며 출력 및 탐색을 하는 방식이다.

큐가 비었다면 더이상 탐색할 값이 없는 것이기때문에 반복을 종료한다.

 

// 전체적 설명

그래프 탐색 알고리즘인 DFS와 BFS를 잘 알고있냐를 묻는 문제.

 

DFS와 BFS구현을 위한 가장 기본적인 visited 배열과 graph배열을 선언해주고 활용한다.

 

여기서 visited배열이란 탐색 과정에서 해당 요소를 탐색했는지 알려주는 배열이다. 이게 없다면 내가 탐색을 했는지 안했는지 몰라서 계속해서 탐색을 하게 된다. 내가 방문한 숫자의 인덱스를 true로 만들어줘서 내가 해당 번호를 방문햇다~를 기록한다.

 

graph배열이란 어느 숫자와 어느 숫자가 연결되어있는지를 나타내는거다. 예를들어 1과 2가 연결되어있다면 graph[0][1], graph[1][0]을 true로 만들어준다. 이렇게 될 경우 1에서 시작할때 2는 true이므로 연결되어있다는 것을 알 수 있다 반대도 마찬가지다. 연결되어있기때문에 해당 숫자로 탐색을 진행할 수 있다.

 

 

DFS와 BFS란?

https://naemamdaelo.tistory.com/37

알고리즘 - 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

이거 은근 자주 쓰인다. 이걸 활용하는게 진짜 많이 쓰이니까 구현 방법을 꼭 외우고 있기를 추천한다.

 

-꿑-