백준 1260번 Graph 탐색

Graph 탐색 방법(DFS,BFS)

Graph 특징

• 정점과 간선으로 이루어진 자료구조
• Graph는 간선이 양방향일때와 방향일때 2가지로 나뉜다
• 간선에 가중치도 있을 수 있음
• 모든 정점의 차수의 합 = 간선의 총개수 x2 이다.
  - 차수란 정점이 가진 간선의 수
• Graph를 코드로 표현하는 방법에는 인접행렬방식과 인접리스트 방식이 있다.
  - 인접행렬 : 2차원배열로 표현하며, 두 정점이 연결되어있으면 1, 아니면 0으로 나타낸다. 인접행렬의 단점은 정점이 서로 연결되어있던 안되어있던 모든 정보가 리스트에 들어가므로 메모리 낭비가 심하다.
  - 인접리스트 : 연결된 정점만 리스트에 표현
  
• A와 B를 잇는 간선의 존재 여부를 묻는 작업이 많을땐 인접행렬 유리
  A와 연결된 모든 정점을 확인하는 작업이 많을땐 인접리스트 유리
  하지만 인접행렬방식으로 했을때 메모리를 너무많이 쓰게되면 인접리스트로 구현해야함

DFS(깊이 우선 탐색) & BFS(넓이 우선 탐색)

# 양방향 그래프
# 인접행렬, 인접리스트 2가지 방식으로 모두 구현
public class Main {
    static StringBuilder sb = new StringBuilder();
    static Scanner scan = new Scanner(System.in);

    static int N, M, V;
    static int[][] adj;
    static ArrayList<Integer>[] adj2;
    static boolean[] visit;

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        V = scan.nextInt();
        adj = new int[N + 1][N + 1];
        adj2 = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            adj2[i] = new ArrayList<Integer>();
        }
        for (int i = 1; i <= M; i++) {
            int x = scan.nextInt(), y = scan.nextInt();
            adj[x][y] = 1;
            adj[y][x] = 1;

            adj2[x].add(y);
            adj2[y].add(x);
        }
        // 인접행렬은 정렬이 필요없지만, 인접리스트는 정렬을 해줘야함.
        // 인접행렬은 순회를 돌때 처음부터 순서대로 도니까 정렬이 필요없음. 반면 인접리스트는 입력이 들어온순서대로 리스트 구성되어있으므로
        // 정렬되지않은상태임.
        for (int i = 1; i <= N; i++) {
            Collections.sort(adj2[i]);
        }
    }

    // 인접행렬일때 DFS
    static void dfs(int x) {
        visit[x] = true;
        sb.append(x).append(" ");
        for (int y = 1; y <= N; y++) {
            if (adj[x][y] == 0)
                continue;
            if (visit[y])
                continue;
            dfs(y);
        }
    }

    // 인접리스트일때 DFS
    static void dfs2(int x) {
        visit[x] = true;
        sb.append(x).append(" ");
        for (int y : adj[x]) {
            if (visit[y])
                continue;
            dfs(y);
        }
    }

    // 인접행렬일때 BFS
    static void bfs(int x) {
        Queue<Integer> que = new LinkedList<>();

        que.add(x);
        visit[x] = true;

        while (!que.isEmpty()) {
            x = que.poll();
            sb.append(x).append(" ");
            for (int y = 1; y <= N; y++) {
                if (adj[x][y] == 0)
                    continue;
                if (visit[y])
                    continue;

                que.add(y);
                visit[y] = true;
            }
        }
    }

    // 인접리스트일때 BFS
    static void bfs2(int x) {
        Queue<Integer> que = new LinkedList<>();

        que.add(x);
        visit[x] = true;

        while (!que.isEmpty()) {
            x = que.poll();
            sb.append(x).append(" ");
            for (int y : adj[x]) {
                if (adj[x][y] == 0)
                    continue;
                if (visit[y])
                    continue;

                que.add(y);
                visit[y] = true;
            }
        }
    }

    static void pro() {
        visit = new boolean[N + 1];
        dfs(V);
        sb.append('\n');
        for (int i = 1; i <= N; i++)
            visit[i] = false;
        bfs(V);

        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}