3주차 : DFS/BFS 문제1

✔ BOJ_1260

--

풀이과정

: DFS/BFS 문제는 무작정 잡고 풀기엔 개념이 잘 안잡힌 것 같아서 풀이를 참조해서 풀었다 :( 최대한 참조 코드를 분석하는 방식으로 풀어보려고 한다.

개념

DFS, BFS에서 알아야하는 개념이 바로 인접행렬 과 인접리스트 이다.
1) 인접행렬
: 여기서는 A[1][4]가 1인지만 알면 1번 꼭지점과 4번 꼭지점이 연결되어있는지 판단할 수 있다. 하지만 이는 꼭지점의 개수가 적을 때만 가능하다. 대부분 시작점에서 도착점을 찾는 방식의 탐색을 많이 하게 되는데, 이 개수는 v가 많아지면 많아질 수록 그만큼 탐색 시간이 오래걸리게 되고, 매번 연결 지점을 찾으려면 v 크기만큼 돌아봐야하므로 시간초과에 걸릴 가능성이 높아진다.

2) 인접 리스트
: 자신의 노드에서 갈 수 있는 노드를 가지고 있다고 생각하면 된다. 인접 리스트는 내가 어디로 갈지를 알려주기만 하면되므로 내가 찾으면 되기 때문이다. 즉, A노드와 B노드가 연결되어 있는지를 알고 싶으면 인접 리스트는 A에는 B가 있는지, B에는 A가 있는지를 파악해서 연결되어 있는 것을 확인하면 된다.

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

public class BOJ_1260 {
    // 인접행렬로 구현
    static int map[][];
    static boolean[] visit;
    static int n,m,v;

    // stack에 하나 넣고
    // 꺼내고 걔의 자식 노드들 다 스택에 넣고 출력
    // 그리고 스택에서 하나 꺼내고 걔의 자식노드 추가하고 꺼낸애 출력하고
   public static void dfs(int i){
        visit[i] = true;
        System.out.print(i+" ");
        for(int j=1; j<n+1; j++){
            if((map[i][j] == 1 && visit[j]) == false){
                dfs(j);
            }
        }
    }

    /// 밑에서 하나 꺼내고 그 노드의 자식들 큐에 추가하고 출력해주기
    public static void bfs(int i){
        Queue<Integer> que = new LinkedList<Integer>();
        // offer : 추가하는데 이미 큐가 꽉 찬 경우 false를 반환한다.
        que.offer(i);
        visit[i] = true;
        while(!que.isEmpty()){
            // 삭제
            int temp = que.poll();
            System.out.print(temp+" ");
            for(int k=1;k<=n;k++){
                if(map[temp][k]==1 && visit[k]==false){
                    que.offer(k);
                    visit[k] = true;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n= Integer.parseInt(st.nextToken());
        m= Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());
        map = new int[n+1][n+1];
        visit = new boolean[n];

        //초기화
        // 근데 약간 굳이..
        for(int j=0; j<n+1; j++){
            Arrays.fill(map[j],0);
        }
        Arrays.fill(visit,false);

        // 간선의 개수
        for(int i=0; i<m;i++){
            String edge = br.readLine();
            StringTokenizer st1 = new StringTokenizer(edge, " ");
            int a = Integer.parseInt(st1.nextToken());
            int b = Integer.parseInt(st1.nextToken());
            map[a][b] = 1;
            map[b][a] = 1;
        }

        dfs(v);
        System.out.println();
        Arrays.fill(visit,false);
        bsf(v);
    }
}

또 다른 참조 코드는 아래와 같다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_1260_ad {
    public static int[][] arr;
    public static boolean[] visit;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int point = sc.nextInt();
        int line = sc.nextInt();
        int start = sc.nextInt();

        arr = new int[point+1][point+1];

        for(int i=1;i<=line;i++){
            int a=sc.nextInt();
            int b =sc.nextInt();
            arr[a][b]=1;
            arr[b][a]=1;
        }

        // dfs
            visit = new boolean[point+1];
            dfs(start);
            System.out.println();
        // bfs
            visit = new boolean[point+1];
            bfs(start);
    }
    public static void dfs(int start){
        visit[start] = true;
        System.out.print(start + " ");
        if(start == arr.length){
            return;
        }
        for(int a=1; a<arr.length;a++){
            if(arr[start][a]==1 && visit[a] ==false){
                // 자식인데 아직 방문 안했으면
                dfs(a);
            }
        }
    }

    public static void bfs(int start){
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(start);
        visit[start]=true;
        System.out.print(start + " ");
        while(! que.isEmpty()){
            int temp = que.poll();
            for(int i=1;i<arr.length;i++){
                if(arr[temp][i] ==1 && visit[i]==false){
                    que.add(i);
                    visit[i]=true;
                    System.out.print(i+" ");
                }
            }
        }
    }
}