[백준][자바] 1260번 DFS와 BFS

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

1260번: DFS와 BFS

//package Practice.P1260;

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

public class Main {
    static int N, M, V;
    static int[] ch;
    static Queue<Integer> Q = new LinkedList<>();
    static ArrayList<Integer> adj[];

    public static void main(String[] args) throws IOException {
    //    System.setIn(new FileInputStream("src/Practice/P1260/input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        ch = new int[N + 1];
        adj = new ArrayList[N + 1];
        for(int i = 0 ; i <= N; i++){
            adj[i] = new ArrayList<>();
        }

        for(int i = 0 ; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int from =  Integer.parseInt(st.nextToken());
            int to =  Integer.parseInt(st.nextToken());

            if(adj[from].size() == 0 && adj[to].size() == 0){
                adj[from].add(to);
                adj[to].add(from);
            }

            int j;
            for(j = 0; j < adj[from].size(); j++){
                if(to < adj[from].get(j)){
                    break;
                }
            }
            adj[from].add(j, to);

            for(j = 0; j < adj[to].size(); j++){
                if(from < adj[to].get(j)){
                    break;
                }
            }
            adj[to].add(j, from);
        }

        ch[V] = 1;
        System.out.print(V + " ");
        dfs(V, 1);
        System.out.println();

        // BFS
        int x;
        ch = new int[N + 1];
        ch[V] = 1;
        Q.add(V);
        System.out.print(V + " ");

        while(!Q.isEmpty()){
            x = Q.poll();
            for(int i = 0; i < adj[x].size(); i++){
                if(ch[adj[x].get(i)] == 0){
                    ch[adj[x].get(i)] = 1;
                    System.out.print(adj[x].get(i) + " ");

                    Q.add(adj[x].get(i));
                }

            }
        }

    }

    static void dfs(int v, int n){
        if(n == N){
            return;
        }else{
            for(int i = 0 ; i < adj[v].size(); i++){
                if(ch[adj[v].get(i)] == 0){
                    System.out.print(adj[v].get(i) + " ");

                    ch[adj[v].get(i)] = 1;
                    dfs(adj[v].get(i), n + 1);
                }
            }
        }
    }
}

dfs를 먼저, 그리고 bfs를 그 후에 탐색하면서 print로 찍어내는 것이 문제였습니다.

간선 정보는 arraylist의 배열을 만들어서 인접리스트에 담았습니다.

dfs는 따로 함수를 만들어주었고 bfs는 main에서 큐로 구현했습니다.

 

우선 문제의 다음 조건이 핵심입니다.

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

위 조건을 만족시키면서 탐색하기 위해서는 두 가지 방법이 존재할 것입니다.

1. 간선 정보를 인접리스트에 담을 때 정렬해서 담는다.

2. 아무렇게나 간선 정보를 담은 후, 탐색할 때 오름차순으로 탐색한다.

 

저는 1번 방법으로 접근했습니다.

그 이유는 탐색을 두 번 하기 때문에 이중으로 시간복잡도가 증가할 것이라 생각했기 때문입니다.

탐색하기 전에 정렬을 해놓는 1번 방법을 쓴다면,

탐색을 1000번 할 때도 한 번의 정렬만으로 가능하겠죠?

 

for(int i = 0 ; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int from =  Integer.parseInt(st.nextToken());
            int to =  Integer.parseInt(st.nextToken());

            if(adj[from].size() == 0 && adj[to].size() == 0){
                adj[from].add(to);
                adj[to].add(from);
            }

            int j;
            for(j = 0; j < adj[from].size(); j++){
                if(to < adj[from].get(j)){
                    break;
                }
            }
            adj[from].add(j, to);

            for(j = 0; j < adj[to].size(); j++){
                if(from < adj[to].get(j)){
                    break;
                }
            }
            adj[to].add(j, from);
        }

adj 인접리스트에 간선이 들어가있지 않아서 size가 0일 때를 따로 빼주어서

간선이 우선 들어가도록 해주어야 합니다. 그 후에 대소비교를 하면서 간선을 넣는 것이죠.

따로 size가 0일 때를 빼주지 않는다면,

adj[from].size() 와 adj[to].size() 는 0을 유지하기 때문에

대소비교하면서 간선을 넣는 반복문이 돌아가지를 않습니다.

 

그리고나서 size가 1 이상일 때는 기존 간선의 정점 번호와 대소비교를 해서

정점 번호가 오름차순이 되도록 add를 해줍니다.

->  add(인덱스, 넣을 값) 을 해주면 인덱스에 값이 들어가면서 뒤로 자동으로 밀려납니다.

 

양방향 간선이기에 from과 to 동일하게 작업해줍니다.

 

dfs에서는 현재까지 탐색한 정점의 개수를 담는 n을 1증가시키면서 매개변수로 넘겨줍니다.

그리고 n이 정점의 총 개수가 되면 return 시키면서 탐색을 종료합니다.

 

방문여부를 저장하는 ch 배열은  탐색 후 0으로 풀어주지 않습니다!!!!!!!!!!

그래야 문제의 조건을 만족하면서, 한 번의 완전탐색을 한 후에 종료합니다.

만약 ch배열을 0으로 풀어줘서 dfs를 반복시킨다면 완전 탐색이 여러번 반복됩니다.