[Algorithm] 프로그래머스 미로 탐색 명령어 - Java

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

문제 설명

• N x M 크기의 미로가 존재한다.
• 미로 안에서 움직일 수 있는 방향은 상하좌우 뿐이다.
• 제한사항
  • 미로의 벽 바깥으로는 움직이지 못 한다.
  • 시작점에서 탈출 지점까지 K만큼 움직여야 하며, 왔던 경로를 재방문 할 수 있다.
  • 탈출한 경로를 u(상), d(하), l(좌), r(우)로 나타냈을 때 사전 순으로 가장 빠른 경로로 탈출해야 한다.

풀이 과정

문제를 보자마자 아 이건 완전 탐색이다 싶었다.

갈 수 있는 경로를 모두 체크해서 그 중 사전 순으로 가장 빠른 경로를 출력하면 된다고 생각해 DFS 알고리즘을 사용해 풀었었다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    static Character[] location = {'l', 'u', 'r', 'd'};

    static char[][] campus;

    static String result = "impossible";
    static ArrayList<String> resultList = new ArrayList<>();
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};

    static int N, M, X, Y, R, C, K;


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

        campus = new char[n][m];
        N = n;
        M = m;
        Y = y - 1;
        X = x - 1;
        R = r - 1;
        C = c - 1;
        K = k;

        if (y == c && x == r) return "";

        dfs(X, Y, 0, "");

		// resultList가 비어있다면 impossible 출력
        if (resultList.isEmpty()) {
            return result;
        }
        // resultList를 사전 순으로 정렬 후 첫 번째 경로 출력
        else {
            Collections.sort(resultList);
            return resultList.get(0);
        }
    }

    public static void dfs(int x, int y, int cnt, String str) {
        
        // 남은 경로로 이동할 수 없으면 그냥 return
        int remainMoves = K - cnt;
        int distanceToGoal = Math.abs(R - x) + Math.abs(C - y);
        if (remainMoves < distanceToGoal) return;

		// K번 이동했을 때 위치가 (R, C)면 resultList에 경로 추가
        if (cnt == K) {
            if (x == R && y == C) {
                resultList.add(str);
            }
            return;
        }

		// 경로 탐색
        for (int i = 0; i < 4; i++) {
            int fx = x + dx[i];
            int fy = y + dy[i];

            if (fy < 0 || fx < 0 || fx >= N || fy >= M) continue;

            dfs(fx, fy, cnt + 1, str + location[i]);
        }
    }
}

이렇게 resultList를 만들어 경로를 모두 찾아준 후, Collections.sort로 사전 순 정렬을 해줬는데 결과는 대참패였다.

아마 7문제 빼고 전부 시간 초과나 메모리 초과였던 것 같다.

이대로는 시간복잡도가 너무 크고 불필요한 경로까지 모두 찾아야 한다는 생각에 List 형태로 저장하지 않고, 애초에 사전 순으로 빠른 경로부터 찾도록 변경해야 한다는 생각이 들었고 그게 아래의 코드다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
	// 경로를 찾을 때 움직이는 순서 변경
    static Character[] location = {'d', 'l', 'r', 'u'};
    static char[][] campus;
    static String result = "impossible";
    static int[] dy = {0, -1, 1, 0};
    static int[] dx = {1, 0, 0, -1};
    static int N, M, X, Y, R, C, K;


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

        campus = new char[n][m];
        N = n;
        M = m;
        Y = y - 1;
        X = x - 1;
        R = r - 1;
        C = c - 1;
        K = k;

        if (y == c && x == r) return "";
        
        // 가지치기 - 애초에 갈 수 없는 경우
        if (!isAvailable(X, Y, 0)) return result;

        dfs(X, Y, 0, "");

        return result;
    }

	// 목적지까지 갈 수 있는지 없는지 판별하는 함수
    public static boolean isAvailable(int x, int y, int cnt) {
        int remainMoves = K - cnt;
        int distanceToGoal = Math.abs(R - x) + Math.abs(C - y);

        return remainMoves >= distanceToGoal && ((remainMoves - distanceToGoal) % 2 == 0);
    }

    public static boolean dfs(int x, int y, int cnt, String str) {
    
    	// 남은 횟수 안에 갈 수 없으면 바로 false 반환
        if(!isAvailable(x, y, cnt)) return false;

		// K만큼 이동하여 현재 위치가 (R, C)인가?
        if (cnt == K) {
        	// 맞으면 result를 str로 변경 후 true 반환
            if (x == R && y == C) {
                result = str;
                return true;
            }
            // 아닌 경우 false 반환
            return false;
        }

        for (int i = 0; i < 4; i++) {
            int fx = x + dx[i];
            int fy = y + dy[i];

            if (fy < 0 || fx < 0 || fx >= N || fy >= M) continue;
			// 더 움직였을 때 도착 가능하면 true 반환
            if (dfs(fx, fy, cnt + 1, str + location[i])) {
                return true;
            }
        }
		
        // 기본적으로 false 반환
        return false;
    }
}

변경사항은 아래와 같다.

1. 움직이는 순서를 사전 순으로 설정
   • l -> u -> r -> d 순에서 d -> l -> r -> u로 변경
2. 애초에 탈출이 불가능한 경우는 solution 함수 내에서 가지치기
   • isAvailable 함수를 생성하여 true - false 반환
3. 경로 탐색 시작 시 남은 횟수 안에 갈 수 없다면 더이상 경로를 찾지 않고 false 반환
4. 리스트로 경로를 모두 저장하지 않고 찾은 경로를 바로 result에 삽입

위와 같은 변경을 거치고 나니, 통과됐다.

뭔가 2023 카카오 공채 코테는 전체적으로 어떻게 풀어야 할지는 알겠지만 이런저런 조건을 생각하는 곳에서 많이 삐끗했던 것 같다.
그래도 점점 문제를 봤을 때 풀기 위해 코드를 구성하는 능력이 길러지고 있는 것 같다.

다음엔 2023 카카오 공채 코테 중 다른 lv.3 문제들을 가지고 오겠다.