BOJ 1260번 DFS BFS 문제 자바 풀이

BOJ 1260번 DFS BFS 자바(java) 풀이

• 랭크 : 실버1
• 백준 온라인 저지(BOJ) 1260 DFS BFS 문제 자바 풀이
• 백준 1260 DFS BFS 문제
  
  
  

문제정리

N M V(정점의 개수, 간선의 수, 시작할 정점 번호)
연결 정보들이 주어진다.
그래프 정보들을 가지고 dfs와 bfs로 순회하여 순서대로 출력하기

문제풀이

이 문제는 정점의 연결 상태를 적절한 자료형으로 저장하여 그래프를 탐색하는 문제입니다.
저는 그래프의 연결 상태를 인접 그래프(adjancy graph)형태로 저장하여 탐색하였습니다.

인접 행렬

다음과 같은 인접 행렬가 주어졌습니다. 무엇을 나타내는 걸까요??

010
101
010

0. adj[i][j] = 1 이라면 점 i와 j는 연결되어 있다. 0이면 연결되어 있지 않다.
1. 3x3이므로 3개의 점의 연결관계를 나타내었음을 알 수 있다.
2. 또한 (0,2)의 값이 1로 되어 잇으므로 0번째 점과 2번째 점이 연결되어 있음을 알 수 있다. (다른점도 마찬가지)
3. 주대각선 기준 대칭이다. (1,0)이 연결되어 있다면 (0,1)도 연결되어 있기 때문이다. -> 무방향 그래프일 경우
   즉 이는 0과 1로만 써있는 행렬일 뿐이지만 그래프의 연결 정보입니다!!

bfs

이는 방문하는 점에서 붙어있는 정점들을 방문하고 들어가며 방문해나간다.
Queue를 이용해서 구현하였습니다.
bfs의 기본형태이며 여기서 for문 안의 if문을 어떻게 하냐에 따라 다양한 문제에 적용할 수 있습니다.

1. 방문하는 점을 queue에 집어넣는다.
2. queue에서 빼나가며 그와 연결된 점(방문하지 않은)을 찾아서 바로 방문한다.
3. 방문하는 점은 queue에 넣고 바로 방문 처리합니다.
   
   
   

dfs

이는 방문하는 점에서 붙어있는 점을 바로 물고 들어가서 방문한다. 그래서 깊이 내려가기 때문에 깊이 우선 탐색(depth first search) 입니다.
이는 재귀를 통해 구현하였습니다.

1. 시작점과 연결되 있는 점 중에 가장 작은 정점번호를 가지는 것 부터 방문한다.(출력)
2. 재귀로 물고 들어가서 그와 연결된 점을 다시 방문하고(방문하지 않은 점만) 다시 물고들어간다.
3. 이렇게 계속 물고 모든 점들을 방문할때까지 깊숙히 내려간다.
   
   
   

1260번 dfs bfs 자바 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

class Main{    
    static int n,m;
    static int arr[][];
    static boolean[] visited;
    static int start;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        start = Integer.parseInt(temp[2]);
        arr = new int[n+1][n+1];

        for(int i=0; i<m; i++){
            String[] temp2 = br.readLine().split(" ");
            int a = Integer.parseInt(temp2[0]);
            int b = Integer.parseInt(temp2[1]);
            arr[a][b] = 1;
            arr[b][a] = 1;
        }

        visited = new boolean[n+1];
        dfs(start);
        bw.newLine();

        visited = new boolean[n+1];
        bfs(start);

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

    public static void dfs(int k) throws IOException {
        visited[k] = true;        
        bw.write(k + " ");

        for(int i=1; i<=n; i++){
            if(arr[k][i] == 1 && !visited[i])
                dfs(i);
        }
    }

    public static void bfs(int k) throws IOException{
        Queue<Integer> q = new LinkedList<>();

        visited[k] = true;
        bw.write(k + " ");
        q.offer(k);
        while(!q.isEmpty()){    
            int a = q.poll();

            for(int i=1; i<=n; i++){
                int b = arr[a][i];
                if(b != 0 && !visited[i]){
                    q.offer(i);
                    visited[i] = true;
                    bw.write(i + " ");
                }
            }
        }
    }
}