암시적 그래프

인접 행렬이나 인접 리스트를 사용하여 그래프를 저장하는 방식이 일반적이다.

`암시적 그래프 (Implicit Graph)`는 명시적인 저장 방식 없이, 문제의 조건을 통해 그래프의 구조를 유추하며 탐색하는 방식이다.

미로 탐색, 퍼즐 문제, 최단 거리 문제 등에서 자주 출제되며, 이를 효과적으로 해결하기 위해 반드시 이해해야 한다.

암시적 그래프 개념

암시적 그래프는 명시적으로 노드와 간선을 저장하지 않고, 탐색하면서 그래프 구조를 동적으로 유추

즉, 탐색 과정에서 이동 가능한 정점과 간선을 문제의 조건을 기반으로 판별함

예시)

아래와 같은 미로가 있다고 가정

• `1`: 이동 가능
• `0`: 이동 불가능
• 상하좌우로 이동

암시적 그래프 예시

겉보기에는 그래프로 보이지 않지만,
값이 1인 곳이 이동 가능(노드) 하다는 점과 상하좌우로 이동(간선)할 수 있다는 점을 고려하면 그래프로 해석 가능하다.

❓ 암시적 그래프에서의 노드
암시적 그래프에서 노드의 이름은 별도로 부여하지 않고, 해당 위치의 좌표를 사용함
∴ (x, y) 좌표 = 노드

 

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

명시적 그래프 (인접 리스트)

인접 리스트를 사용한 BFS에선 현재 노드의 다음 노드를 찾는 과정은 간단함.

for(int next: graph.get(current)){...}

`graph.get(current)`를 순회하면 미리 저장된 연결 정보를 활용해 다음 노드를 바로 찾을 수 있음

즉, 다음 노드를 미리 알고 있으므로 반복문을 통해 찾기만 하면 됨

암시적 그래프

암시적 그래프는 연결된 노드 정보를 저장하지 않음

∴ 탐색 중에 직접 다음 노드를 찾아야 함

for (int i = 0; i < 4; i++) { // 상하좌우 탐색
    int nx = x + dx[i];
    int ny = y + dy[i];
    
    // 배열 범위 체크
    if (0 <= nx && nx < rowLen && 0 <= ny && ny < colLen) {
        // 이동 가능한지 확인
        if (grid[nx][ny] == 1) { ...

암시적 그래프에서 다음 노드를 찾는 방식은 문제의 조건에 따라 동적으로 결정됨.