[백준 / BOJ] 6087번 : 레이저 통신 - JAVA

https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

가장 적은 방향 전환

제시된 조건에 따르면 아무리 멀리 돌아가더라도 방향 전환 횟수가 가장 적은 게 답이다. 따라서 방향 전환 횟수를 우선 순위로 두는 PriorityQueue를 사용하여 BFS를 돌렸다. BFS의 성질에 따라 가장 먼저 도착한 노드의 방향 전환 횟수가 정답이기 때문에 바로 break 해주었다.

 

방문 체크

가장 어려웠던 것은 방문 체크를 어떻게 해주느냐 였다. 한 번 방문한 곳을 다시 방문하지 않는다면 오류가 발생한다.

위와 같은 상황일 때, 파란색 경로와 빨간색 경로 모두 1번 꺾인 상태로 노란 칸에 도착하게 된다. 거치는 칸의 개수도 같고, 꺾인 횟수도 같기 때문에 dr, dc의 방향 순서를 어떻게 지정했냐에 파란색 경로가 먼저 Queue에 들어갈 수도 있고, 빨간색 경로가 먼저 Queue에 들어갈 수도 있다.

 

만일 빨간색 경로가 먼저 Queue에 들어가고, 한 번 방문한 곳에 다시 방문하지 못하게 한다면 파란색 경로는 나타나지 못하고 끝날 것이다. (예시에서 다른 경로는 무시한다)

 

따라서 칸만을 기준으로 하는 것이 아니라, 어떤 방향을 가지고 들어와 어떤 방향을 가지고 나갔는지를 파악하도록 했다. 

int[][][][] v = new int[H][W][4][4];

 

전체 코드

// 시간 : 196ms
// 메모리 : 19596KB
public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int W = Integer.parseInt(st.nextToken());
		int H = Integer.parseInt(st.nextToken());
		
		char[][] map = new char[H][W];
		
		int[][] C = new int[2][2];
		int c = 0;
		
		for (int i = 0; i < H; i++) {
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < W; j++) {
				if(map[i][j] == 'C') {
					C[c][0] = i;
					C[c++][1] = j;
				}
			}
		}
		
		int[] dr = {-1,0,1,0};
		int[] dc = {0,-1,0,1};
		
		PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
		});
		que.offer(new int[] {C[0][0], C[0][1], 1, -1});
		
		int[][][][] v = new int[H][W][4][4];
		v[C[0][0]][C[0][1]][0][0] = 1;
		v[C[0][0]][C[0][1]][1][1] = 1;
		v[C[0][0]][C[0][1]][2][2] = 1;
		v[C[0][0]][C[0][1]][3][3] = 1;
		
		
		int min = 0;
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			if(cur[0] == C[1][0] && cur[1] == C[1][1]) {
				min = cur[2];
				break;
			}
			for (int d = 0; d < 4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(nr >= H || nc >= W || nr < 0 || nc < 0) continue;
				if(map[nr][nc] == '*') continue;
				if(cur[3] == -1) {
					v[nr][nc][d][d] = cur[2];
					que.offer(new int[] {nr, nc, cur[2], d});
					continue;
				}
				if(v[nr][nc][cur[3]][d] != 0 && v[nr][nc][cur[3]][d] <= cur[2]) continue;
				
				v[nr][nc][cur[3]][d] = cur[2];
				if(d == cur[3]) que.offer(new int[] {nr, nc, cur[2], d});
				else que.offer(new int[] {nr, nc, cur[2] + 1, d});
			}
		}
		
		System.out.println(min - 1);
		
	}

}