백준 6087 레이저 통신
문제
https://www.acmicpc.net/problem/6087
접근방법
우선순위, BFS
풀이코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static final int INF = 987654321;
static int N, M, ans;
static char[][] map;
static int[][] visited;
static int[] dr = {-1,0,1,0};
static int[] dc = {0,1,0,-1};
private static class Pos implements Comparable<Pos>{
int r, c, dir, count;
public Pos(int r, int c, int dir, int count) {
super();
this.r = r;
this.c = c;
this.dir = dir;
this.count = count;
}
@Override
public int compareTo(Pos p) {
return this.count - p.count;
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
// 1. 입력 및 초기화
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine(), " ");
M = Integer.parseInt(st.nextToken()); // 열
N = Integer.parseInt(st.nextToken()); // 행
map = new char[N][M];
for(int i=0; i<N; i++) map[i] = in.readLine().toCharArray();
visited = new int[N][M];
for(int i=0; i<N; i++) Arrays.fill(visited[i], INF);
// 2. 우선순위 BFS
Loop:
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j] == 'C') {
bfs(i, j); // 두 개의 C이므로 한 번만 BFS 연결을 시도한다.
break Loop;
}
}
}
// 3. Answer
System.out.println(ans);
}
public static void bfs(int sr, int sc) {
PriorityQueue<Pos> que = new PriorityQueue<Pos>();
que.offer(new Pos(sr, sc, -1, 0)); // 행, 열, 방향, 거울사용횟수
visited[sr][sc] = 0;
while(!que.isEmpty()) {
Pos p = que.poll();
int r = p.r;
int c = p.c;
int dir = p.dir;
int count = p.count;
if(dir != -1 && map[r][c] == 'C') {
ans = count;
break;
} // 종료조건
int nr, nc;
for(int d=0; d<4; d++) {
nr = r + dr[d];
nc = c + dc[d];
if(nr > -1 && nr < N && nc > -1 && nc < M
&& map[nr][nc] != '*') {
// 1) 방향 그대로 가는경우 (처음 시작경우도 포함)
if((dir == d || dir == -1) && (count <= visited[nr][nc])) {
visited[nr][nc] = count;
que.offer(new Pos(nr, nc, d, count));
}
// 2) 기존방향과 다른 방향으로 가는경우 (거울 사용)
else if(dir != -1 && dir != d && (count+1 <= visited[nr][nc])) {
visited[nr][nc] = count + 1;
que.offer(new Pos(nr, nc, d, count+1));
}
}
}
}
}
}