[프로그래머스] 미로 탈출(159993)

1. 문제 풀이 아이디어

• BFS를 활용하여 시작 지점부터 레버까지의 최소 거리와 레버부터 출구까지의 최소 거리를 구하여 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    boolean[][] map;
    final int dir[][] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int solution(String[] maps) {
        map = new boolean[maps.length][maps[0].length()];
        int[] s = null;
        int[] e = null;
        int[] l = null;
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length(); j++) {
                char c = maps[i].charAt(j);
                if (c == 'X') continue;
                map[i][j] = true;
                if (c == 'S') {
                    s = new int[]{i, j};
                } else if (c == 'E') {
                    e = new int[]{i, j};
                } else if (c == 'L') {
                    l = new int[]{i, j};
                }
            }
        }
        int sl = bfs(s, l);
        if (sl == -1) return -1;
        int le = bfs(l, e);
        if (le == -1) return -1;
        return sl + le;
    }

    public int bfs(int[] start, int[] end) {
        boolean[][] visited = new boolean[map.length][map[0].length];
        Queue<int[]> q = new ArrayDeque<>();
        q.add(start);
        visited[start[0]][start[1]] = true;
        int dist = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            dist++;
            for (int i = 0; i < size; i++) {
                int[] cur = q.poll();
                for (int j = 0; j < dir.length; j++) {
                    int nx = cur[0] + dir[j][0];
                    int ny = cur[1] + dir[j][1];
                    if (nx == end[0] && ny == end[1]) {
                        return dist;
                    }
                    if (nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length || visited[nx][ny] || !map[nx][ny])
                        continue;
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }

        }

        return -1;
    }
}

3. 정리

• BFS를 사용하여 시작 지점에서 레버까지의 최소 거리(sl)와 레버에서 출구까지의 최소 거리(le)를 각각 계산했다.

• 만약 두 거리 중 하나라도 -1이 반환되면 도달할 수 없으므로 -1을 반환했다.

• visited 배열을 통해 방문 여부를 관리하며, 큐를 활용해 인접한 좌표를 탐색했다.

• 큐에서 좌표를 꺼내 네 방향(dir)으로 이동 가능한지 확인하며, 목표 지점에 도달하면 누적 거리를 반환했다.

• 두 구간의 최소 거리를 더한 값이 최종 결과가 된다.