[백준 1260/JAVA] DFS와 BFS

문제

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

1260번: DFS와 BFS

단순하게 입력받은 그래프를 dfs, bfs로 탐색한 결과를 출력하는 프로그램이다.

풀이

• dfs는 재귀로, bfs는 Queue 인터페이스를 LinkedList로 구현해 사용했다.
• 인접 행렬 : 그래프 각 정점 사이의 간선을 배열로 표현한다. 
  • 참고) 인접 행렬을 사용하는 경우, 간선 존재 여부를 상수시간 O(1) 안에 확인할 수 있으나, 정점이 많은 경우 메모리가 낭비된다.

*인접 행렬 사용 방법

 

만약 4개의 정점(1, 2, 3, 4)의 인접 행렬이라면 (1,1) ~ (4,4) 에 간선 정보를 입력해야 하므로

인접 행렬 크기를 edge[5][5]로 생성한다.

 

입력받은 값 :

1 2

1 3

1 4

2 4

3 4

 

1, 2가 간선으로 이어져있으므로 edge[1][2] = edge[2][1] = 1 

1, 3이 간선으로 이어져있으므로 edge[1][3] = edge[3][1] = 1 

...

 

문제에서 주어진 그래프는 무방향 그래프이므로 간선이 양방향으로 작용하기 때문에 (a,b) (b,a) 모두 간선 표시

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

코드

import java.util.*;
import java.util.Queue;
import java.io.*;

public class Main {
    //DFS - recursion/Stack
    //BFS - LinkedList/Queue

    //방문 노드 기록할 boolean 배열 'check'
    //간선을 표현할 int 배열 'edge'
    
    static StringBuilder sb = new StringBuilder();
    static Queue<Integer> q = new LinkedList<>();
    static boolean[] check;
    static int[][] edge;
    static int N, M, V;


    static void dfs(int V) { //recursion
        //node를 방문
        check[V] = true;
        sb.append(V+" ");

        //V와 인접 && 아직 방문하지 않은 node를 방문
        for(int i=1; i<=N; i++) { 
            if(edge[V][i]==1 && !check[i]) {
                dfs(i);
            }
        }
    }

    static void bfs(int V) { //Queue Interface
        //시작 node 큐에 넣기
        q.offer(V);
        check[V] = true;
        sb.append(V+" ");

        //V와 인접 && 아직 방문하지 않은 node를 방문
        while(!q.isEmpty()) {
            V = q.poll();

            for(int i=1; i<=N; i++) {
                if(edge[V][i]==1 && !check[i]) {
                    q.offer(i);
                    check[i] = true;
                    sb.append(i+" ");
                }
            }            
        }
    }


    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;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        check = new boolean[N+1]; //인덱스가 0부터 시작하므로 +1
        edge = new int[N+1][N+1];

        for(int i=0; i<M; i++) { //간선 수만큼 반복
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            edge[a][b] = edge[b][a] = 1;
        }

        dfs(V);

        sb.append("\n");
        check = new boolean[N+1];

        bfs(V);

        bw.write(sb + " ");
        bw.close();
    }
}

Note

• java.util.* 를 임포트했는데도 계속 큐 선언 코드에 에러가 떠서 java.util.Queue를 임포트했다. 큐는 java.util 패키지에 소속되어있는데 왜 에러가 뜬 걸까..
• sb, q, check, edge, N, M, V는 클래스 내의 dfs, bfs, main 함수 모두 써야 하므로 지역 변수가 아닌 클래스 변수로 선언
• 클래스 변수는 클래스가 메모리에 올라갈 때 생성되며, 인스턴스에 static을 붙여줘야 함
• 주의 : dfs, bfs 함수에서 인접한 노드를 찾는 for문의 조건을 i=1; i<=N 으로 설정해야 한다. i가 노드 번호로 쓰이므로 노드 번호 1부터 N까지를 나타내기 때문. i=0; i<N으로 쓰면 마지막 노드는 검사하지 못한다.