Programmers - 미로탈출 159993번

Programmers - 미로탈출 159993번

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

 

기본적인 길찾기 문제라고 생각했다.

1. 시작지점 -> 레버
2. 레버 -> 출구

이렇게 두번의 탐색을 실행하고, 둘중에 하나라도 못찾을 시 -1 return

Queue 를 활용한 bfs를 이용하여 문제를 풀이했다

 

마지막에 -2를 하고 return 하는 이유는 check 배열에서 이미 지나간 곳인지 체크할 때 0 인지 아닌지로 체크를 하는데, 처음 시작장소를 다시오면 안되므로 출발하는 장소의 check에 1를 넣고 시작했기 때문..

2차원 check배열은 출발지점으로부터 얼만큼 이동했는지 확인할 수 있는 저장장소이며, 이미 지나간 곳인지 확인할 수 있는 역할도 함.

​x
import java.util.LinkedList;
import java.util.Queue;

public class Programmers_159993 {

    final int MAX_MAP_SIZE = 101;

    Coordinate s = new Coordinate();
    Coordinate e = new Coordinate();
    Coordinate l = new Coordinate();

    int[][] map = new int[MAX_MAP_SIZE][MAX_MAP_SIZE];
    int[][] check;

    int[] dir_y = {-1,0,1,0};
    int[] dir_x = {0,1,0,-1};

    int map_height;
    int map_width;

    public int solution(String[] maps) {

        createMap(maps);
        map_height = maps.length;
        map_width = maps[0].length();

        int res1 = bfs(s.y, s.x, l.y, l.x);

        int res2 = bfs(l.y, l.x, e.y, e.x);

        if(res1 == 0 || res2 == 0)
            return -1;

        return res1 + res2 - 2;
    }

    int bfs(int start_y, int start_x, int end_y, int end_x) {

        check = new int[MAX_MAP_SIZE][MAX_MAP_SIZE];

        Queue<Coordinate> q = new LinkedList<>();
        q.add(new Coordinate(start_y,start_x));

        int idx = 1;

        check[start_y][start_x] = idx;

        while(q.size() != 0) {
            int y = q.peek().y;
            int x = q.poll().x;

            for(int i = 0; i < 4; i ++) {
                int next_y = y + dir_y[i];
                int next_x = x + dir_x[i];

                if(next_y < 0 || next_x < 0 || next_y >= map_height || next_x >= map_width)
                    continue;

                if(map[next_y][next_x] == 1 || check[next_y][next_x] != 0)
                    continue;

                check[next_y][next_x] = check[y][x] + 1;
                q.add(new Coordinate(next_y,next_x));
            }
        }

        if(check[end_y][end_x] != 0)
            return check[end_y][end_x];
        else
            return 0;
    }

    void createMap(String[] maps) {
        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length(); j++) {
                String tmp = maps[i].substring(j, j+1);
                if(tmp.equals("X"))
                    map[i][j] = 1;
                else if(tmp.equals("S")) {
                    s.y = i;
                    s.x = j;
                }
                else if(tmp.equals("L")) {
                    l.y = i;
                    l.x = j;
                }
                else if(tmp.equals("E")) {
                    e.y = i;
                    e.x = j;
                }
            }
        }
    }

    class Coordinate {
        int y;
        int x;

        Coordinate() { }
        Coordinate(int y,int x) {
            this.y = y;
            this.x = x;
        }
    }
}