[JAVA 문제 풀이] 373. 미로 탈출

내가 작성한 코드

import java.util.*;

class Solution {
    static int n; // 행의 개수
    static int m; // 열의 개수

    public int solution(String[] maps) {
        n = maps.length; // 행의 개수 초기화
        m = maps[0].length(); // 열의 개수 초기화

        // 시작, 레버 위치 저장
        int sx = 0;
        int sy = 0;
        int lx = 0;
        int ly = 0;

        // 맵에서 S와 L의 위치 찾기
        // S: 시작 위치, L: 레버 위치
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char ch = maps[i].charAt(j);
                if (ch == 'S') {
                    sx = i;
                    sy = j;
                } else if (ch == 'L') {
                    lx = i;
                    ly = j;
                }
            }
        }

        // S → L까지의 최단 거리와 L → E까지의 최단 거리 구하기
        int timeToLever = bfs(maps, sx, sy, 'L'); // S → L
        int timeToExit = bfs(maps, lx, ly, 'E'); // L → E

        // 둘 중 하나라도 도달할 수 없는 경우
        if (timeToLever == -1 || timeToExit == -1)
            return -1;
        return timeToLever + timeToExit;
    }

    // BFS로 특정 목적지까지 최단 거리 구하기
    public int bfs(String[] maps, int x, int y, char target) {
        // 상하좌우 이동을 위한 배열
        int[] dx = { -1, 1, 0, 0 };
        int[] dy = { 0, 0, -1, 1 };
        boolean[][] visited = new boolean[n][m]; // 방문 여부 체크
        Queue<int[]> q = new LinkedList<>(); // 큐 초기화
        q.add(new int[] { x, y, 0 }); // 큐에 시작 위치와 걸린시간 추가
        visited[x][y] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll(); // 현재 위치 꺼내기
            int cx = cur[0]; // 현재 x 좌표
            int cy = cur[1]; // 현재 y 좌표
            int time = cur[2]; // 현재까지 걸린 시간

            // 목적지에 도달한 경우
            if (maps[cx].charAt(cy) == target)
                return time;

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i]; // 다음 x 좌표
                int ny = cy + dy[i]; // 다음 y 좌표

                // 맵의 범위를 벗어난 경우
                if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;

                // 이미 방문한 경우
                if (visited[nx][ny])
                    continue;

                // 벽인 경우
                if (maps[nx].charAt(ny) == 'X')
                    continue;

                // 다음 좌표 방문 처리
                visited[nx][ny] = true;
                q.add(new int[] { nx, ny, time + 1 }); // 큐에 다음 위치와 걸린 시간 추가
            }
        }

        return -1; // 목적지에 도달할 수 없음
    }
}

다른 사람의 코드

import java.util.*;

class Solution {
    // 레버~시작점 거리와 레버~출구 거리의 합
    public int solution(String[] maps) {
        int R = maps.length; // 행
        int C = maps[0].length(); // 열
        int[][] time = new int[R][C]; // 시간 배열
        Queue<Integer> q = new ArrayDeque<>();

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                // 레버 위치 큐에 저장
                // 나머지는 시간 배열을 무한대로 초기화
                if (maps[r].charAt(c) == 'L') {
                    q.add(r);
                    q.add(c);
                } else {
                    time[r][c] = Integer.MAX_VALUE;
                }
            }
        }

        int toStart = -1;
        int toEnd = -1;

        int[][] dir = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; // 상하좌우 이동

        while (toStart == -1 || toEnd == -1) {
            if (q.size() == 0)
                return -1;

            int r = q.poll(); // 레버 행
            int c = q.poll(); // 레버 열
            int t = time[r][c] + 1; // 현재 시간 + 1

            for (int i = 0; i < 4; i++) {
                // 다음 위치 계산
                int nextR = r + dir[i][0];
                int nextC = c + dir[i][1];

                // 범위 내에 있는지 확인
                if (nextR >= 0 && nextR < R && nextC >= 0 && nextC < C) { 
                    // 벽이 아니고, 아직 방문하지 않은 위치라면
                    if (maps[nextR].charAt(nextC) != 'X' && time[nextR][nextC] > t) {
                        time[nextR][nextC] = t; // 시간 업데이트
                        // 큐에 다음 위치 추가
                        q.add(nextR);
                        q.add(nextC);

                        // 레버 -> 시작점 거리
                        if (maps[nextR].charAt(nextC) == 'S' && toStart == -1) {
                            toStart = t;
                        }

                        // 레버 -> 출구 거리
                        if (maps[nextR].charAt(nextC) == 'E' && toEnd == -1) {
                            toEnd = t;
                        }
                    }
                }
            }
        }

        return toStart + toEnd;
    }
}