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

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

프로그래머스

---

문제 풀이

1. 시작점 -> 레버로 가는 최단 경로 StoL을 구한다.
2. StoL이 0이라면, 미로를 통과할 수 없으므로 -1을 리턴한다.
3. StoL이 0보다 크다면, 레버 -> 탈출구로 가는 최단 경로 'LtoE'를 구한다.
4. LtoE가 0이라면, 미로를 통과할 수 없으므로 -1을 리턴한다.
5. LtoE가 0보다 크다면, StoE + LtoE를 리턴한다. -> BFS를 총 2번 수행해야 함
 
 
실수한 점
1. BFS 구현 시, depth를 정확히 이해하지 못해 풀이에 오래 걸렸다. -> 한 point에서 4방향을 탐색하는 동안 depth는 동일해야 한다.
2. 'endChar'를 만났을 경우 'break'만 건다면 BFS가 종료되지 않는다. 함수 return을 해주어야 한다.

import java.util.*;

class Point {
    int x;
    int y;
    int depth;
    
    public Point(int x, int y, int depth) {
        this.x = x;
        this.y = y;
        this.depth = depth;
    }
}

class Solution {
    
    static int dx[] = {0, 0, -1, 1};
    static int dy[] = {-1, 1, 0 ,0};
    static char map[][];
    static boolean visited[][];
    int answer = 0; int a = 0; int b = 0;
    Queue<Point> q = new LinkedList<>();
    
    public int solution(String[] maps) {
        int StoL = 0; // 시작점 ~ 레버까지 가는데 걸린 시간
        int LtoE = 0; // 레버 ~ 출구까지 가는데 걸린 시간
        
        // 1. maps을 2차원 배열 map으로 변환
        a = maps.length;
        b = maps[0].length();
        map = new char[a][b];
        
        for(int i=0; i<a; i++) {
            String str = maps[i];
            for(int j=0; j<b; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        
        // 2. 시작점과 레버 좌표 찾기
        int sI = 0; int sJ = 0; // 시작점 좌표 저장용
        int lI = 0; int lJ = 0; // 레버 좌표 저장용
        
        for(int i=0; i<a; i++) {
            for(int j=0; j<b; j++) {
                if(map[i][j] == 'S') { 
                    sI = i;
                    sJ = j;
                } else if(map[i][j] == 'L') {
                    lI = i;
                    lJ = j;
                }
            }
        }
        
        // 시작점 ~ 레버까지 bfs
        StoL = bfs(sI, sJ, 'L');
        
        if(StoL == 0) {
            // 시작점부터 레버까지 갈 수 없다면 -1
            answer = -1;
        } else {
            // 레버 ~ 출구까지 bfs
            LtoE = bfs(lI, lJ, 'E'); 

            // 레버에서 출구까지 갈 수 없다면 -1
            if(LtoE == 0) {
                answer = -1;
            } else {
                answer = StoL + LtoE;
            }
        }
        System.out.println("StoL : " + StoL);System.out.println("LtoE : " + LtoE);
        return answer;
    }
    
    // BFS 알고리즘
    int bfs(int x, int y, char endChar) { 
	    int sec = 0;
        visited = new boolean[a][b]; 
        q = new LinkedList<>();
        q.add(new Point(x, y, 0));
        visited[x][y] = true; 
       
        while(!q.isEmpty()) {
            // 1. 큐에서 꺼내옴
            Point p = q.poll();
			int depth = p.depth + 1;
            
            // 2. 연결된 곳 순회
            for(int i=0; i<4; i++) {
                int nextX = p.x + dx[i];
                int nextY = p.y + dy[i];
                
                // 3. 갈 수 있는가?
                if(nextY >= 0 && nextY < b && nextX >= 0 && nextX < a
                    && map[nextX][nextY] != 'X' && !visited[nextX][nextY]) {
					
					
					// int depth = p.depth += 1;
                    /*
					System.out.println("p.x : " + nextX);
					System.out.println("p.y : " + nextY);
					System.out.println("p.depth : " + depth);
					System.out.println();
					*/
					
                    if(map[nextX][nextY] == endChar) {
                        return depth;
                    } else {
                        q.add(new Point(nextX, nextY, depth));
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
        return sec;
    }
}