[BFS] - Lv2 - 미로탈출

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

프로그래머스

 

🌿 - 문제설명

🌿 - 제한사항

 

📌- 풀이

경우의 수 문제로 몇번 접해본 기억이 있어서 비슷하게 해결했습니다.

중간 지점을 무조건 들려야 하기 때문에 처음 시작 지점 -> 중간 지점까지와 중간 지점 -> 도착 지점을

두 가지로 분리해서 계산하면 결과가 나오게 됩니다.

1. 여기서는 경우의 수를 계산하는 것이 아니라 완전탐색을 해야하기 때문에 BFS로 처음 지점 -> 중간지점
2. 중간지점을 시작 지점으로 중간 지점 -> 도착 지점

 

Node result= bfs(bfs(node, map1,'L'),map2,'E'); // map1 = S->L, map2 = L->E 

 

이렇게 2번 BFS를 하게되면 결과값이 나오게 됩니다.

 

🔥 - Java 코드

 

import java.util.*;

class Solution {
        static char[][] map1, map2; // map1 = S부터 L까지 사용, map2= L부터 E까지 찾을 때
        static int[] dx = {0,0,1,-1};
        static int[] dy = {1,-1,0,0};
        static int N,M;
    
    public int solution(String[] maps) {
        int answer = 0;
        N = maps.length;
        M = maps[0].length();
        map1 = new char[N][M];
        map2 = new char[N][M];
        Node node = null;
        
        for(int i=0;i<N;i++){ // map1,2 셋팅
            for(int j=0;j<M;j++){
                char c = maps[i].charAt(j);
                map1[i][j] = c;
                map2[i][j] = c;
                if(c == 'S'){ 
                    node = new Node(i,j,0); // 시작 노드 생성
                }   
            }
        }
        
        Node result= bfs(bfs(node, map1,'L'),map2,'E'); // map1 = S->L, map2 = L->E 하기 위함
        answer = result.depth;
        return answer;
    }
    
    public Node bfs(Node start, char[][] map, char find){
        
        if(start.depth == -1){ // depth가 -1이면 도착할 수 없는 경우이므로 종료
            return new Node(0,0,-1);
        }
        Queue<Node> que = new LinkedList<>();
        que.add(start);
        
        while(!que.isEmpty()){
            Node next= que.poll();

            if(map[next.x][next.y] == find){
                return next;
            }
            
            for(int i=0;i<4;i++){
                int nx = next.x + dx[i];
                int ny = next.y + dy[i];
                if(0<= nx && nx < N && 0<= ny && ny < M && map[nx][ny] != 'X'){
                    que.add(new Node(nx,ny,next.depth +1));
                    if(map[nx][ny] != find){
                        map[nx][ny] = 'X';
                    }
                    
                }
            }
            
        }
        return new Node(0,0,-1);
    }
}

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