2023 KAKAO BLIND RECRUITMENT - 미로 탈출 명령어 JAVA

 

 

코딩테스트 연습 - 미로 탈출 명령어 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

오랜만에 알고리즘 관련 포스팅을 하는것 같다.

 

문제는 전형적인 '길찾기' 문제로 보였다.하지만 여기서 포인트는 두 가지가 있었다. 

1. 같은 위치를 두번 방문해도 된다.

2. 목표에 도착하더라도 걸어온 경로는 사전순으로 우선순위를 같는다.

 

처음에는 해당 문제를 bfs로 접근하였다. k 라는 이동 거리의 제한이 있었기에, queue에 이동한 위치를 담은 class를 하나씩 담고 이미 사전순으로 앞선 경로가 방문한 위치라면 건너뛰는 형식으로 구현하였다. 

 

bfs 코드

import java.util.LinkedList; 
import java.util.Queue; 
class Solution {
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        int[][] map = new int[n+1][m+1];
        Queue<Pos> queue = new LinkedList<>();
        
        queue.offer(new Pos("",x,y));
        answer = bfs(queue,0,k,n,m,r,c);
        return answer;
    }
    
    String bfs(Queue<Pos> queue, int dist, int k, int n, int m, int r, int c) {
        if(dist > k) return "impossible";
        
        boolean[][] visited = new boolean[n+1][m+1];
        Queue<Pos> newQueue = new LinkedList<>();
        
        while(!queue.isEmpty()) {
            Pos curPos = queue.poll();
            int x = curPos.x;
            int y = curPos.y;
            String tracks = curPos.tracks;
            if(x > n || x == 0 || y > m || y == 0 || visited[x][y]) {
               continue;    
            }
            
            // 목표 도착
            if(x == r && y == c && dist == k) {
                return tracks;
            }
            
            // 방문
            visited[x][y] = true;
            
            newQueue.offer(new Pos(tracks+"d", x+1, y));
            newQueue.offer(new Pos(tracks +"l", x, y-1));
            newQueue.offer(new Pos(tracks +"r", x, y+1));
            newQueue.offer(new Pos(tracks +"u", x-1, y));
            
        }

        dist++;
        return bfs(newQueue,dist,k,n,m,r,c);
    }
    
    class Pos {
        String tracks = "";
        int x = 0;
        int y = 0;
        
        Pos(String tracks, int x, int y) {
            this.tracks = tracks;
            this.x = x;
            this.y = y;
        }
    }
}

해당 방법으로 문제를 성공적으로 풀었다. 하지만, 해당 방법 시간이 많이 소요되었다.

일단 문자열(string)을 변경해 게속 할당하는 방식이 비효율 적이였다. java 에서 str += " ~" 방식은 비효율적이다.

 

해서 문자열을 탐색후 마지막에 추가 하는 방식으로 바꿔보았다. 해당 방식을 구현하기 위해 깊이 우선 탐색 즉, dfs로 구현하였다.

dfs 코드

class Solution {
    static boolean[][][] visited;
    static int k,n,m,r,c = 0;
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        this.k = k;
        this.n = n;
        this.m = m;
        this.r = r;
        this.c = c;
        
        visited = new boolean[n+1][m+1][k+1];
        answer = dfs("",0,x,y);
        StringBuilder sb = new StringBuilder(answer);
        answer = sb.reverse().toString();
        return answer.length() == 0 ? "impossible" : answer;
    }
    
    String dfs(String route, int dist, int x, int y) {
        String answer = "";
        
        if(dist > k ||x > n || x == 0 || y > m || y == 0 || visited[x][y][dist]) {
           return "";    
        }
        
        // 목표 도착
        if(x == r && y == c && dist == k) {
            return route;
        }

        //  현 위치 방문
        visited[x][y][dist] = true;
        
        // 사전순으로
        answer += dfs("d", dist+1, x+1, y);
        if(answer.length() == 0) answer += dfs("l", dist+1, x, y-1);
        if(answer.length() == 0) answer += dfs("r", dist+1, x, y+1);
        if(answer.length() == 0) answer += dfs("u", dist+1, x-1, y);
        
        return answer.length() == 0 ? "" : answer+route;
    }

}