백준 6087 레이저 통신 자바

태그 : 다익스트라

새로운 테스트 케이스의 등장으로 맞힌 사람이 타노스되고 올바르지 않은 해답들이 돌아다녀, 글을 작성하게 되었다.

테스트 케이스의 등장 전에는 다익 조건에서 if(전의 거울 개수 >= 현재 거울 개수)로 2차원 배열을 선언하여, 중복으로 재탐색하는 풀이가 통과되었다.

하지만 이후는 메모리초과, 시간초과를 받게된다. (80퍼)

그렇다면, 어떻게 해야 하나.

바로 거울 개수를 저장하는 2차원 배열에서 각각의 방향을 추가하여 3차원 배열로 만들면 된다.

[0][i][j]

[1][i][j]

[2][i][j]

[3][i][j]

---> i, j에 4가지 방향의 거울의 개수가 담긴채로 다익스트라가 진행이 된다.

이렇게 되면 <= 로 전의 거울의 개수가 같게되어 중복으로 큐에 들어가는 경우는 배제 할 수 있다.

다익스트라 경우, 큐가 아닌 우선순위 큐를 활용해야한다.

 

코드는 밑에 더보기를 클락하시면 됩니다.

package p_6087;

import java.io.*;
import java.util.*;

public class Main {
	static class Search implements Comparable<Search> {
		int moveX, moveY, cur, mirror;
		public Search(int moveX, int moveY, int cur, int mirror) {
			this.moveX = moveX;
			this.moveY = moveY;
			this.cur = cur;
			this.mirror = mirror;
		}
		public int compareTo(Search o) {
			return this.cur - o.cur;
		}
	}
	static char[][] c;
	static int[][][] count;
	static PriorityQueue<Search> pq;
	static int n;
	static int m;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static int x;
	static int y;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		c = new char[n][m];
		count = new int[4][n][m];
		pq = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
			String k = br.readLine();
			for (int j = 0; j < m; j++) {
				c[i][j] = k.charAt(j);
				if (c[i][j] == 'C' && pq.isEmpty()) {
					pq.offer(new Search(i, j, 0, 0));
					pq.offer(new Search(i, j, 1, 0));
					pq.offer(new Search(i, j, 2, 0));
					pq.offer(new Search(i, j, 3, 0));
					count[0][i][j] = 0;
					count[1][i][j] = 0;
					count[2][i][j] = 0;
					count[3][i][j] = 0;
				} else if (c[i][j] == 'C' && !pq.isEmpty()) {
					x = i;
					y = j;
				}
			}
		}
		for(int i = 0; i < 4; i++) {
			for(int j = 0; j < n; j++) {
				for(int k = 0; k < m; k++) {
					count[i][j][k] = 987654321;
				}
			}
		}
		int min = 987654321;
		while (!pq.isEmpty()) {
			Search g = pq.poll();
			if (g.moveX == x && g.moveY == y) {
				min = Math.min(min, g.mirror);
				continue;
			}
			for (int k = 0; k < 4; k++) {
				int i = g.moveX + dx[k];
				int j = g.moveY + dy[k];
				if (i >= 0 && j >= 0 && i < n && j < m) {
					if(c[i][j] != '*') {
						int tmp = g.mirror;
						if(g.cur != k) tmp++;
						if (count[k][i][j] > tmp) {
							count[k][i][j] = tmp;
							pq.offer(new Search(i, j, k, tmp));
						}
					}
				}
			}
		}
		sb.append(min);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}