[pg] 프로그래머스 미로탈출

1. 문제 정의

 전형적인 길찾기 문제이다. 지도가 주어지고 o로 된 곳은 지나갈 수 있는 곳 x로 된 곳은 벽으로 막힌 곳이다. 맵 안에는 start 지점, 레버, exit 지점이 있으며, start 지점에서 출발해 레버를 찍고 exit지점에 가야 탈출할 수 있다.

 맵의 크기는 5x5 부터 100x100까지 가능하다.

 

2. 내가 한 시도

 전형적인 BFS문제였다. 그런데 이 문제에서 BFS로직 만으로는 해결할 수는 없었다. 바로 레버 때문이었는데, 레버에 도착 후 다시 돌아가야하는 경우가 있는데, 이 경우 BFS 썼다면 vistied가 이미 뒤로는 갈 수없기 때문에 그 시점에서 전진이 안되고 끝나버리는 경우가 생겼다.

 사실 정말 간단한 발상의 전환만으로도 해결이 가능했지만, 나는 끝내 해결법을 떠올리지 못하고 검색을 통해 해결하였다. 결과는 정말 허무했는데, start지점부터 레버까지의 BFS와 레버를 시작점으로 해서 exit지점까지의 BFS를 두 번 실행하면 해결되는 문제였다.

 코딩테스트 문제는 각 문제마다 알고리즘은 기본이거니와 추가적으로 창의력? 사고력?이 필요한 문제들이 많은 것 같다.

 

3. 코드

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

/**
 * 프로그래머스 LV2
 * 미로 탈출
 * 접근 방법: bfs를 이용해서 구현
 */
public class Solution {

    public int solution(String[] maps) {

        char[][] map = new char[maps.length][maps[0].length()];
        int[] start = new int[2];
        int[] lever = new int[2];

        for (int i = 0; i < maps.length; i++) {
            String s = maps[i];
            for (int j = 0; j < s.length(); j++) {
                map[i][j] = s.charAt(j);

                if (map[i][j] == 'S') {
                    start[0] = i;
                    start[1] = j;
                }
                if (map[i][j] == 'L') {
                    lever[0] = i;
                    lever[1] = j;
                }
            }
        }
        int leverTime = bfs(map, start, 'L');
        int exitTime = bfs(map, lever, 'E');

        if (exitTime == -1 || leverTime == -1) {
            return -1;
        }
        return leverTime + exitTime;
    }

    public int bfs(char[][] map, int[] start, char target) {

        /*
         * 움직일 좌표 설정
         */
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};

        /*
         * 방문 여부 확인용
         */
        boolean[][] visited = new boolean[map.length][map[0].length];

        Queue<Person> queue = new LinkedList<>(); // bfs용 큐

        Person person = new Person(start[0], start[1], 0); // 큐에 넣을 객체

        queue.offer(person);
        visited[person.getX()][person.getY()] = true;

        /*
         * 큐에서 객체 꺼내면서 target을 찾음.
         */
        while (!queue.isEmpty()) {

            Person poll = queue.poll();
            if (map[poll.getX()][poll.getY()] == 'X') { // 벽 일경우
                continue;
            }

            if (map[poll.getX()][poll.getY()] == target) { // target을 찾을 경우 그때까지의 시간을 리턴
                return poll.getSeconds();
            }


            for (int i = 0; i < 4; i++) {
                if (poll.getX() + dx[i] < 0 || poll.getY() + dy[i] < 0
                        || poll.getX() + dx[i] >= map.length || poll.getY() + dy[i] >= map[0].length) {
                    continue;
                }
                if(!visited[poll.getX() + dx[i]][poll.getY() + dy[i]]) {
                    queue.offer(new Person(poll.getX() + dx[i], poll.getY() + dy[i], poll.getSeconds() + 1));
                    visited[poll.getX() + dx[i]][poll.getY() + dy[i]] = true;
                }
            }
        }
        return -1;
    }

    class Person {
        private int x;
        private int y;
        private int seconds;

        public Person(int x, int y, int seconds) {
            this.x = x;
            this.y = y;
            this.seconds = seconds;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int getSeconds() {
            return seconds;
        }

        public void addSeconds() {
            this.seconds++;
        }
    }

}

 

4. 회고

이제 BFS를 작성하는 것에 있어서 조금 익숙해진 느낌이다. 이번 문제는 전형적인 BFS, DFS 문제였지만, Visited를 전역변수가 아닌 BFS 로컬변수로 선언해서 사용해야 했던 것이 특이했던 문제였다. 그리고 BFS를 2번 진행해야 한다는 점도 다른 문제와 차별화 되는 부분이 었다. 

 

참조

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