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

메모리 초과로 어려움을 겪은 문제다.

BFS, DFS에서 메모리 초과가 난다면, visited를 의심하라.

 

import java.util.*;

//2500 2500    6250000

/*
입력값 〉	3, 4, 2, 3, 3, 1, 5
기댓값 〉	"dllrl"
실행 결과 〉	실행한 결괏값 "dlllr"이 기댓값 "dllrl"과 다릅니다.
출력 〉	d1 l3 r1 u0
*/
class Solution {
    static int[] dy = {1,0,0,-1};
    static int[] dx = {0,-1,1,0};
    static String[] dd = {"d","l","r","u"};
    static boolean[][][] visited;
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        visited = new boolean[n+1][m+1][k+1];
        String answer = getDirects(x,y,r,c,k,n,m);
        if(answer == null){
            return "impossible";
        }
        return answer;
    }
    
    public String getDirects(int y, int x, int r, int c, int k, int n, int m){
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(new Node(y,x,0,""));
        visited[y][x][0] = true;
        while(!queue.isEmpty()){
            Node temp = queue.poll();
            int ty = temp.ty;
            int tx = temp.tx;
            int tv = temp.tv;
            for(int i = 0; i < 4; i++){
                int ny = ty + dy[i];
                int nx = tx + dx[i];
                int nv = tv + 1;
                if(ny < 1 || ny > n || nx < 1 || nx > m)continue;
                if(nv > k)continue;
                if(visited[ny][nx][nv])continue;
                if(ny == r && nx == c && nv == k){
                    System.out.println(y + " " + x);
                    return temp.str + dd[i];
                }
                visited[ny][nx][nv] = true;
                queue.add(new Node(ny, nx, nv, temp.str + dd[i]));
            }
        }
        return null;
    }
}

class Node{
    int ty;
    int tx;
    int tv;
    String str;
    
    Node(int ty, int tx, int tv, String str){
        this.ty = ty;
        this.tx = tx;
        this.tv = tv;
        this.str = str;
    }
}