[프로그래머스스쿨] 미로 탈출 명렁어 java - bfs/dfs

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

프로그래머스

 

 

맨 처음에는 기본적인 최단거리 문제라고 생각을 해서

visited 처리 없이 PriorityQueue를 이용한 bfs로 풀었는데..

시간초과로 인해 부분 점수를 맞았다 (omg)

 

📍

처음부터 답이 나올 수 없는 경우는 바로 "impossible" 리턴

int dist = Math.abs(x-r)+Math.abs(y-c);
        if(dist%2!=k%2||dist>k) return "impossible";

1) 거리가 k보다 작은 경우

2) 거리는 k보다 크지만 이동경로상 k에 접근할 수 없는 경우

 

이동횟수의 홀짝성
(dist%2!=k%2)
격자에서 한 칸 이동할 때마다 맨해튼 거리는 1만큼 변합니다.
이때 중요한 것은 이동 횟수와 맨해튼 거리의 홀짝성 관계입니다.
어떤 위치에서든 한 칸 이동하면, 나의 현재 위치는 기존 위치에서 맨해튼 거리가 1만큼 변하게 됩니다.
그런데 다시 원래 자리로 돌아오거나, 같은 거리를 유지하면서 다른 경로로 이동하기 위해서는 짝수 번의 추가 이동이 필요합니다.
만약 목표 지점까지 직선으로 이동한다면, 이동 횟수는 맨해튼 거리와 같습니다.
만약 목표 지점을 지나쳤다가 다시 돌아오거나 다른 경로로 우회한다면, 이동 횟수는 맨해튼 거리보다 2칸, 4칸, 6칸 등 짝수 칸 더 많아지게 됩니다. (왔다갔다 한 번: 2칸, 두 번: 4칸 등)
예를 들어, 맨해튼 거리가 3인 두 지점이 있다고 해봅시다.
최소 3번 이동하여 도달할 수 있습니다.
(홀수)5번 이동하여 도달할 수 있습니다.
(3번 이동 + 2번 왔다갔다 = 5번, 홀수)
7번 이동하여 도달할 수 있습니다.
(3번 이동 + 4번 왔다갔다 = 7번, 홀수)
즉, 시작점에서 목표 지점까지 맨해튼 거리(dist)와 총 이동 횟수(k)의 홀짝성이 같아야만 도달할 수 있습니다.
dist가 홀수이면, k도 홀수여야 합니다.dist가 짝수이면, k도 짝수여야 합니다.
이를 수학적으로 표현한 것이 바로 dist % 2 != k % 2 입니다.

 

📍

bfs로 풀이할 경우 visited처리가 필수이다

같은 x,y 이동경로를 중복해서 방문할 수 있지만

이동거리가 같은 경우는 중복해서 카운팅 할 필요가 없다

boolean[][][] visited = new boolean[x의 경로][y의 경로][이동거리]

 

📍

dfs로 풀이할 경우 최악의 경우 4^k 시간복잡도를 갖지만

가지치기를 조건에 나눠서 해주면 불필요한 연산을 줄일 수 있다

<종료 조건>

1. 이동하는 중에 거리가 k보다 커지는 경우

2. 이미 arr배열을 사전순으로 배치 했기 때문에(r,d,l,u)

dfs에서 맨 처음 담긴 answer 값이 답이다

-> answer에 값이 있는 경우

3. cnt>k인 경우

 

 

[bfs 풀이]

import java.util.*;  
class Solution {  
static int[][] map;  
static int[] dx = {0,1,0,-1};  
static int[] dy = {1,0,-1,0};  
static String[] arr = {"r","d","l","u"};  
static String answer="";  
static class Node implements Comparable {  
    int x;  
    int y;  
    int c;  
    String result;
    public Node(int x,int y,int c,String result){
        this.x=x;
        this.y=y;
        this.c=c;
        this.result=result;
    }

    public int compareTo(Node o){
        if(this.c!=o.c){
            return this.c-o.c;
        }
        return this.result.compareTo(o.result);
    }
}

static void bfs(int n, int m, int x,int y, int r, int c, int k){
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.add(new Node(x,y,0,""));
    boolean[][][] visited = new boolean[n+1][m+1][k+1];
    visited[x][y][0] = true;

    while(!pq.isEmpty()){
        Node now = pq.poll();
        int nowX = now.x;
        int nowY = now.y;
        int nowC = now.c;
        String nowR = now.result;

        if(nowC==k && nowX==r && nowY==c){
            answer = nowR;
            break;
        }

        for(int i=0;i<4;i++){
            int nx = nowX+dx[i];
            int ny = nowY+dy[i];
            if(nx<1||nx>n||ny<1||ny>m||nowC+1>k) continue;

            if(visited[nx][ny][nowC+1]) continue;
            visited[nx][ny][nowC+1]=true;
            pq.add(new Node(nx,ny,nowC+1,nowR+arr[i]));
        }
    }
}
public String solution(int n, int m, int x, int y, int r, int c, int k) {
    map = new int[n+1][m+1];

     // 가능 불가능 판별
    if((Math.abs(x-r) + Math.abs(y-c)) % 2 != k%2) {
        return "impossible";
    }

    if((Math.abs(x-r) + Math.abs(y-c)) > k) return "impossible";
    bfs(n,m,x,y,r,c,k);

    return answer;
}
}

 

[dfs 풀이]

import java.util._;  
import java.io._;  
class Solution {  
    static String[] arr = {"d","l","r","u"};  
    static int[] dx = {1,0,0,-1};  
    static int[] dy = {0,-1,1,0};  
    static int N,M,R,C;  
    static String answer = "";  
    static void dfs(int x, int y, int cnt, int k, ArrayList result){  
        int dist = Math.abs(x-R)+Math.abs(y-C);  
        if(cnt+dist>k) return;  
        if(answer!="") return;  
        if(cnt>k) return;  
        if(cnt==k) {  
            if(x==R&&y==C&&answer==""){  
                for(int i=0;i<result.size();i++){  
                    answer+=result.get(i);  
                }  
            }  
            return;  
          }
        for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<1||nx>N||ny<1||ny>M) continue;
        result.add(arr[i]);
        dfs(nx,ny,cnt+1,k,result);
        result.remove(cnt);
    }
}
public String solution(int n, int m, int x, int y, int r, int c, int k) {
    N=n;
    M=m;
    R=r;
    C=c;

    int dist = Math.abs(x-r)+Math.abs(y-c);
    if(dist%2!=k%2||dist>k) return "impossible";
    else {
        ArrayList<String> result = new ArrayList<>();
        dfs(x,y,0,k,result);
    }
    return answer;
}