[Algorithm] 프로그래머스 미로 탈출 - 자바

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

오늘은 제가 준비했던 회사의 코딩테스트를 진행한 날이었습니다.

정말 한 없이 실력이 모자다라는 것을 느끼고 십 분간 좌절한 후, 현실을 냉철하게 분석하는 시간이 되었습니다.

먼저, 간단하게 회고를 남기고 이어서 프로그래머스 미로 탈출 문제를 해결한 과정을 정리하도록 하겠습니다.

 

1. 회고

제가 본시험은 120분간 4문제를 해결해야 했습니다. 최초 목표는 60, 60분씩 두 문제를 해결하고자 하는 마음으로 출발했습니다.

하지만 1번 문제의 다소 복잡한 구현에서 105분을 소비해 버렸습니다. 예상하지 못한 테스트 케이스를 제가 임의로 추가한 후에, 처음 작성한 문제가 무엇이었는지 파악하고 수정하는데 많은 시간을 소모했습니다. 결국 1번에서 제공해 주신 테스트 케이스는 성공했지만, 2번 문제를 분석할 시간도 없이 2번을 흐적이다가 끝났습니다.

 

끝난 후, 문제의 난이도와 별개로 정말 제 실력이 많이 부족하다는 것을 느끼게 되었습니다. 하지만 큰 경험으로 현재 문제점을 파악하고 앞으로의 공부 방향을 어떻게 잡아야 하는지 느끼게 되었습니다. 알고리즘뿐만 아니라, 특정 문제가 주어졌을 때, 이를 구현하는 실력과 빠른 시간 내에 문제를 파악하고 코드를 작성해야하는 것을 느끼게 되었습니다.

 

이에 현실을 자각할 수 있었고, 헤이해진 몸과 정신을 다 잡을 수 있는 기회가 되었습니다. 좌절할 시간도 아깝기에 바로 다른 부분을 공부하며 흐름이 끊기지 않도록 하였습니다.

 

그럼 본론으로 들어가서 프로그래머스 미로 탈출 문제를 해결하도록 하겠습니다.

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

 

 

2. 프로그래머스 미로 탈출 해결하기

 

<소스>

 

// 4: 18 ~ 5: 27//

import java.util.*;

class Solution {
    
    static final int[] D_X = {-1, 0, 1, 0}; // x 이동 좌표
    static final int[] D_Y = {0, -1, 0, 1}; // y 이동 좌표
    
    int eX; // 도착지 x좌표
    int eY; // 도착지 y좌표
    
    public int solution(String[] maps) {        
        int sX = 0, sY = 0, lX = 0, lY = 0; // s는 출발지 좌표, l은 레버 좌표
        
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[0].length(); j++) {
                if (maps[i].charAt(j) == 'S') {
                    sX = i;
                    sY = j;
                } else if (maps[i].charAt(j) == 'E') {
                    eX = i;
                    eY = j;
                } else if (maps[i].charAt(j) == 'L') {
                    lX = i;
                    lY = j;
                }
            }
        }
        
        boolean[][] visited = new boolean[maps.length][maps[0].length()]; // 방문여부
        
        int step = bfs(new Node(sX, sY, 0), lX, lY, maps, visited, false);  // bfs로 먼저 시작점 -> 레버의 최단 거리 
        if (step == -1) return -1; // 만약 갈 수 없는 경우
        
        int sToE = bfs(new Node(sX, sY, step * 2), eX, eY, maps, visited, true);  // 시작점 -> 레버 -> 시작점 -> 도착점   
        int lToE = bfs(new Node(lX, lY, step), eX, eY, maps, visited, true);   // 시작점 -> 레버 -> 도착점
        
        if (lToE == -1) return sToE;
        else if (sToE == -1) return lToE;
        return Math.min(lToE, sToE);
    }
    
    private int bfs(Node node, int eX, int eY, String[] maps, boolean[][] visited, boolean refresh) {
        Queue<Node> queue = new ArrayDeque<>(); // bfs를 위한 queue
        queue.add(node); 
        
        if (refresh) {
            for (int i = 0; i < visited.length; i++) {
                for (int j = 0; j < visited[i].length; j++)
                    visited[i][j] = false; // 방문 여부 초기화
            }
        }

        while(!queue.isEmpty()) {
            
            Node n = queue.poll(); // 큐에서 꺼내기
            
            if (n.x == eX && n.y == eY) return n.step; // 최단 거리 리턴
            if (visited[n.x][n.y]) continue; // 방문한 경우 패스
            
            visited[n.x][n.y] = true; // 방문 여부 설정
            
            for (int k = 0; k < 4; k++) {
                int newX = n.x + D_X[k]; // 새로운 좌표 설정
                int newY = n.y + D_Y[k];
                
                if (validRange(newX, newY, maps, visited)) {
                    queue.add(new Node(newX, newY, n.step + 1));
                }
            }
        }
        return -1;
    }
    
    // 방문한 경우가 아니고 유효한 인덱스 && 지나갈 수 있는 경로일 경우
    private boolean validRange(int x, int y, String[] maps, boolean[][] visited) {
        return x >= 0 && y >= 0 && x < maps.length && y < maps[x].length()
            && !visited[x][y] && (maps[x].charAt(y) != 'X');
    }
    
    class Node {
        int x;
        int y;
        int step;
        
        Node (int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
}

 

 

 

3. 특이점

 

이 문제를 처음에 "이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다."라는 문구를 보고, 레버의 유무는 크게 상관이 없는 것인가 의아해하면서 일반적인 bfs로 문제를 해결했습니다.

 

하지만, 테스트 케이스를 실패하였고, 문제를 다시 읽어보고 레버의 문제 출제 의도를 파악해 보았습니다. 

여기서 말하는 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있다는 의미는, 출구를 통과하여 해당 알고리즘을 끝내는 것이 아니라, 말 그대로 지나갈 수 만 있다는 의미였습니다.

즉, 시작점 S -> L -> E로 레버를 통과해야만 E로 가서 미로를 통과할 수 있습니다.

 

 

 

4. 가능한 경우와 알고리즘

 

미로를 탈출하거나 종료하기 위해서는 먼저 S -> L -> E의 루트를 거치거나 혹은 E로 갈 수 없는 경우로 종료를 해야 합니다.

 

여기서 확인할 수 있는 경우는 크게 4가지입니다.

 

• S -> L -> E  (시작점에서 도착지로 가는 과정에 레버가 존재)  return step
• S -> L -> S -> E  (레버와 도착지 사이에 출발지가 있는 경우) return step
• S -> L -> || --x-----   E  레버까지는 도착했지만 레버에서 도착지로 갈 수 없는 경우  return -1
• S ---x---  ||  ---x----   L  레버까지 갈 수 없는 경우 return -1

 

따라서, 

먼저 S -> L로 출발지에서 레버까지의 step을 bfs로 계산한 후, 만약 -1이라면 그대로 return으로 해당 메서드를 종료하고,
만약 -1이 아닌 양수가 나온다면 출발지에서 레버까지 갈 수 있는 최단 경로이므로 해당 step을 더하여 

L -> E (1)과 S -> E (2)를 계산합니다.

 

여기서 주의할 점은 S -> E가 되는 경우 S -> L까지 이동한 경로인 step * 2를 해야 다시 S에 도착할 수 있습니다.

그리하여 만약 (1) 과 (2) 중 하나라도 -1이라면 다른 하나가 정답이 되고 둘 다 -1인 경우 -1, 둘 다 -1이 아니라면 최솟값이 정답이 됩니다.

 

정리하면, bfs를 적용하되 가능한 경로 경우를 나눠서 최소 경로를 판단해야하는 문제였습니다.

테스트 케이스와 정답 제출 결과는 다음과 같습니다.

 

["SOOOL", "OXXXO", "OXXXO", "OXXXO", "EXOOO"] , 12

["SOOOL", "OXXXX", "OXXXX", "OXXXX", "EXXXX"], 12

["SOOOL", "XXXXO", "OXXXO", "OXXXO", "EXOOO"],  -1

 

 

이상으로 프로그래머스 미로 탈출 문제를 정리하도록 하겠습니다. 

감사합니다.!