암시적 그래프에서 도착점 찾기 (BFS & DFS 활용)

암시적 그래프에서 도착점 찾기 (BFS & DFS 활용)

1. BFS를 활용한 도착점 탐색

BFS는 가까운 위치부터 차례대로 탐색

따라서 큐에서 꺼낸 현재 위치가 도착점인지 확인하고, 맞다면 즉시 탐색을 종료할 수 있다.

• 현재 위치: (r, c)
• 목표 위치: (endR, endC)

구현 흐름

1. 현재 위치가 도착점인지 확인
2. if (r == endR && c == endC) { return true; }
3. 모든 위치를 탐색했는데도 도달하지 못하면 실패 처리
4. return false;

예제 코드

import java.util.*;

public class BFSSearch {
    public static void main(String[] args) {
        int[][] grid = {
            {1, 1, 0, 1, 1},
            {0, 1, 1, 0, 1},
            {1, 1, 0, 1, 1},
            {1, 0, 1, 1, 0},
            {1, 1, 1, 0, 1}
        };

        int[] start = {0, 0};
        int[] end = {4, 4};

        boolean result = bfs(grid, start, end);
        if (result) {
            System.out.println("도착점에 도달했습니다.");
        } else {
            System.out.println("도착할 수 없습니다.");
        }
    }

    public static boolean bfs(int[][] grid, int[] start, int[] end) {
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        int rowLen = grid.length;
        int colLen = grid[0].length;
        boolean[][] visited = new boolean[rowLen][colLen];

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start[0], start[1]});
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int r = current[0], c = current[1];

            if (r == end[0] && c == end[1]) {
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < rowLen && nc >= 0 && nc < colLen && grid[nr][nc] == 1 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    queue.add(new int[]{nr, nc});
                }
            }
        }

        return false;
    }
}

 

2. DFS를 활용한 도착점 탐색

DFS도 도착점 탐색이 가능하지만, 재귀 호출의 흐름 관리가 중요하다.

DFS는 한 경로를 깊게 따라가며 탐색하기 때문에, 도착점을 발견했을 때 그 사실을 모든 상위 호출에 전달해야 한다.

방식 1: 반환값을 이용한 종료 신호 전달

• 도착 지점 도달 시 true 반환
• 하위 DFS 호출이 true를 반환하면 상위 호출도 그대로 반환
• 끝까지 탐색해도 도달하지 못하면 false 반환

public class DFSSearch {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    static int[][] grid = {
        {1, 1, 0, 1, 1},
        {0, 1, 1, 0, 1},
        {1, 1, 0, 1, 1},
        {1, 0, 1, 1, 0},
        {1, 1, 1, 0, 1}
    };

    static boolean[][] visited = new boolean[grid.length][grid[0].length];
    static int endR = 2, endC = 2;

    public static void main(String[] args) {
        if (dfs(0, 0)) {
            System.out.println("도착점에 도달했습니다.");
        } else {
            System.out.println("도착할 수 없습니다.");
        }
    }

    public static boolean dfs(int r, int c) {
        visited[r][c] = true;

        if (r == endR && c == endC) {
            return true;
        }

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == 1 && !visited[nr][nc]) {
                if (dfs(nr, nc)) {
                    return true;
                }
            }
        }

        return false;
    }
}

 

방식 2: 전역 변수로 플래그 관리

전역 변수 found를 선언하고, 도착점을 찾았을 때 해당 값을 true로 바꾸면, 모든 탐색을 중단할 수 있다.

public class DFSSearch {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    static int[][] grid = {
        {1, 1, 0, 1, 1},
        {0, 1, 1, 0, 1},
        {1, 1, 0, 1, 1},
        {1, 0, 1, 1, 0},
        {1, 1, 1, 0, 1}
    };

    static boolean[][] visited = new boolean[grid.length][grid[0].length];
    static int endR = 2, endC = 2;
    static boolean found = false;

    public static void main(String[] args) {
        dfs(0, 0);
        if (found) {
            System.out.println("도착점에 도달했습니다.");
        } else {
            System.out.println("도착할 수 없습니다.");
        }
    }

    public static void dfs(int r, int c) {
        if (found) return;

        visited[r][c] = true;

        if (r == endR && c == endC) {
            found = true;
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == 1 && !visited[nr][nc]) {
                dfs(nr, nc);
            }
        }
    }
}