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

문제 설명

출발점 , 도착점이 주어진다. 도착점 까지 k거리가 걸려 올 때, 올수 있는 경로는 여러가지이다. 그중 사전순으로 가장 앞선 경로를 나타내는 문제이다.

주의할점

• 출발지 , 목적지를 다시 방문해도 상관없음에 유의해야 한다.
  • 그래서 아마 일반적인 BFS 큐가 커져 시간초과가 난다.
• BFS를 사용한다면 큐에 담긴 객체를 최적화 해야한다.

TRY

큐안에 담긴 객체를 최적화 하기위해 3가지 시도를 했다.

1. 현재 온 거리 +1 > k 크다면 삽입 x [시간초과] - 4개 맞음
2. 현재 온거리 + 맨헤튼 거리 > k 일 경우 삽입 x [시간초과] - 6개 맞음
3. 3차원 방문 [통과]
   • 사전 순으로 먼저 인것을 골라내기 위해 d,l,r,u 으로 거리백터까지 생성해야함

풀이

public String solution(int n, int m, int x, int y, int r, int c, int k) {
		String answer = "";
		N = n;
		M = m;

		Node start = new Node(x - 1, y - 1);
		LinkedList<Node> q = new LinkedList<>();
		List<String> results = new ArrayList<>();
		q.offer(start);

		boolean v[][][] = new boolean[k + 1][n][m];
		v[0][x - 1][y - 1] = true;
		// 핵심은 큐안에 담기는 노드를 최적화해야함. 안그러면 TLE
		while (!q.isEmpty()) {
			Node cur = q.poll();

			if (cur.y == r - 1 && cur.x == c - 1 && cur.cnt == k) {
				results.add(cur.path);
				continue;
			}

			for (int i = 0; i < 4; i++) {
				int ny = dy[i] + cur.y;
				int nx = dx[i] + cur.x;

				if (isOutOfRange(ny, nx))
					continue;

				if (cur.cnt + 1 > k || v[cur.cnt + 1][ny][nx])
					continue;
				Node next = new Node(ny, nx, cur.cnt + 1, cur.path + dirs.get(i));
				q.offer(next);
				v[next.path.length()][ny][nx] = true;
			}
		}

		Collections.sort(results);

		if (results.isEmpty()) {
			return "impossible";
		}

		return results.get(0);
	}

	boolean isOutOfRange(int ny, int nx) {
		return ny < 0 || nx < 0 || ny >= N || nx >= M;
	}