[JAVA]백준_6087_레이저통신

문제 : www.acmicpc.net/problem/6087  

6087번: 레이저 통신

 

문제 유형 : BFS + DP, 다익스트라(우선순위큐)

 

풀이 방식 

Step 1. 시작점과 끝점을 파악한 후 visited[][] int형 2차원 배열값을 최대치로 초기화한다.

Step 2. 우선순위 큐를 이용하여 다익스트라 알고리즘 

Step 3. 방향이 같을때 visited[nr][nc]와 현재 거울 개수를 비교

          방향이 다를때 visited[nr][nc]와 현재 거울 개수 +1 를 비교

 

소스코드

package BOJ;

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

public class BOJ_6087_레이저통신_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 answer = 0, start_r = 0, start_c = 0, end_r=0, end_c=0;
		boolean flag = false;
		
		for (int i = 0; i < H; i++) {
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < W; j++) {
				if(map[i][j]=='C') {
					if(!flag) {
						start_r = i;
						start_c = j;
						flag = true;
					}else {
						end_r = i;
						end_c = j;
						break;
					}
				}
			}
		}
		
		int[][] visited = new int[H][W];
		for (int i = 0; i < H; i++) {
			Arrays.fill(visited[i], Integer.MAX_VALUE);
		}
		
		int[] dr = {0, 0, 1, -1};
		int[] dc = {1, -1, 0, 0};
		
		PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2]-o2[2];
			}
		});
		pq.offer(new int[] {start_r, start_c, 0, 4}); // r, c, 거울개수, 방향
		
		visited[start_r][start_c] = 0;
		
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			if(cur[0]==end_r&&cur[1]==end_c) {
				answer = cur[2];
				break;
			}
			
			for (int d = 0; d < 4; d++) {
				int nr = dr[d] + cur[0];
				int nc = dc[d] + cur[1];
				
				if(nr>-1&&nc>-1&&nr<H&&nc<W && map[nr][nc]!='*') {
					if(cur[3]==4 || cur[3]==d) {
						if(visited[nr][nc] >= cur[2]) {
							visited[nr][nc] = cur[2];
							pq.offer(new int[] {nr, nc, cur[2], d});
						}
					}else {
						if(visited[nr][nc] >= cur[2]+1) {
							visited[nr][nc] = cur[2]+1;
							pq.offer(new int[] {nr, nc, cur[2]+1, d});
						}
					}
				}
			}
		}
		
		
		System.out.println(answer);
		
		
	}

}