[BOJ 1260] DFS와 BFS

[BOJ 1260] DFS와 BFS

 

1. 문제 : Link

dfs 와 bfs 묻는 문제

 

2. 풀이

이제 슬 감이 잡힌다 (2023.04.07)

link[i][j] = link [j][i] = 1 (연결된 선이 있다고 표시하는게 중요)

* E를 순회하는 것이 아님 !
* 연결된 간선 중 다음 숫자가 작은 것 부터 탐색해야하기 때문

 

3. 코드

package baekjoon;

import java.io.IOException;
import java.util.*;
public class Main {
    //함수에서 사용할 변수들
    static int[][] link; //간선 연결상태
    static boolean[] visited; //확인 여부
    static int V; //정점개수
    static int E; //간선개수
    static int start; //시작정점

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        E = sc.nextInt();
        start = sc.nextInt();

        link = new int[1001][1001]; //좌표를 그대로 받아들이기 위해 +1해서 선언
        visited = new boolean[1001]; //초기값 False

        //간선 연결상태 저장
        for(int i = 0; i < E; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

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

        dfs(start); //dfs호출

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

        bfs(); //bfs호출
    }

    //시작점을 변수로 받아 확인, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출
    public static void dfs(int cur) {
        visited[cur] = true;
        System.out.print(cur + " ");

        for(int j = 1; j <= V; j++) {
            if(link[cur][j] == 1 && !visited[j]) {
                dfs(j);
            }
        }
    }

    public static void bfs() {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(start);
        visited[start] = true;
        System.out.print(start + " ");

        while(!queue.isEmpty()) {
            int cur = queue.poll();

            for(int j = 1; j <= V; j++) {
                if(link[cur][j] == 1 && !visited[j]) {
                    queue.offer(j);
                    visited[j] = true;
                    System.out.print(j + " ");
                }
            }
        }
    }
}