프로그래머스 - 미로탈출 (JAVA)

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

프로그래머스

문제)

지도에서 시작(S) → 레버(L) → 출구(E)  순서로 가야한다.

 

접근 방식) BFS

1. O, X, S, L, E 문자 들어있는 char map[][] 배열 만듦

   만들면서 Start와 Lever 위치 파악해서 좌표 저장해둠 (startX, startY, leverX, leverY)

2. 시작지점(S) → 레버(L) 까지 갈 수 있는지 bfs 실행 

    return 값이 -1이면 갈 수 없다는 뜻이므로 -1 반환하고 끝냄

3. 레버(L) → 출구(E) 까지 갈 수 있는지 bfs 실행

   return 값이 -1이면 갈 수 없다는 뜻이므로 -1 반환하고 끝냄

4. 답 = 시작(S) → 레버(L) + 레버(L) → 출구(E)

 

import java.util.*;
class Solution {
    static char[][] map;
    static int[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    
    public int solution(String[] maps) {
        int startX = 0; int startY = 0;
        int leverX = 0; int leverY = 0;
        map = new char[maps.length][maps[0].length()];
        
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length(); j++) {
                map[i][j] = maps[i].charAt(j);
                
                if (map[i][j] == 'S') {
                    startX = i;
                    startY = j;
                }
                if (map[i][j] == 'L') {
                    leverX = i;
                    leverY = j;
                }
            }
        }
        
        // 시작(S) → 레버(L)
        int startToLever = bfs(startX, startY, 'L');
        if (startToLever == -1) return -1;
        
        // 레버(L) → 출구(E)
        int leverToExit = bfs(leverX, leverY, 'E');
        if (leverToExit == -1) return -1;
        
        return startToLever + leverToExit;
    }
    
    static int bfs(int i, int j, char search) {
        visited = new int[map.length][map[0].length];
        for (int n = 0; n < visited.length; n++) {
            for (int m = 0; m < visited[n].length; m++)
                visited[n][m] = -1;
        }
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        visited[i][j] = 0;
        
        while (!queue.isEmpty()) {
            int[] now = queue.poll();   
            for (int k = 0; k < 4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
              
                if (x < 0 || y < 0 || x >= map.length || y >= map[0].length) continue;
                if (map[x][y] != 'X' && visited[x][y] == -1) {
                    visited[x][y] = visited[now[0]][now[1]] + 1;
                    if (map[x][y] == search) 
                        return visited[x][y];
                    queue.add(new int[]{x, y});
                }
            }
        }
        return -1;
    }
}