암시적 그래프에서의 BFS, DFS

1. 암시적 그래프 vs 인접 리스트 그래프

명시적 그래프: 인접 리스트 방식

명시적 그래프에서는 노드 간의 연결 정보를 미리 저장해두고 탐색에 활용

대표적인 방식이 인접 리스트

for (int nextVertex : graph.get(curVertex)) {
    // 현재 노드(curVertex)에서 연결된 노드(nextVertex)로 이동
}

위 코드처럼 graph.get(curVertex)를 순회하면, 연결된 노드들을 바로 얻을 수 있어 간단하게 탐색이 가능,
즉, 미리 구성된 연결 관계에 따라 nextVertex를 직접 조회하는 방식

암시적 그래프: 동적으로 연결 관계 판단

암시적 그래프에서는 연결 정보를 저장하지 않고, 탐색 중에 직접 판단하여 연결 여부를 결정

for (int i = 0; i < 4; i++) {
    int nr = r + dr[i];
    int nc = c + dc[i];
    
    if (0 <= nr && nr < rowLen && 0 <= nc && nc < colLen) {
        if (grid[nr][nc] == 1) {
            // 이동 가능
        }
    }
}

 

방향 벡터

▸ 상하좌우 (4방향)

int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};

▸ 상하좌우 + 대각선 (8방향)

int[] dr = {-1, 1, 0, 0, -1, -1, 1, 1};
int[] dc = {0, 0, -1, 1, -1, 1, -1, 1};

▸ 상하좌우 2칸

int[] dr = {-2, 2, 0, 0};
int[] dc = {0, 0, -2, 2};

▸ 1칸 + 2칸 혼합

int[] dr = {-1, 1, 0, 0, -2, 2, 0, 0};
int[] dc = {0, 0, -1, 1, 0, 0, -2, 2};

 

 

+cur+1, 형식으로 동적으로 이동도 가능,

이동 조건

• 이동 가능한 곳이 1인 경우:

if (grid[nr][nc] == 1)

• 이동 가능한 곳이 0인 경우:

if (grid[nr][nc] == 0)

 

2. 암시적 그래프 BFS 구현

public class ImplicitGraphBFS {
    static boolean[][] visited;
    static int[][] grid;
    static int[] dr = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] dc = {1, 1, 0, -1, -1, -1, 0, 1};
    static int rowLength;
    static int colLength;

    public static boolean isValid(int r, int c) {
        return 0 <= r && r < rowLength && 0 <= c && c < colLength;
    }

    public static void main(String[] args) {
        grid = new int[][] { /* your grid here */ };
        rowLength = grid.length;
        colLength = grid[0].length;
        visited = new boolean[rowLength][colLength];
        bfs(0, 0);  // 시작 좌표
    }

    public static void bfs(int r, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curRow = cur[0];
            int curCol = cur[1];

            for (int i = 0; i < 8; i++) {
                int nextRow = curRow + dr[i];
                int nextCol = curCol + dc[i];
                if (isValid(nextRow, nextCol) && !visited[nextRow][nextCol]) {
                    queue.offer(new int[]{nextRow, nextCol});
                    visited[nextRow][nextCol] = true;
                }
            }
        }
    }
}

 

3. 암시적 그래프 DFS 구현

public class ImplicitGraphDFS {
    static boolean[][] visited;
    static int[][] grid;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static int rowLength;
    static int colLength;

    public static boolean isValid(int r, int c) {
        return 0 <= r && r < rowLength && 0 <= c && c < colLength;
    }

    public static void main(String[] args) {
        grid = new int[][] { /* your grid here */ };
        rowLength = grid.length;
        colLength = grid[0].length;
        visited = new boolean[rowLength][colLength];
        dfs(0, 0);  // 시작 좌표
    }

    public static void dfs(int r, int c) {
        visited[r][c] = true;
        for (int i = 0; i < 4; i++) {
            int nextRow = r + dr[i];
            int nextCol = c + dc[i];
            if (isValid(nextRow, nextCol) && !visited[nextRow][nextCol]) {
                dfs(nextRow, nextCol);
            }
        }
    }
}