[백준] 1260. DFS와 BFS (Java)

문제

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

1260번: DFS와 BFS

 

 

알고리즘

DFS, BFS

 

 

풀이

그래프 간의 연결 관계를 인접리스트로 설정해주고, 정점 작은 것을 먼저 방문해줘야 하기 때문에 정렬을 해줬다. 그리고 DFS, BFS를 통해 탐색을 진행시켰다.

인접리스트를 이용한 풀이, 배열을 사용한 풀이 2가지로 풀어보았다.

 

 

코드

[인접리스트를 이용한 풀이]

package com.company;

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

public class Test_DFS_BFS {
    static int N, M, S;
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static List<Integer>[] graph = new ArrayList[1001];
    static boolean[] visited = new boolean[1001];

    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

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

        for(int i=0; i<M; i++){
            st = new StringTokenizer(bf.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph[from].add(to);
            graph[to].add(from);
        }

        //이동 경우의 수가 다수 존재할 경우 작은 정점부터 이동해야 하므로 인접 리스트를 오름 차순으로 정렬한다.
        for(int i=1; i<=N; i++){
            Collections.sort(graph[i]);
        }

        DFS(S);
        sb.append("\n");

        Arrays.fill(visited,false);
        BFS();
    }

    public static void DFS(int start){
        visited[start]= true;
        sb.append(start+" ");
        for(int i=0; i<graph[start].size(); i++){
            int node = graph[start].get(i);
            if(visited[node]) continue;
            DFS(node);
        }
    }

    public static void BFS() throws IOException {
        Queue<Integer> q = new LinkedList<>();
        q.add(S);
        visited[S]=true;
        while(!q.isEmpty()){
            int cur = q.poll();
            sb.append(cur+" ");
            for(int i=0; i<graph[cur].size(); i++){
                int next =graph[cur].get(i);
                if(visited[next]) continue;
                visited[next] =true;
                q.add(next);
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }
}

 

 

[배열을 이용한 풀이]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int vertex = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
        int[][] map = new int[vertex+1][vertex+1];
        boolean[] visited = new boolean[vertex+1];
        
        //인접 행렬을 만드는 것
        for(int i=0; i<edge; i++) {
            st = new StringTokenizer(br.readLine());
            int a1 = Integer.parseInt(st.nextToken());
            int a2 = Integer.parseInt(st.nextToken());
            
            map[a1][a2] = 1;
            map[a2][a1] = 1;
        }
        
        dfs(map, visited, start);
        System.out.println();
        //dfs를 통해 visited가 true가 되었으므로 false로 바꿔준다.
        Arrays.fill(visited, false);
        bfs(map, visited, start);
    }
    
    public static void dfs(int[][] map, boolean[] visited, int v) {
        visited[v] = true;
        System.out.print(v + " ");
        //재귀를 사용해 다음 노드를 방문하면 그곳에서 다시 dfs를 시작한다.
        //방문하는 기준은 노드가 연결되어 있으면서 그 노드를 방문하지 않았을 경우이다.
        for(int i=1; i<visited.length; i++) {
            if(map[v][i] == 1 && !visited[i]) {
                dfs(map, visited, i);
            }
        }
    }
    
    public static void bfs(int[][] map, boolean[] visited, int v) {
        //큐를 사용하여 bfs를 실행하는 번호를 입력해준다.
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(v);
        visited[v] = true;
        
        while(!q.isEmpty()) {
            v = q.poll();
            System.out.print(v + " ");
            
            for(int i=1; i<=visited.length-1; i++) {
                if(map[v][i] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}