[programmers] 미로 탈출 명령어 (JAVA)

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

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

프로그래머스

 

[접근 방식]

키워드는 '맨해튼 거리' , '백트래킹' 이다.

 

맨해튼 거리란 2차원 평면 좌표 위 두점 점p(x1, y1) 에서 점q(x2, y2)의 최소 거리를 뜻하는 것으로,

맨해튼 거리는 |x1 - x2| + |y1 - y2| 이다.

 

백트래킹 이란 해를 찾는 도중 해가 절대 될 수 없다고 판단되면 되돌아가서 다시 해를 찾는 방법이다.

 

이 두가지 키워드를 이용하는 경우 다음과 같은 접근이 가능하다.

 

1. 시작점에서 도착점 까지의 맨해튼 거리 > k 인 경우 미로를 탈출할 수 없다.

2. 시작점에서 도착점 까지의 맨해튼 거리 <= k 인 경우,
'k - 맨해튼 거리' 가 짝수여야 미로를 탈출할 수 있다.

3. 이동과정에서 '현재 위치에서 도착점까지의 맨해튼 거리' > '남은 이동 횟수' 가 된다면,

미로를 탈출할 수 없기 때문에, 백트래킹 방식을 적용하여 해당 경로는 제외(무시)한다.

 

※ 기존의 2차원 평면 좌표와 조금 다르다!

Down 명령이 일어나는 경우 : x 좌표는 +1, y 좌표는 0 이 일어난다.

Up 명령이 일어나는 경우 : x 좌표는 -1, y 좌표는 0 이일어난다.

Left 명령이 일어나는 경우 : x 좌표는 0, y 좌표는 -1 이 일어난다.

Right 명령이 일어나는 경우 : x 좌표는 0, y 좌표는 +1 이 일어난다.

 

※ 사전순으로 빠른 정렬을 구현해야 함으로, 명령 우선 순서는 d, l, r, u 순이다.   

 

[Java 코드]

class Solution {

  //이동 우선순위 : d, l, r, u (아래, 왼쪽, 오른쪽, 위)
  private static final int[] dx = {1, 0, 0, -1};
  private static final int[] dy = {0, -1, 1, 0};
  private static final char[] dir = {'d', 'l', 'r', 'u'};
  private String result = "impossible";
  private boolean found = false;

  public String solution(int n, int m, int x, int y, int r, int c, int k) {

    //맨해튼 거리 계산
    int distance = Math.abs(r - x) + Math.abs(c - y);

    //불가능 조건 체크
    if (distance > k || (k - distance) % 2 != 0) {
      return "impossible";
    }

    dfs(n, m, x, y, r, c, k, new StringBuilder());
    return result;
  }

  private void dfs(int n, int m, int x, int y, int r, int c, int remainingMoves, StringBuilder path) {
    //목표를 찾은 경우 중단 (조기 발견 해도 '남은 거리' % 2 == 0 을 항상 만족)
    if (found) return;

    //이동이 끝났고, 목적지에 도달했으면 종료
    if (remainingMoves == 0) {
      if (x == r && y == c) {
        result = path.toString();
        found = true;
      }
      return;
    }

    //사전 순 탐색 (d, l, r, u)
    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;

      //현재 위치에서 목적지도 이동 불가한 경우 무시
      int estimateDistance = Math.abs(r - nx) + Math.abs(c - ny);
      if (estimateDistance > remainingMoves - 1) continue;

      //이동
      path.append(dir[i]);
      dfs(n, m, nx, ny, r, c, remainingMoves - 1, path);
      path.deleteCharAt(path.length() - 1); //백트래킹
    }
  }

}

 

[Rewind]