LV2 - 미로 탈출

 

---

 

문제

 

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

프로그래머스

 

 

풀이

전형적인 bfs 문제이다.

 

출발점에서 레버까지 도달한다음, 레버에서 다시 출구까지 도달하도록 

 

2번을 나눠서 bfs를 수행하면 된다.

 

탐색하면서 거리를 계속 체크하다가, 타겟칸(레버나 출구칸) 으로 이동하면 그만큼의 거리를 반환하도록 bfs를 구성하면 된다. 

 

참고로 나는 시작점을 0이 아닌 1로 줘서 시작했기 때문에 마지막에 반환할 때 -2를 빼줬다. (bfs를 두번 수행하기에)

 

 

코드

import java.util.*;

class Solution {

    public int h;
    public int w;
    public int solution(String [] maps) {

        // s부터 레버 까지 최소칸
        // 레버부터 e 까지 최소칸
        // 중간에 하나라도 끝에 도달하지 못한다면 -1 return
        // 도달한다면 그 칸에서 검색

        h = maps.length;
        w = maps[0].length();

        int sTol = 0;
        int lToe = 0;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if(maps[i].charAt(j) == 'S') {
                    sTol = bfs(i, j, new int[h][w], maps, 'L');
                }

                if(maps[i].charAt(j) == 'L') {
                    lToe = bfs(i, j, new int[h][w], maps, 'E');
                }
            }
        }

        return (sTol != -1 && lToe != -1) ? sTol+lToe-2 : -1;
    }

    public int bfs(int x, int y, int[][] visited, String[] maps, char target){
        int dx[] = {0, -1, 1, 0};
        int dy[] = {1, 0, 0, -1};
        Deque<Integer[]> deque = new ArrayDeque<>();
        deque.addLast(new Integer[]{x, y});
        visited[x][y] = 1;

        while (!deque.isEmpty()) {
            Integer[] integers = deque.removeFirst();

            x = integers[0];
            y = integers[1];

            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx >= 0 && nx < h && ny >= 0 && ny < w){
                    if(maps[nx].charAt(ny) != 'X' && visited[nx][ny] == 0){
                        deque.addLast(new Integer[]{nx, ny});
                        visited[nx][ny] = visited[x][y] + 1;
                        if(target == maps[nx].charAt(ny)) return visited[nx][ny];
                    }
                }
            }
        }
        return -1;
    }
}

 

후기