[백준] #1260 DFS와 BFS

기본적인 DFS, BFS 문제이다. 

오랜만에 알고리즘 문제를 풀기로 다짐해서 차근차근 연습해볼 생각이다.

 

내가 맨 처음 작성한 코드는 아래와 같다.

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

public class Main {
    static ArrayList<Integer>[] adjList;
    static boolean[] isVisited;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        adjList = new ArrayList[N + 1];

        for (int i = 0; i < N + 1; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            adjList[node1].add(node2);
            adjList[node2].add(node1);
        }

        for (ArrayList<Integer> n : adjList) {
            n.sort(Collections.reverseOrder());
        }

        isVisited = new boolean[N + 1];
        dfs(V);

        for (ArrayList<Integer> n : adjList) {
            Collections.sort(n);
        }

        isVisited = new boolean[N + 1];
        bfs(V);

        System.out.println(sb);
    }

    public static void dfs(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

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

            if (!isVisited[node]) {
                isVisited[node] = true;
                sb.append(node).append(" ");

                for (int n : adjList[node]) {
                    if (!isVisited[n]) {
                        stack.push(n);
                    }
                }
            }
        }

        sb.append("\n");
    }

    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        isVisited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            sb.append(node).append(" ");

            for (int n : adjList[node]) {
                if (!isVisited[n]) {
                    queue.add(n);
                    isVisited[n] = true;
                }
            }
        }
    }
}

 

코드를 좀 더 정리해보고자 GPT를 이용했고, 두 번 초기화하고 있던 isVisited 배열을 아래와 같이 지역변수화 할 수 있었다.

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

public class Main {
    static ArrayList<Integer>[] adjList;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        adjList = new ArrayList[N + 1];

        for (int i = 0; i < N + 1; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            adjList[node1].add(node2);
            adjList[node2].add(node1);
        }

        for (ArrayList<Integer> n : adjList) {
            n.sort(Collections.reverseOrder());
        }

        dfs(V, new boolean[N + 1]); // 지역변수 isVisited 전달

        for (ArrayList<Integer> n : adjList) {
            Collections.sort(n);
        }

        bfs(V, new boolean[N + 1]); // 지역변수 isVisited 전달

        System.out.println(sb);
    }

    public static void dfs(int start, boolean[] isVisited) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

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

            if (!isVisited[node]) {
                isVisited[node] = true;
                sb.append(node).append(" ");

                for (int n : adjList[node]) {
                    if (!isVisited[n]) {
                        stack.push(n);
                    }
                }
            }
        }

        sb.append("\n");
    }

    public static void bfs(int start, boolean[] isVisited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        isVisited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            sb.append(node).append(" ");

            for (int n : adjList[node]) {
                if (!isVisited[n]) {
                    queue.add(n);
                    isVisited[n] = true;
                }
            }
        }
    }
}

 

아래와 같이 함수에 인자로 new boolean[]을 직접 넘기면 함수 호출 시마다 배열이 새로 초기화된다.

dfs(V, new boolean[N + 1]); // 지역변수 isVisited 전달

public static void dfs(int start, boolean[] isVisited) { 
	...
}

 

함수 안에서 배열에 수정이 일어날 경우,

자바에서 배열은 참조 타입이기 때문에 내용 변경이 실제로 반영된다.