[백준 / 실버2] 1260 DFS와 BFS (Java)

문제 보기

사용한 것

• DFS, BFS와 그래프를 나타내기 위한 인접행렬

풀이 방법

• 입력 값으로 인접행렬인 adj를 초기화한다.
• adj와 stack을 사용해 DFS, 결과를 dfsPath에 저장한다.
• adj와 q를 사용해 BFS, 결과를 bfsPath에 저장한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int v = Integer.parseInt(line[2]);

        boolean[][] adj = new boolean[n + 1][n + 1];

        for(int i = 0; i < m; i++) {
            line = br.readLine().split(" ");
            int v1 = Integer.parseInt(line[0]);
            int v2 = Integer.parseInt(line[1]);
            adj[v1][v2] = true;
            adj[v2][v1] = true;
        }

        StringBuilder dfsPath = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        boolean[] dfsVisited = new boolean[n + 1];
        stack.push(v);

        while(!stack.isEmpty()) {
            int cv = stack.pop();

            if(dfsVisited[cv]) {
                continue;
            }

            dfsVisited[cv] = true;
            dfsPath.append(cv).append(" ");

            for(int nv = n; nv >= 1; nv--) {
                if(!adj[cv][nv] || dfsVisited[nv]) {
                    continue;
                }

                stack.push(nv);
            }
        }

        StringBuilder bfsPath = new StringBuilder();
        Queue<Integer> q = new LinkedList<>();
        boolean[] bfsVisited = new boolean[n + 1];
        q.offer(v);
        bfsVisited[v] = true;

        while(!q.isEmpty()) {
            int cv = q.poll();
            bfsPath.append(cv).append(" ");

            for(int nv = 1; nv <= n; nv++) {
                if(!adj[cv][nv] || bfsVisited[nv]) {
                    continue;
                }

                q.offer(nv);
                bfsVisited[nv] = true;
            }
        }

        System.out.println(dfsPath);
        System.out.println(bfsPath);
    }
}