실2 1260 DFS와 BFS - 그래프의 탐색

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

1260번: DFS와 BFS

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    //함수에서 사용할 변수들
    static int[][] a; //간선 연결상태
    static boolean[] check; //확인 여부
    static int n; //정점개수
    static int m; //간선개수
    static int start; //시작정점

    public static void main(String[] args) throws IOException {

        //인접리스트 구현
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();

        a = new int[1001][1001]; //좌표를 그대로 받아들이기 위해 +1해서 선언
        check = new boolean[1001]; //초기값 False
        
        //간선 연결상태 저장
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            a[x][y] = a[y][x] = 1;
        }

        //문제 풀이 시작
        dfs_1260(start);    //dfs

        check = new boolean[1001];   //확인상태 초기화
        System.out.println();   //줄바꿈

        bfs_1260();    //bfs
    }

    //시작점을 변수로 받아 확인, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출
    public static void dfs_1260(int x) {
        // 1. check[x] = true => 방문후 표시(dfs의 목적은 모든 정점을 1번씩 방문하는 것이므로, 방문을 표시해야 한다.)
        check[x] = true;
        System.out.print(x + " ");

        // 인접리스트 방식
        // 2. x->i => x에서 i로 가는 다음 정점을 찾아줘야 한다. 이를 만족하는 조건은 아래 2가지이다.
        // 2-1) a[x][i]==1 => x와 i 사이에 간선이 존재한다.
        // 2-2) check[i]==false => i를 방문한 적 없어야 한다.
        // 위 2가지 조건을 만족하면 x->i(x에서 i로 이동 가능) 이므로 dfs(i)를 호출한다.
        for (int i = 1; i <= n; i++) {
            if (a[x][i]==1 && check[i]==false) {
                dfs_1260(i);
            }
        }
    }

    private static void bfs_1260() {
        Queue<Integer> q = new LinkedList<Integer>();
        // 1. 시작점
        // check[start] = true => 1을 방문한 것으로 표시
        // q.offer(start) => 1을 큐에 넣음
        check[start] = true; q.offer(start);
        System.out.print(start + " ");

        // 2. 범위 : 큐가 비어있지 않은 동안 (=큐가 비워지면 종료)
        while (!q.isEmpty()) {
            // 3. 큐의 처음값을 x로 선언.
            // int x = q.poll() => 큐의 처음 값을 제거한다.
            int x = q.poll();
//            int x = q.peek(); q.poll();

            // 인접리스트 방식
            // 4. 이용 가능한도를 i에 대해 설정한다
            // x->i => x에서 i로 가는 다음 정점을 찾아줘야 한다. 이를 만족하는 조건은 아래 2가지이다.
            // 4-1) a[x][i]==1 => x와 i 사이에 간선이 존재한다.
            // 4-2) check[i]==false => i를 방문한 적 없어야 한다.
            for (int i = 1; i <= n; i++) {
                if (a[x][i]==1 && check[i]==false) {
                    // 위 2가지 조건을 만족한다면, 방문한 것을 표시한다(BFS의 경우 큐를 제거하는 시점에, 방문후로 표시해야 한다(DFS와 방문 표시 위치가 다름))
                    check[i] = true;
                    // 큐에 넣어준다.
                    q.offer(i);
                    System.out.print(i + " ");
                }
            }
        }
    }

}