미로 찾기 (BFS)

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

문제 풀이

전형적인 BFS 2단계 최단거리 문제.

1. 1단계: S에서 BFS를 돌려 L까지의 최단 거리를 구함
2. 2단계: L에서 BFS를 돌려 E까지의 최단 거리를 구함
3. 두 거리를 더해서 반환. 둘 중 하나라도 도달 불가능하면 -1

 

 

작성한 코드

import java.util.*;

public class Solution {

    public int solution(String[] maps) {

        int n = maps.length;
        int m = maps[0].length();
        char[][] grid = new char[n][m];
        int[] start = null, lever = null, exit = null;

        // 탐사를 위한 2중 배열 맵 제작
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char c = maps[i].charAt(j);
                grid[i][j] = c;
                if (c == 'S') start = new int[]{i,j};
                else if (c == 'L') lever = new int[]{i,j};
                else if (c == 'E') exit = new int[]{i, j};
            }
        }

        // 시작점 ~ 레버 거리
        int distToLever = bfs(grid, start, lever, n, m);
        if (distToLever == -1) return -1;

        // 레버 ~ 종료점 거리
        int distToExit = bfs(grid, lever, exit, n, m);
        if (distToExit == -1) return -1;

        return distToLever + distToExit;
    }

    private static int bfs (char[][] grid, int[] start, int[] target, int n, int m) {

        // 거리 저장용 이중 배열 (모든 거리 -1로 초기화)
        int[][] dist = new int[n][m];
        for (int[] row : dist) Arrays.fill(row, -1);

        // 델타 배열
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        // 시작점 설정
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0], start[1]});
        dist[start[0]][start[1]] = 0;

        // BFS 시작
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];

            if (x == target[0] && y == target[1]) {
                return dist[x][y];
            }

            // 델타 배열로 근처 칸을 큐에 추가
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (grid[nx][ny] == 'X') continue;
                if (dist[nx][ny] != -1) continue;

                dist[nx][ny] = dist[x][y] + 1;
                queue.offer(new int[]{nx, ny});
            }
        }
        return dist[target[0]][target[1]];
    }
}

 

참고 : 

https://record47584.tistory.com/36

델타 배열을 이용해 2차원 배열 탐색하기

https://record47584.tistory.com/63

BFS(너비 우선 탐색)