[JAVA] 백준 1260번 - DFS와 BFS

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

1260번: DFS와 BFS

---

풀이)

나 DFS랑 BFS 못해서 이거 푼건데 진짜 못푼다....

 

dfs와 bfs는 인접 행렬, 인접 리스트 둘 다 이용해서 풀 수 있다

인접 행렬은 배열로, 인접 리스트는 연결 리스트(자바에선 ArrayList)로 푼다

(인접 행렬 : arr[x][y] = arr[y][x] = 1 )

 

인접 행렬이 구현하긴 편하긴 한데 인접 행렬은 사이즈가 커지면 사용 못함

따라서 인접 리스트(ArrayList)를 사용해서 구현하였다

 

dfs는 스택이나 재귀로, bfs는 큐로 푼다

dfs 의 경우 정석은 스택 사용이긴 한데 재귀가 사실상 스택이나 마찬가지고 코드도 간단하니까 재귀로 풀었다

bfs는 큐로 풀었다

dfs는 깊이 우선 탐색이니까 스택에 하나를 넣고 갈 수 있는 끝까지 간다음 하나씩 뺴면서 돈다

bfs는 너비 우선 탐색이니까 지금 갈 수 있는 노드를 모두 큐에 넣고 하나씩 빼면서 이걸 반복한다

 

다시 알고리즘 공부하면서 풀었다...

난 이거 언제쯤 능숙하게 풀까ㅠ

 

 

 

 

자바 코드)

import java.util.*;


public class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static int n;
    static int m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int v = sc.nextInt();

        visited = new boolean[n+1];
        for(int i=0;i<=n;i++) {
            graph.add(new ArrayList<>());
        }

        for(int i=1;i<=m;i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            graph.get(x).add(y);
            graph.get(y).add(x);
        }

        for(int i=1;i<=n;i++) {
            Collections.sort(graph.get(i));
        }

        dfs(v);
        System.out.println();
        visited = new boolean[1001]; //방문상태 초기화
        bfs(v);
    }

    public static void dfs(int x) { //stack
        visited[x] = true;
        System.out.print(x+" ");
        for(int num : graph.get(x)) {
            if(!visited[num]) {
                dfs(num);
            }
        }
    }

    public static void bfs(int x) { //queue
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        visited[x] = true;

        while(!queue.isEmpty()) {
            int value = queue.poll();
            System.out.print(value+ " ");

            for(int num : graph.get(value)) {
                if(!visited[num]) {
                    visited[num] = true;
                    queue.offer(num);
                }
            }
        }

    }


}

여기서 막판에 헤맸던건 갈 수 있는 노드가 여러개면 작은 노드 먼저 방문하라는 조건을 못본 것이었다

그래서 graph 입력 받고 정렬한 다음 dfs랑 bfs를 호출하여 사용하였다

 

 

 

결론 : 아무래도 이 알고리즘 문제들을 더 많이 풀어봐야겠다 진짜로.