[프로그래머스 150365] 미로 탈출 명령어

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

프로그래머스

 

 

맨 처음 bfs + priority queue를 사용하여 풀이하였고, 시간 초과 ㅜㅜ 가 떴다(아무래도 한 번 방문했던 좌표에 또 방문할 수 있으니까)

아마 처음의 방식의 시간복잡도는.. 4^k횟수(최대 2500)

사실 프로그래머스의 시간 초과 기준은 잘 모르겠지만 2의 5000승 정도면 시간초과가 안 나는게 이상하긴 하지.. 미친거지

 

최적화할 방식이 도저히~~ 생각이 나질 않아서 아래 게시글을 참고하였다

https://velog.io/@ddongh1122/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AF%B8%EB%A1%9C-%ED%83%88%EC%B6%9C-%EB%AA%85%EB%A0%B9%EC%96%B4 

티스토리는 왜 링크 대체텍스트가 안먹히는걸까..? 내가잘못쓰고있는건가

[프로그래머스] 미로 탈출 명령어

 

나의 bfs 구현에서는 priority queue를 적용하여 사전 순으로 경로를 조사하고 있는데,

한 좌표까지의 경로 string의 문자열 길이(복잡하게 적었지만 걍 이동 거리)에 대하여 방문 체크를 추가하여 중복을 삭제하는 방식으로 최적화 하였다

(방문 체크 배열 isVisited[n][m][len] 를 추가)

왜냐면.. 목적지까지 이동해야 하는 거리 k는 정해져있고 k-len이 같은 경우이니까.

 

 

+

dfs는 시간 초과가 일어날 듯해서 쳐다보지도 않았는데.. 대부분의 사람들이 백트래킹으로 문제를 풀이한 듯 하다 🥹

java의 재귀 제한 횟수가 몇천번 아니면 몇만번(1~2만 번 정도?) 이었는데, 여기서 최대 depth는 k=2500이니까 이걸 통과?? 하는 것 같다

 

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
	static class Node {
		int x;
		int y;
		String route;

		public Node(int x, int y, String route) {
			this.x = x;
			this.y = y;
			this.route = route;
		}
	}

	Node start, dest, maxNode;
	boolean[][][] isVisited;
	final int[] dX = {1, 0, 0, -1};
	final int[] dY = {0, -1, 1, 0};
	final char[] suffix = {'d', 'l', 'r', 'u'};

	public String solution(int n, int m, int x, int y, int r, int c, int k) {
		start = new Node(x, y, "");
		dest = new Node(r, c, null);
		maxNode = new Node(n, m, null);
		isVisited = new boolean[n + 1][m + 1][k + 1];
		isVisited[x][y][0] = true;

		return bfs(k);
	}

	private String bfs(int len) {
		StringBuilder sb = new StringBuilder();
		PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparing(o -> o.route));
		pq.add(start);
		while (!pq.isEmpty()) {
			sb.setLength(0);    //초기화
			Node currNode = pq.poll();
			String currRoute = currNode.route;
			int currX = currNode.x, currY = currNode.y;
			sb.append(currRoute);

			if (currRoute.length() >= len) {
				if (currRoute.length() == len && isDestination(currNode)) {
					return currRoute;
				}
				continue;
			}
			for (int i = 0; i < dX.length; i++) {
				int nextX = currX + dX[i], nextY = currY + dY[i];
				if (isAvailable(nextX, nextY, currRoute.length() + 1)) {
					isVisited[nextX][nextY][currRoute.length() + 1] = true;
					sb.append(suffix[i]);
					pq.add(new Node(nextX, nextY, sb.toString()));
					sb.setLength(sb.length() - 1);
				}
			}
		}
		return "impossible";
	}

	private boolean isAvailable(int x, int y, int len) {
		return x >= 1 && x <= maxNode.x && y >= 1 && y <= maxNode.y && !isVisited[x][y][len];
	}

	private boolean isDestination(Node curr) {
		return curr.x == dest.x && curr.y == dest.y;
	}
}

 

 

 

 

 

https://github.com/kkj0419/code_test/pull/47

[2023.02.24] 150365 미로 탈출 명령어 by kkj0419 · Pull Request #47 · kkj0419/code_test