거리 측정과 최단거리 문제

1. 거리 측정의 핵심 원리

다음 노드의 거리 = 현재 노드의 거리 + 1, 즉 거리 값을 퍼뜨리는 bfs가 유리

2. BFS로 거리 측정하기

BFS의 특징

• 너비 우선 탐색: 가까운 곳부터 먼저 방문
• 한 번 방문한 노드에는 항상 최단거리로 도달

방법 1. distance 배열만 사용

int[][] distance = new int[rowLen][colLen];
for (int[] row : distance) Arrays.fill(row, -1); // -1: 미방문

Queue<int[]> q = new LinkedList<>();
q.add(new int[]{startR, startC});
distance[startR][startC] = 0;

while (!q.isEmpty()) {
    int[] curr = q.poll();
    for (int i = 0; i < 4; i++) {
        int nr = curr[0] + dr[i];
        int nc = curr[1] + dc[i];
        if (valid(nr, nc) && grid[nr][nc] == 1 && distance[nr][nc] == -1) {
            distance[nr][nc] = distance[curr[0]][curr[1]] + 1;
            q.add(new int[]{nr, nc});
        }
    }
}

방법 2. 큐에 거리까지 저장

q.add(new int[]{r, c, 0}); // 거리까지 포함
while (!q.isEmpty()) {
    int[] cur = q.poll();
    for (int i = 0; i < 4; i++) {
        int nr = cur[0] + dr[i], nc = cur[1] + dc[i];
        if (valid(nr, nc) && !visited[nr][nc]) {
            visited[nr][nc] = true;
            q.add(new int[]{nr, nc, cur[2] + 1});
        }
    }
}

 

3. DFS로 거리 측정하기

처음 찾은 경로가 최단거리라고 보장할 수 없으나, 조건에 따라 거리 측정이 가능

트리(사이클 없음)

void dfs(int r, int c, int dist) {
    distance[r][c] = dist;
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (valid(nr, nc) && distance[nr][nc] == -1) {
            dfs(nr, nc, dist + 1);
        }
    }
}

일반 그래프(사이클 있음)

이미 방문한 노드라도 더 짧은 거리로 도달했다면 갱신

void dfs(int r, int c, int dist) {
    if (dist >= distance[r][c]) return;
    distance[r][c] = dist;

    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (valid(nr, nc) && grid[nr][nc] == 1) {
            dfs(nr, nc, dist + 1);
        }
    }
}

 

4. 최단거리 문제와 BFS

최단거리 문제는 “시작점 → 도착점까지 가장 짧은 경로”를 묻는 대표 문제

bfs에서 처음 도달한 순간은 곧 최단거리 도달 순간

구현 예시: 도착점까지 최단 거리

public static int shortestPath(int[][] grid, int[] start, int[] end) {
    int[][] distance = new int[rowLen][colLen];
    for (int[] row : distance) Arrays.fill(row, -1);

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

    while (!q.isEmpty()) {
        int[] curr = q.poll();
        int r = curr[0], c = curr[1];
        if (r == end[0] && c == end[1]) return distance[r][c];

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (valid(nr, nc) && grid[nr][nc] == 1 && distance[nr][nc] == -1) {
                distance[nr][nc] = distance[r][c] + 1;
                q.add(new int[]{nr, nc});
            }
        }
    }

    return -1; // 도달 불가
}