[Java] 그래프 탐색 알고리즘: DFS, BFS

인사말

 

 모두들 안녕하신가요.

 

 저는 어느덧 알고리즘을 건든 지 140일 지났답니다. 기쁜 소식이 있어 전해드리자면, 최근에 BFS 문제들을 풀며 골드 구간에 진입했어요. 목표는 골랜디 마스터고요. 이번에 문제를 풀며 스스로 아쉬웠던 부분들이 있어서 지금의 생각과 감정을 기록하려고 글을 적습니다.

---

BFS인데 그래프가 2개?

package bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Problem10026 {
    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};

    static Queue<int[]> queue1 = new LinkedList<>();
    static Queue<int[]> queue2 = new LinkedList<>();
    static boolean isProcess1 = true;
    static boolean isProcess2 = true;
    static int count1 = 0;
    static int count2 = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        char[][] board1 = new char[N][N];
        char[][] board2 = new char[N][N];
        int[][] visited1 = new int[N][N];
        int[][] visited2 = new int[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                char ch = line.charAt(j);
                board1[i][j] = ch;
                if (ch == 'R') {
                    board2[i][j] = 'G';
                } else {
                    board2[i][j] = ch;
                }
            }
        }

        while (isProcess1) {
            int[] point = point(visited1);
            int x = point[0];
            int y = point[1];
            queue1.add(new int[]{x, y});
            bfs1(board1, visited1);
        }

        while (isProcess2) {
            int[] point = point(visited2);
            int x = point[0];
            int y = point[1];
            queue2.add(new int[]{x, y});
            bfs2(board2, visited2);
        }

        System.out.println(count1 + " " + count2);
    }

    static int[] point(int[][] visited) {
        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[0].length; j++) {
                if (visited[i][j] == 0) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }

    static void bfs1(char[][] board1, int[][] visited1) {
        while (!queue1.isEmpty()) {
            int[] cur = queue1.poll();
            int x = cur[0];
            int y = cur[1];
            if (x < 0 && y < 0) {
                isProcess1 = false;
                return;
            }
            visited1[x][y] = 1;

            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (isValid(board1, visited1, newX, newY)) {
                    if (board1[x][y] == board1[newX][newY]) {
                        queue1.add(new int[]{newX, newY});
                        visited1[newX][newY] = 1;
                    }
                }
            }
        }
        count1++;
    }

    static void bfs2(char[][] board2, int[][] visited2) {
        while (!queue2.isEmpty()) {
            int[] cur = queue2.poll();
            int x = cur[0];
            int y = cur[1];
            if (x < 0 && y < 0) {
                isProcess2 = false;
                return;
            }
            visited2[x][y] = 1;

            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (isValid(board2, visited2, newX, newY)) {
                    if (board2[x][y] == board2[newX][newY]) {
                        queue2.add(new int[]{newX, newY});
                        visited2[newX][newY] = 1;
                    }
                }
            }
        }
        count2++;
    }

    static boolean isValid(char[][] board, int[][] visited, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length && visited[x][y] == 0;
    }
}

 BOJ 10026번 <적록색약> 문제입니다. 당시에도 그래프 포함 여러 코드들을 재활용할 수 있지 않을까 싶었지만, 일단 생각대로 되는지부터 확인하고 싶어서 무지성으로 작성했어요.

 

 다행히 정답 처리는 되었습니다만, 딱 봐도 문제가 많죠. 제가 보기에 중복된 코드들은 물론이고 메모리 낭비까지 있는 것 같습니다. 답은 맞혔으니 이제 리팩토링 해보기로 결심했습니다.

---

코드 분석

static final int[] dx = {0, 0, -1, 1};
static final int[] dy = {1, -1, 0, 0};

 일단 상하좌우로 인접해 있는지는 따져야 하니까 위 코드는 내버려 두어도 될 것 같습니다.

static Queue<int[]> queue1 = new LinkedList<>();
static Queue<int[]> queue2 = new LinkedList<>();
static boolean isProcess1 = true;
static boolean isProcess2 = true;
static int count1 = 0;
static int count2 = 0;

 탐색을 위한 큐, 반복문에 사용할 불린 타입, 구역의 수를 저장하는 카운트 변수는 굳이 2개씩일 필요가 없어 보이네요. 큐와 불린 타입은 당연한 거고, 카운트 변수도 StringBuilder 선언해서 값을 추가하는 식으로 진행하면 될 것 같습니다.

char[][] board1 = new char[N][N];
char[][] board2 = new char[N][N];

int[][] visited1 = new int[N][N];
int[][] visited2 = new int[N][N];

for (int i = 0; i < N; i++) {
    String line = br.readLine();
    for (int j = 0; j < N; j++) {
        char ch = line.charAt(j);
        board1[i][j] = ch;
        if (ch == 'R') {
            board2[i][j] = 'G';
        } else {
            board2[i][j] = ch;
        }
    }
}

 보드랑 방문 배열도 재사용하면 될 것 같아요. 일반 보드(본 입력)로 먼저 탐색하고 결과를 StringBuilder에 넣은 뒤, 적록색약에 맞게 보드를 수정하고 다시 메서드 돌리면 될 것 같습니다.

 

 그런데 여기에서 의문이 하나 생기네요. 어차피 자바에는 GC가 있어서 사용을 끝낸 녀석들은 사라진다고 들었던 것 같거든요. 두 그래프를 순차적으로 탐색하나, 한 그래프를 탐색하고 재활용해서 재탐색하나, 그게 그거 아닐까요?

while (isProcess1) {
    int[] point = point(visited1);
    int x = point[0];
    int y = point[1];
    queue1.add(new int[]{x, y});
    bfs1(board1, visited1);
}

while (isProcess2) {
    int[] point = point(visited2);
    int x = point[0];
    int y = point[1];
    queue2.add(new int[]{x, y});
    bfs2(board2, visited2);
}

 앞서 말했던 부분이니까 이 부분은 패스하겠습니다. 불린 타입을 초기화해서 쓰는 방식으로 중복 코드를 제거할 수 있을 듯해요.

System.out.println(count1 + " " + count2);

 StringBuilder 선언해서 값을 넣기로 했으니, 이 코드도 바뀌겠네요.

static int[] point(int[][] visited) {
    for (int i = 0; i < visited.length; i++) {
        for (int j = 0; j < visited[0].length; j++) {
            if (visited[i][j] == 0) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{-1, -1};
}

 탐색 시작점을 찾는 메서드입니다. 방문 배열을 순차적으로 돌다가 탐색하지 않은 곳(0)이 발견되면 해당 좌표를 뱉는 메서드고요. 전부 방문했다면 {-1, -1}을 뱉습니다.

 

 그래프 입력도 그렇고, 시간복잡도 측면에서 아쉽긴 한데 어쩔 수 없는 부분 같아서 넘길게요.

static void bfs1(char[][] board1, int[][] visited1) {
    while (!queue1.isEmpty()) {
        int[] cur = queue1.poll();
        int x = cur[0];
        int y = cur[1];
        if (x < 0 && y < 0) {
            isProcess1 = false;
            return;
        }
        visited1[x][y] = 1;

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            if (isValid(board1, visited1, newX, newY)) {
                if (board1[x][y] == board1[newX][newY]) {
                    queue1.add(new int[]{newX, newY});
                    visited1[newX][newY] = 1;
                }
            }
        }
    }
    count1++;
}

static void bfs2(char[][] board2, int[][] visited2) {
    while (!queue2.isEmpty()) {
        int[] cur = queue2.poll();
        int x = cur[0];
        int y = cur[1];
        if (x < 0 && y < 0) {
            isProcess2 = false;
            return;
        }
        visited2[x][y] = 1;

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            if (isValid(board2, visited2, newX, newY)) {
                if (board2[x][y] == board2[newX][newY]) {
                    queue2.add(new int[]{newX, newY});
                    visited2[newX][newY] = 1;
                }
            }
        }
    }
    count2++;
}

 탐색 시작점 메서드에서 마지막에 {-1, -1}을 뱉기 때문에 좌표가 음수인 경우 리턴하도록 처리했습니다. 마찬가지로 한 메서드로 정리해야 해요.

 

 근데 이거 짜면서 x랑 y 위치를 바꿔야 논리적으로 맞나 싶은 생각이 들었는데, 본 문제에서 크게 중요한 내용은 아닌 것 같아서 편의상 안 따지기로 했습니다.

static boolean isValid(char[][] board, int[][] visited, int x, int y) {
    return x >= 0 && x < board.length && y >= 0 && y < board[0].length && visited[x][y] == 0;
}

 탐색할 좌표가 유효한지 따지는 메서드입니다. 범위를 벗어난다거나 이미 탐색한 곳이라면 false를 반환하겠죠. 수정할 내용은 없어 보입니다.

---

수정된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Problem10026 {
    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};
    static Queue<int[]> queue = new LinkedList<>();
    static boolean isProcess = true;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // 본 배열 생성
        char[][] board = new char[N][N];
        int[][] visited = new int[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                board[i][j] = line.charAt(j);
            }
        }
        br.close();

        // 본 배열 탐색
        while (isProcess) {
            int[] point = point(visited);
            int x = point[0];
            int y = point[1];
            queue.add(new int[]{x, y});
            bfs(board, visited);
        }

        // 본 배열 탐색 결과 추가
        StringBuilder sb = new StringBuilder();
        sb.append(count);

        // 초기화
        isProcess = true;
        count = 0;
        visited = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'R') {
                    board[i][j] = 'G';
                }
            }
        }

        // 적록색약 배열 탐색
        while (isProcess) {
            int[] point = point(visited);
            int x = point[0];
            int y = point[1];
            queue.add(new int[]{x, y});
            bfs(board, visited);
        }

        // 적록색약 배열 탐색 결과 추가
        sb.append(" ").append(count);

        // 결과 출력
        System.out.print(sb);
    }

    static int[] point(int[][] visited) {
        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[0].length; j++) {
                if (visited[i][j] == 0) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }

    static void bfs(char[][] board, int[][] visited) {
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            if (x < 0 && y < 0) {
                isProcess = false;
                return;
            }
            visited[x][y] = 1;

            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (isValid(board, visited, newX, newY)) {
                    if (board[x][y] == board[newX][newY]) {
                        queue.add(new int[]{newX, newY});
                        visited[newX][newY] = 1;
                    }
                }
            }
        }
        count++;
    }

    static boolean isValid(char[][] board, int[][] visited, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length && visited[x][y] == 0;
    }
}

 배열 탐색 블록도 재사용하기 때문에 따로 메서드로 뺄까 했지만, 알고리즘을 푸는데 굳이 메서드로 빼야 할 것 같지는 않아서 이대로 진행했습니다. 겸사겸사 버퍼도 닫았어요.

---

성능 측정 결과

 중복 코드 제거 위주의 리팩토링이어서 그런지 코드 길이만 대폭 줄고 성능은 그대로에 가깝네요. 그래프를 두 개 선언해서 쓰나, 그래프를 초기화해서 쓰나 큰 차이는 없는 것 같습니다.

 

 만족스러운 결과가 안 나왔으니 다시 수정해 봅시다.

---

수정된 코드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Problem10026 {
    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        char[][] board = new char[N][N];
        int[][] visited = new int[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                board[i][j] = line.charAt(j);
            }
        }
        br.close();

        int count1 = bfs(board, visited);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'R') {
                    board[i][j] = 'G';
                }
            }
        }

        visited = new int[N][N];
        int count2 = bfs(board, visited);

        System.out.print(count1 + " " + count2);
    }

    static int bfs(char[][] board, int[][] visited) {
        Queue<int[]> queue = new LinkedList<>();
        int count = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (visited[i][j] == 0) {
                    visited[i][j] = 1;
                    queue.add(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        int x = cur[0];
                        int y = cur[1];

                        for (int d = 0; d < 4; d++) {
                            int newX = x + dx[d];
                            int newY = y + dy[d];
                            if (isValid(board, visited, newX, newY) && board[x][y] == board[newX][newY]) {
                                queue.add(new int[]{newX, newY});
                                visited[newX][newY] = 1;
                            }
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }

    static boolean isValid(char[][] board, int[][] visited, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length && visited[x][y] == 0;
    }
}

 point 메서드를 반복 실행하며 visited 배열을 여러 차례 순회하던 문제를 개선했습니다. 생각해 보니 한 번만 순회하면 되더라고요. 전역변수로 사용하지 않아도 될 것 같아 보이는 녀석들도 스코프를 좁혀줬습니다.

 

---

성능 측정 결과 2

 실행 시간이 꽤나 줄어들었지만 bfs 메서드 내에서 큐를 반복적으로 생성하며 직전 코드보다 메모리를 더 차지하게 된 것 같습니다. 큐를 다시 전역변수로 사용하는 편이 좋겠어요.

---

수정된 코드 3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Problem10026 {
    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};
    static Queue<int[]> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        char[][] board = new char[N][N];
        int[][] visited = new int[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                board[i][j] = line.charAt(j);
            }
        }
        br.close();

        int count1 = bfs(board, visited);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'R') {
                    board[i][j] = 'G';
                }
            }
        }

        visited = new int[N][N];
        int count2 = bfs(board, visited);

        System.out.print(count1 + " " + count2);
    }

    static int bfs(char[][] board, int[][] visited) {
        queue.clear();
        int count = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (visited[i][j] == 0) {
                    visited[i][j] = 1;
                    queue.add(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        int x = cur[0];
                        int y = cur[1];

                        for (int d = 0; d < 4; d++) {
                            int newX = x + dx[d];
                            int newY = y + dy[d];
                            if (isValid(board, visited, newX, newY) && board[x][y] == board[newX][newY]) {
                                queue.add(new int[]{newX, newY});
                                visited[newX][newY] = 1;
                            }
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }

    static boolean isValid(char[][] board, int[][] visited, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length && visited[x][y] == 0;
    }
}

---

성능 측정 결과 3

 추론한 대로 큐를 전역변수로 사용하였음에도 메모리 측면에서 개미 오줌만큼 개선되었습니다. 더는 모르겠으니 일단 여기까지 적을게요.