미로 탈출 명령어(프로그래머스) JAVA

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

프로그래머스

 

문제 설명

• 격자의 바깥으로 나갈 수 없다.
• (x,y) 에서 (r,c) 까지 이동하는 거리가 총 k 여야 한다.
• (x,y) 와 (r,c) 격자를 포함해, 같은 격자를 두 번 이상 방문해도 된다.
• 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이  사전 순으로 가장 빠른 경로로 탈출해야 한다.

사전순으로 했을 때, dllrl이 제일 빠르므로 답은 dllrl이다. 만약 k 안에 E지점까지 갈 수 없다면 impossible을 리턴해야 한다.

 

문제에 대한 아이디어

해결해야 할 조건들이 몇가지 존재한다.

1. 출발점에서 끝 지점 까지 k 안에 도착하기
2. 도착 가능 한 많은 경우의 수 중에 사전순으로 제일 빠른거 고르기
3. 한번 들린 지점도 또 갈수 있다.

 

출발점에서 끝 지점까지 k안에 도착하기

일단 출발지점과 도착지점이 정해져있고 경로가 여러개가 존재할 수 있다는 점에서 나는 BFS를 선택했다. (나중에 답을 찾아보니 DFS로도 풀 수 있다고 한다). 특정한 좌표에 도착하면 그 좌표에 어떻게 왔는지 String으로 저장하는 것이다.

만약 1,1 에서 1,2로 갔으면 1, 2, u가 저장되는 것이다.

 

도착 가능 한 많은 경우의 수 중에 사전순으로 제일 빠른거 고르기

이 부분을 해결하다가 생각난 방법은 굳이 많은 경로를 다 돌아보지 말고 사전순으로 빠른 순서대로 경로를 선택하면 되지 않을까? 였다. 사전 순은 d, l, r, u 이므로 이 순서대로 경로를 선택해서 돌아보면 제일 첫번째로 End 지점에 도착한 경로를 선택하는 것이다.

 

한번 들린 지점도 또 갈 수 있다.

이 부분은 평범한 BFS이면 보통 visited 2차원 배열을 만든다. 그리고 좌표를 방문하면 true로 바꾼다. 즉, 이 좌표는 방문했다는 것을 알려준다. 

이 문제는 그 지점을 방문해도 또 그 지점을 갈 수가 있다. 그래서 다른 visited 배열이 필요하다고 생각했다.

특정한 지점을 갈 때 달라지는 것을 생각해보니 바로 경로의 길이가 바뀐다. 

예를 들어 1,1 에서 1,2를 갔다가 1,1로 돌아온다하면 처음은 (1,1,"") (1,2,"u") (1,1,"ud") 이렇게 된다. 그러므로 visited 배열을 3차원 배열로 만들었다.

boolean visited[][][] 이고 y좌표, x좌표, 문자열의 길이를 각각 나타낸다!!

 

구현

char [][] pro; 
int dx[] = {0,-1,1,0};
int dy[] = {1,0,0,-1};
char ch[] = {'d','l','r','u'}; //사전순
boolean visited[][][]; //3차원 배열

• Node

class Node {
    int y; int x;
    String str;
    public Node(int y, int x, String str){
        this.y = y;
        this.x = x;
        this.str = str;
    }
}

• Solution

 public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        pro = new char[n+1][m+1];
        visited = new boolean[n+1][m+1][k+1];
        pro[x][y] = 'S'; pro[r][c] = 'E';
        answer = BFS(n,m,x,y,r,c,k);
        return answer;
    }

y와 x가 0 보다 크므로 배열의 크기를 하나씩 크게 만들어줬다.

• BFS

public String BFS(int n, int m, int y, int x, int r, int c, int k){
        //BFS를 할 때 Deque를 자주 사용함
        Deque<Node> dq = new ArrayDeque<>();
        dq.addFirst(new Node(y,x,""));
        visited[y][x][0] = true;
        while(!dq.isEmpty()){
            Node now = dq.removeFirst();
            //도착 지점에 도착하면 길이 비교
            if(r == now.y && c == now.x){
                if(now.str.length() == k){
                    return now.str;
                }
            }
            //만약 도착 지점에 도착은 안했지만 이미 k만큼 왔다면 더이상 조사 안해도 된다. 
            if(now.str.length() == k) continue;
            //방향 탐색
            for(int i = 0; i<4; ++i){
                StringBuilder sb = new StringBuilder(now.str);
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx <= 0 || nx > m || ny <=0 || ny > n) continue;
                if(visited[ny][nx][now.str.length()+1]) continue;
                visited[ny][nx][now.str.length()+1] = true;
                sb.append(ch[i]);
                dq.addLast(new Node(ny,nx,sb.toString()));
            }
        }
        return "impossible";
    }

StringBuilder를 사용한 이유
자바에서 String 객체는 변경 불가능하다. 한 번 생성되면 내용을 바꿀 수 없다. 따라서 하나의 문자열을 다른 문자열과 연결하면 새 문자열이 생성되고, 이전 문자열은 가비지 컬렉터로 들어간다.
StringBuilder의 객체를 생성한 후, append()의 인자로 연결하고자 하는 문자열을 넣어서 StringBuilder의 객체를 통해 호출한다. 그리고 출력 시에는 toString()을 붙여야 하고, String 변수에 넣을 때도 마찬가지다.
setCharAt,deleteCharAt 같이 String을 쉽게 변경할 수 있다.