[ 백준 ] 1260번 - DFS와 BFS

< 문제 정보 >

[ 문제 ]

  양방향으로 이어진 노드 그래프가 주어졌을 때, DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)으로 그래프를 탐색하여 방문된 점들을 출력하는 문제이다.

[ 예시 ]

• 입력

4 5 1
1 2
1 3
1 4
2 4
3 4

※ 4 : 정점의 개수, 5 : 간선의 개수, 1 : 시작 정점 번호

• 출력

1 2 4 3
1 2 3 4 

  ※ 첫 번째 줄은 BFS 수행 결과, 두 번째 줄은 DFS 수행 결과

[ 규칙 ]

• 정점의 개수 N ( 1 ≤ N ≤ 1,000 )
• 간선의 개수 M ( 1 ≤ N ≤ 10,000 )

[ 백준 ]

• DFS, BFS
• 링크

< 풀이 >

  인접 행렬 방법으로 입력을 받고, DFS는 재귀, BFS는 큐를 사용하였다. BFS와 DFS의 개념과 기본 알고리즘 숙지가 필수이다. 입력 방식만 주의한다면 쉽게 풀 수 있는 문제이다.

입력 행렬

	1	2	3	4
1		1	1	1
2	1			1
3	1			1
4	1	1		1

※ 1 : 간선 표시
Ex. (3, 1) = 1 : 3번과 1번이 연결되어 있다.

< 코드 >

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 BaekJoon1260 {
    static int node, line, point;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        node = Integer.parseInt(st.nextToken());
        line = Integer.parseInt(st.nextToken());
        point = Integer.parseInt(st.nextToken());
        boolean[] visited = new boolean[node+1];
        int[][] graph = new int[node+1][node+1];
        for(int i=0;i<line;i++) {
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a][b] = graph[b][a] = 1;
        }
        BaekJoon1260 baekJoon1260 = new BaekJoon1260();
        baekJoon1260.DFS(graph, point, visited);
        Arrays.fill(visited,false);
        System.out.println();
        baekJoon1260.BFS(graph, point, visited);
    }
    private void DFS(int[][] graph, int point, boolean[] visited) {
        visited[point] = true;
        System.out.print(point + " ");
        for(int i=0;i<node+1;i++) {
            if (!visited[i] && graph[point][i] == 1)
                DFS(graph,i,visited);
        }
    }
    private void BFS(int[][] graph, int point, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(point);
        visited[point] = true;
        while(!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");
            for (int i=1;i<graph[v].length;i++) {
                if (!visited[i] && graph[v][i] == 1) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

---

  최근 코딩 테스트를 여러 봤는데, 비슷한 알고리즘이 여러 번 나오는 것을 체감하여 알고리즘별 문제 풀이를 진행하고 있다. 공부를 그닥 잘하는 편도 아니고, 시작한지 얼마 안 되서 보고 할 때가 많지만, 다시 풀기 메모를 남겨 못 풀었던 문제들은 다시 풀 예정이다.