[알고리즘] 프로그래머스 - JAVA 미로탈출 (bfs)

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

프로그래머스

package Programmers;

import java.util.LinkedList;
import java.util.Queue;

/*
  S : 시작지점
  E : 출구
  L : 레버
  O : 통로
  X : 벽
 */

public class 미로탈출 {

    static int[] dx ={0, 1, 0, -1};
    static int[] dy ={-1, 0, 1, 0};
    static String[][] myMap;
    static int[][] chMap;

    static int minDis = Integer.MAX_VALUE;
    static Queue<int[]> q = new LinkedList<>();


    public static void main(String[] args){
        String[] maps = new String[] {"SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"};
        미로탈출 T = new 미로탈출();
        T.solution(maps);
    }

    public int solution(String[] maps) {
        int answer = 0;
        int stX = 0; //필요없음
        int stY = 0; // 필요없음
        int lX = 0;
        int lY = 0;
        int eX = 0; //필요없음
        int eY = 0; //필요없음

        myMap = new String[maps.length][maps[0].length()];
        chMap = new int[maps.length][maps[0].length()];
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[0].length(); j++) {
                myMap[i][j] = String.valueOf(maps[i].charAt(j));
                //chMap[i][j] = 0;
                if(String.valueOf(maps[i].charAt(j)).equals("S")){ //시작좌표
                    stX = j;
                    stY = i;
                    q.offer(new int[]{stX,stY});
                } else if (String.valueOf(maps[i].charAt(j)).equals("L")) { //레버좌표
                    lX = j;
                    lY = i;
                } else if (String.valueOf(maps[i].charAt(j)).equals("E")) { //탈출구좌표
                    eX = j;
                    eY = i;
                }
            }
        }

        //1. 레버까지의 최소거리 탐색
        bfs("L");
        int minStoL = minDis;
        //2. 레버에서부터 도착점까지 최소거리 탐색
        minDis = Integer.MAX_VALUE;
        chMap = new int[maps.length][maps[0].length()];
        q.offer(new int[]{lX, lY});
        bfs("E");
        int minLtoE = minDis;
        //3. 두개 합
        answer = minStoL + minLtoE;
        if(minStoL == Integer.MAX_VALUE || minLtoE == Integer.MAX_VALUE) answer = -1;
        return answer;
    }

    public void bfs(String goal){
        while (!q.isEmpty()){
            int[] t = q.poll();
            int x = t[0];
            int y = t[1];
            if(myMap[y][x].equals(goal)){
                minDis = Math.min(minDis, chMap[y][x]);
            }else{
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if(nx >= 0 && nx < myMap[0].length && ny >= 0 && ny < myMap.length && !myMap[ny][nx].equals("X") && chMap[ny][nx] == 0){
                        chMap[ny][nx] = chMap[y][x] + 1;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }

}

 

풀이 단계를 설명하면 

1. S -> L 시작지점에서 레버까지의 최소거리를 구한다.

2. L -> E 레버에서부터 탈출구 까지의 최소거리를 구한다.

3. 두개의 합 출력 (탈출구가 없을경우 -1 출력 )

 -> 탈출구가 없는지 판단은

if(minStoL == Integer.MAX_VALUE || minLtoE == Integer.MAX_VALUE) answer = -1;

여기 문구로 판단함 최대값 변수로 집어넣어놨는데 레버나 탈출구를 만나지 않으면 값은 변하지 않음 

 

※ 처음엔 DFS 연습겸 DFS로 접근했더니 역시나 안풀림(시간초과). 

dfs로 접근법또한 Bfs코드하고 비슷함 단지  q스택에 넣는대신 dfs 호출하고 다음코드에서 chMap 에 저장된걸 0으로 만들어주는 백트래킹 과정만 추가하면 된다.