암시적 그래프

암시적 그래프란?

그래프는 보통 인접 행렬이나 인접 리스트와 같은 자료구조로 표현함

암시적 그래프는 이러한 방식 없이, 문제의 조건을 바탕으로 노드와 간선을 유추하며 탐색하는 방식
미로 탐색, 퍼즐, 최단 거리 문제 등에서 자주 등장..

1. 암시적 그래프의 개념

암시적 그래프는 노드와 간선을 명시적으로 저장하지 않고, 탐색 과정에서 동적으로 판단

• 값이 0이면 이동 가능 (길)
• 값이 1이면 이동 불가 (벽)
• 상, 하, 좌, 우로만 이동 가능

이런 미로는 처음에는 단순한 2차원 배열처럼 보이지만, 값이 0인 좌표를 노드, 상하좌우 이동 가능 조건을 간선으로 간주하면 그래프 구조로 해석할 수 있다.

2. 암시적 그래프에서의 노드와 간선

암시적 그래프에서는 별도의 노드 번호가 없습니다. 좌표 자체가 노드의 역할을 한다.

예를 들어, (1,2) 좌표는 다음 위치들과 연결될 수 있다.

• (0,2) (위쪽)
• (1,1) (왼쪽)
• (2,2) (아래쪽)

(1,3)이 벽(1)이라면 연결되지 않는다.

• 노드: 값이 0인 좌표 (r, c)
• 간선: 상하좌우로 이동할 수 있는 경로

3. 명시적 그래프 vs 암시적 그래프

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

Map<Integer, List<Integer>> graph = new HashMap<>() {{
    put(0, List.of(1, 2));
    put(1, List.of(0, 3, 4));
    put(2, List.of(0, 5, 6));
}};

 

for (int next : graph.get(cur)) {
    // next 노드 처리
}

 

 

4. 암시적 그래프에서 nextVertex 탐색

인접 리스트 없이도 다음 좌표를 다음과 같은 방향 벡터로 찾을 수 있다.

int[] dr = {-1, 1, 0, 0};  // 위, 아래
int[] dc = {0, 0, -1, 1};  // 왼쪽, 오른쪽

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

5. 다음 노드가 유효한지 판단하는 조건

1. 범위 안에 있는가?
   • 0 <= nr < N, 0 <= nc < M 확인
2. 이동 가능한가? (값이 0인가?)
   • grid[nr][nc] == 0

if (0 <= nr && nr < N && 0 <= nc && nc < M) {
    if (grid[nr][nc] == 0) {
        // 유효한 이동 가능 노드
    }
}