[백준] 1260번 : DFS와 BFS

DFS와 BFS

---

풀이 방법

그래프 탐색의 가장 대표적인 DFS와 BFS를 구현하는 문제였다.

구현 방법은 정점을 인접 행렬에 저장하고 DFS는 재귀를 통해 쉽게 구현했고, BFS는 Queue를 이용해서 구현했다.

다른 블로그를 찾아봐도 이렇게 구현하는 것이 대표적인 구현 방법 인 것 같았다.

인접행렬 vs 인접리스트

인접 행렬

• 모든 노드의 관계를 저장하기 때문에 메모리가 불필요하게 낭비
• 하지만 탐색에 효과적

인접리스트

• 연결된 정보만을 저장하기에 메모리가 효율적
• 탐색에 있어서 모든 데이터를 확인해야 한다.

크기가 그렇게 크지 않기 때문에 인접 행렬로 선택했다.

느낀 점

DFS와 BFS는 자주 나오는 자료구조이기에 구현을 확실히 이해하고 가자..

---

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][] graph = new int[1001][1001];
    static boolean[] visited = new boolean[1001];
    static int n;

    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()); //정점
        int m = Integer.parseInt(st.nextToken()); //간선
        int v = Integer.parseInt(st.nextToken()); //시작정점

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            init(a,b);
        }

        dfs(v);
        System.out.println();
        bfs(v);
    }
    static void init(int a, int b){
        graph[a][b] = graph[b][a] = 1;
    }
    static void dfs(int node){
        visited[node] = true;
        System.out.print(node + " ");

        for(int i=1;i<=n;i++){
            if(!visited[i] && graph[node][i] == 1){
                dfs(i);
            }
        }
    }
    static void bfs(int node){
        visited = new boolean[1001];
        Queue<Integer> queue = new LinkedList<>();
        visited[node] = true;
        queue.add(node);

        while(!queue.isEmpty()){
            int v = queue.remove();
            System.out.print(v + " ");

            for(int i=1;i<=n;i++){
                if(!visited[i] && graph[v][i] == 1){
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}