[백준] dfs/bfs - 1260번 DFS와 BFS(Java)

문제링크

1260번: DFS와 BFS

 

 

접근한 방법

• 문제에 대놓고 DFS와 BFS로 적혀있으므로 각 알고리즘으로 구현

 

---

풀이방법

dfs

1. dfs 메소드를 선언하여 파라미터를 정점 번호로 받는다.
2. 현재 정점을 방문 처리하고,
3. 그 정점과 연결되어 있으며 방문하지 않은 정점을 방문한다 (dfs 메소드를 호출한다).

bfs

1. 탐색 시작 정점을 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 정점을 꺼내 해당 정점의 인접 정점 중에서 방문하지 않은 정점을 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

---

소스코드 작성 방법

• 정점의 수, 간선의 수, 탐색을 시작할 정점의 번호, 그래프 정보 (정점이 연결된 정보), 정점 방문 여부 (dfs, bfs 따로), 결과를 담는 리스트(dfs, bfs 따로)를 전역 필드로 선언한다.
• 정점은 1번부터 시작이므로 배열의 크기는 모두 n+1로 초기화 시켜준다.
• 입력을 받을 때 graph는 인접행렬로 구현한다.

dfs

• dfs 메소드의 인자를 정점 번호(cur)로 받는다. (cur : 현재 정점을 나타냄)
• dfsVisited[cur] = true로 하여 방문 처리
• dfsList에 해당 정점 담기 (결과 출력을 위함)
• 인접행렬로 구현했기 대문에 1번 정점부터 연결되어있는 지를 확인
  • 그래프가 연결되어있고 (graph[cur][i] = 1) 아직 방문하지 않았다면 (dfsVisited[i] = false) 다음 정점을 탐색
    -> dfs(i) 호출

bfs

• 큐를 선언
• 큐에 현재 정점(cur) 삽입
• bfsVisited[cur] = true로 하여 방문처리
• while문으로 q가 비어있지 않을 때까지 큐에서 정점을 꺼내 해당 정점의 인접 정점 중에서 방문하지 않은 정점을 모두 큐에 삽입하고 방문 처리를 한다.
  • 인접행렬로 구현했기 때문에 1번 정점부터 연결되어있는 지를 확인
  • 그래프가 연결되어있고 아직 방문하지 않았다면 해당 정점을 큐에 삽입
  • bfsVisited[i] = true로 해당 정점 방문 처리

---

실수한점

입력받을 때 인접리스트 또는 인접행렬형태로 입력을 받아야하는데, 1차월 배열로 입력을 받았다.

인접리스트와 인접행렬 알아보기

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.*;

public class Q_1260_DFSandBFS_20210630 {
    public static int n,m,v; // n : 정점의 개수, m : 간선의 개수, v : 탐색을 시작할 정점의 번호
    public static int[][] graph; // 그래프 정보
    public static boolean[] dfsVisited; // 정점 방문 여부 체크
    public static boolean[] bfsVisited; // 정점 방문 여부 체크
    public static List dfsList; // dfs 탐색 결과
    public static List bfsList; // bfs 탐색 결과

    public static void solution(){
        dfs(v);
        bfs(v);
    }

    public static void dfs(int cur){
        dfsVisited[cur] = true; // 현재 정점 방문 처리
        dfsList.add(cur); // 출력하기 위한 결과 넣기

        // 인접행렬로 구현했기 때문에 1번 정점부터 연결되어있는 지를 확인
        for(int i=1 ; i<=n ; i++){
            // 그래프가 연결되어있고 아직 방문하지 않았다면 다음 정점 탐색
            if(graph[cur][i] == 1 && !dfsVisited[i]) {
                dfs(i);
            }
        }
    }

    public static void bfs(int cur){
        Queue<Integer> q = new LinkedList<>(); // bfs니까 큐로 구현
        q.add(cur); // 큐에 현재 정점 삽입
        bfsVisited[cur] = true; // 현재 정점 방문 처리

        while (!q.isEmpty()) {
            int k = q.poll(); // 큐에서 꺼내기
            bfsList.add(k); // 출력하기 위한 결과 넣기

            // 인접행렬로 구현했기 때문에 1번 정점부터 연결되어있는 지를 확인
            for(int i=1 ; i<=n ; i++) {
                // 그래프가 연결되어있고 아직 방문하지 않았다면 해당 정점을 큐에 삽입
                if (graph[k][i] == 1 && !bfsVisited[i]){
                    q.add(i);
                    bfsVisited[i] = true; // 해당 정점 방문 처리
                }
            }
        }
    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        graph = new int[n + 1][n + 1];
        dfsVisited = new boolean[n + 1];
        bfsVisited = new boolean[n + 1];
        dfsList = new ArrayList();
        bfsList = new ArrayList();

        // 인접행렬로 구현
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int one = Integer.parseInt(st.nextToken());
            int two = Integer.parseInt(st.nextToken());
            graph[one][two] = 1;
            graph[two][one] = 1;
        }

        solution();

        // 출력
        for(int i=0 ; i<dfsList.size() ; i++){
            bw.write(dfsList.get(i)+" ");
        }
        bw.write("\n");
        for(int i=0 ; i<bfsList.size() ; i++){
            bw.write(bfsList.get(i)+" ");
        }

        br.close();
        bw.close();
    }
}