백준 1260(DFS와 BFS) JAVA <그래프 구현 방법>

문제

1260번: DFS와 BFS

노드의 갯수 n, 간선의 정보 m개, 시작 노드 v를 입력받아 DFS와 BFS 한 결과를 출려하면 되는 문제이다.

그동안 C++로 알고리즘을 풀다가 처음으로 JAVA로 구현하다 보니 헷갈리는 부분이 많아 정리한다.

C++ 에서는 2차원 벡터로 구현하면 된다.

 

1) 인접 행렬 구현

arr[a][b] = 1 (a에서 b로가는 간선이 있다.)

arr[a][b] = 0 (a에서 b로 가는 간선이 없다.)

for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = 1;
            arr[b][a] = 1;
}
static void dfs(int v){
        chk[v] =true;
        System.out.print(v+ " ");
        for(int i = 1; i<arr[v].length;i++){
            if(chk[i] == false && arr[v][i] ==1)
                dfs(i);
        }
}
static void bfs(int v){
        Queue<Integer>q = new LinkedList<>();
        q.add(v);
        chk[v] = true;
        while(!q.isEmpty()){
            int cur = q.peek();
            System.out.print(cur + " ");
            q.remove();
            for(int i = 1;i<arr[cur].length;i++){
                if(chk[i]== false && arr[cur][i] ==1){
                    q.add(i);
                    chk[i]=true;
                }
            }
        }
}

위와 같이 활용할 수 있다.

장점은 연결된 정점을 찾기 매우 쉽다는 것이다. (a와 b가 연결되있는지 알고싶으면 arr[a][b]를 보면 됨)

단점은 O(n^2)의 공간 복잡도를 가진다.

 

2) 인접 리스트

c++에서 사용한 방법과 매우 유사하다.

static ArrayList<Integer>[]list;
list = new ArrayList[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());
            list[a].add(b);
            list[b].add(a);
}

for(int i=0;i< list.length;i++)Collections.sort(list[i]); //문제 특성상 정렬을 함

static void dfs(int v){
        chk[v] =true;
        System.out.print(v+ " ");
        for(int a : list[v]){
            if(chk[a] ==false){
                dfs(a);
            }
        }
    }
static void bfs(int v){
        Queue<Integer>q = new LinkedList<>();
        q.add(v);
        chk[v] = true;
        while(!q.isEmpty()){
            int cur = q.peek();
            System.out.print(cur + " ");
            q.remove();
            for(int a : list[cur]){
                if(chk[a]== false){
                    q.add(a);
                    chk[a]=true;
                }
            }
        }
}

장점은 공간복잡도가 O(n) 이라는 것이다.

단점은 연결된 정점의 정보를 보려면 list를 순회해야 한다는 것이다.

---

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj1260_DFS와BFS {
    static ArrayList<Integer>[]list;
    static boolean []chk;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m= Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        list = new ArrayList[n+1];
        chk = new boolean[n+1];

        for(int i = 0;i<=n;i++)list[i] = new ArrayList<>();

        for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }

        for(int i=0;i< list.length;i++)Collections.sort(list[i]);

        dfs(v);
        Arrays.fill(chk, false);
        System.out.println();
        bfs(v);
    }
    static void dfs(int v){
        chk[v] =true;
        System.out.print(v+ " ");
        for(int a : list[v]){
            if(chk[a] ==false){
                dfs(a);
            }
        }
    }
    static void bfs(int v){
        Queue<Integer>q = new LinkedList<>();
        q.add(v);
        chk[v] = true;
        while(!q.isEmpty()){
            int cur = q.peek();
            System.out.print(cur + " ");
            q.remove();
            for(int a : list[cur]){
                if(chk[a]== false){
                    q.add(a);
                    chk[a]=true;
                }
            }
        }
    }
}