[백준 (Baekjoon)] (java) 문제 1260 - dfs & bfs

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

1260번: DFS와 BFS

1) 접근법

문제 이름에서부터 보이듯이 bfs와 dfs를 모두 사용하는 문제이다. 인접 행렬 graph와 1차원 int 배열 visited를 사용하였으며 dfs는 stack대신 재귀함수를 이용하고 bfs는 queue를 이용해 풀었다.

 

2) 시간 복잡도

인접 리스트가 아닌 행렬로 풀었기에 dfs와 bfs모두 O(V^2)가 걸린다. 

 

3) 이 문제로 얻은 것 + 소감

DFS와 BFS에 관한 이해를 얻었고 정석대로 풀고싶어서 dfs를 stack으로 푸는 코드들은 없는지 찾아보았으나 사람들이 하지않는데는 이유가 있다는것을 알았다.

시간 복잡도는 정점과 간선의 갯수 모두 1~1000 사이로 큰 수는 아니여서 인접 행렬도 풀어도 가능했다. 그러나 정점과 간선의 갯수가 더 많아지는 것을 대비하여 인접 리스트로 풀어보는 것도 연습을 해야겠다.

 

4) 코드

package BFS_DFS;

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

public class p1260_bfsdfs {
    static BufferedReader br;

    static Queue<Integer> bfs;

    static int n,m,v;
    static int[][] graph;
    static int[] visited;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tok = new StringTokenizer(br.readLine());
        n = Integer.parseInt(tok.nextToken());
        m = Integer.parseInt(tok.nextToken());
        v = Integer.parseInt(tok.nextToken());

        graph = new int[n+1][n+1];
        for(int i=0;i<n+1;i++){
            Arrays.fill(graph[i],0);
        }
        visited = new int[n+1];
        Arrays.fill(visited,0);
        visited[v] = 1;

        for(int i=0;i<m;i++){
            tok = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(tok.nextToken());
            int b = Integer.parseInt(tok.nextToken());

            graph[a][b] = graph[b][a] = 1;
        }

        dfs(v);
        System.out.println();

        Arrays.fill(visited,0);
        visited[v] = 1;

        bfs();
    }

    public static void dfs(int current){
        System.out.print(current+" ");

        for(int j=1;j<n+1;j++){
            if(current!=j && graph[current][j]==1 && visited[j]==0){
                visited[j]=1;
                dfs(j);
            }
        }
    }

    public static void bfs(){
        bfs = new LinkedList<Integer>();
        bfs.offer(v);

        while(!bfs.isEmpty()){
            int current = bfs.poll();
            System.out.print(current+" ");

            for(int j=1;j<n+1;j++){
                if(current!=j && graph[current][j]==1 && visited[j]==0){
                    visited[j]=1;
                    bfs.offer(j);
                }
            }
        }
    }
}