1. 문제 링크
https://www.acmicpc.net/problem/6087
2. 문제
요약
- 크기가 1 x 1인 정사각형으로 나누어진 W x H 크기의 지도에 각 칸은 빈 칸이거나 벽이며, 두 칸은 'c'로 표시되어 있는 칸입니다.
- 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있습니다.
- 'c'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 문제입니다.
- 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 W, H가 주어지고 두 번째 줄부터 H개의 줄에 지도가 주어집니다. 지도의 각 문자가 의미하는 것은 다음과 같습니다. 'c'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어집니다.
- . : 빈칸
- * : 벽
- C : 레이저로 연결해야 하는 칸
- 출력: 첫 번째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력합니다.
3. 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int W, H;
static char[][] map;
static int[][] lasers;
static void input() {
Reader scanner = new Reader();
W = scanner.nextInt();
H = scanner.nextInt();
map = new char[H][W];
lasers = new int[2][2];
int idx = 0;
for(int row = 0; row < H; row++) {
String info = scanner.nextLine();
for(int col = 0; col < W; col++) {
map[row][col] = info.charAt(col);
if(map[row][col] == 'C') {
lasers[idx][0] = row;
lasers[idx][1] = col;
idx++;
}
}
}
}
static void solution() {
int answer = bfs(lasers[0], lasers[1]);
System.out.println(answer);
}
static int bfs(int[] start, int[] end) {
PriorityQueue<Loc> queue = new PriorityQueue<>();
int[][] visited = new int[H][W];
for(int row = 0; row < H; row++)
Arrays.fill(visited[row], Integer.MAX_VALUE);
int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
queue.offer(new Loc(start[0], start[1], 0, 4));
int answer = -1;
while(!queue.isEmpty()) {
Loc cur = queue.poll();
if(cur.x == end[0] && cur.y == end[1]) {
answer = cur.mirrorNum;
break;
}
for(int dir = 0; dir < 4; dir++) {
int cx = cur.x + dx[dir], cy = cur.y + dy[dir];
if(isInMap(cx, cy)) {
if(map[cx][cy] != '*') {
if(cur.direction == dir || cur.direction == 4) {
if(visited[cx][cy] >= cur.mirrorNum) {
visited[cx][cy] = cur.mirrorNum;
queue.offer(new Loc(cx, cy, cur.mirrorNum, dir));
}
} else {
if(visited[cx][cy] >= cur.mirrorNum + 1) {
visited[cx][cy] = cur.mirrorNum + 1;
queue.offer(new Loc(cx, cy, cur.mirrorNum + 1, dir));
}
}
}
}
}
}
return answer;
}
static boolean isInMap(int x, int y) {
if(x >= 0 && x < H && y >= 0 && y < W) return true;
return false;
}
static class Loc implements Comparable<Loc> {
int x, y, mirrorNum, direction;
public Loc(int x, int y, int mirrorNum, int direction) {
this.x = x;
this.y = y;
this.mirrorNum = mirrorNum;
this.direction = direction;
}
@Override
public int compareTo(Loc l) {
return this.mirrorNum - l.mirrorNum;
}
}
public static void main(String[] args) {
input();
solution();
}
static class Reader {
BufferedReader br;
StringTokenizer st;
public Reader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while(st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}4. 접근
- BFS 탐색 시에 레이저의 방향 및 사용한 거울의 개수를 나타내기 위해 Loc 클래스를 생성합니다.
- Loc 클래스는 해당 위치의 x, y 좌표, 사용한 거울의 개수 mirrorNum, 레이저의 방향 direction을 멤버로 가집니다.
- 또한 Comparable 인터페이스를 구현하여 사용한 거울의 개수의 오름차순으로 정렬될 수 있도록 합니다.
- 주어진 지도의 정보를 map이라는 2차원 배열에 담고 C의 위치들을 lasers라는 2차원 배열에 담습니다.
- lasers에 담긴 두 위치 중 한 위치를 시작 지점으로 잡고 다른 한 위치를 종료 지점으로 잡아 BFS 탐색을 실행합니다.
- PriorityQueue를 생성하여 시작 위치를 Loc 객체로 만들어 넣고, 각 위치에서 사용한 거울의 개수의 최솟값을 담는 2차원 배열 visited를 생성하고 모든 값을 INF로 초기화시킵니다.
- PriorityQueue가 비워질 때까지 BFS 탐색을 진행하여 답을 구합니다.
- PriorityQueue에서 Loc 객체 하나를 뽑고 해당 위치가 종료 지점의 위치에 있는지 확인합니다. 만약 그렇다면 뽑은 Loc 객체의 mirrorNum이 정답이 됩니다.
- 만약 그렇지 않다면 뽑은 Loc 객체의 상하좌우 위치를 확인하고 이후에 그 위치들을 탐색할지 결정합니다.
- 만약 해당 위치가 지도 내에 위치하고 벽이 아니라면 다음 2가지를 확인하여 이후 BFS 탐색 시에 해당 위치를 탐색할지 확인합니다.
- 현재 레이저의 방향으로 이동한 경우 혹은 시작점에서 시작하는 경우
- 해당 위치의 visited 값이 현재 사용한 거울의 개수보다 크거나 같은지 확인하고 만약 그렇다면 해당 위치의 visited 값을 현재 사용한 거울의 개수로 변경하고 PriorityQueue에 해당 위치를 이후 탐색하기 위해 Loc 객체로 변경하여 넣습니다.
- 현재 레이저의 방향으로 이동했기 때문에 거울을 사용할 이유가 없어 현재 사용한 거울의 개수를 기준으로 비교하였습니다.
- 현재 레이저의 방향이 아닌 곳으로 이동하는 경우
- 해당 위치의 visited 값이 (현재 사용한 거울의 개수 + 1)보다 크거나 같은지 확인하고 만약 그렇다면 해당 위치의 visited 값을 (현재 사용한 거울의 개수 + 1)로 변경하고 PriorityQueue에 해당 위치를 이후 탐색하기 위해 Loc 객체로 변경하여 넣습니다.
- 현재 레이저의 방향과 다른 곳으로 이동했기 때문에 거울을 사용해야만 하므로 (현재 사용한 거울의 개수 + 1)을 기준으로 비교하였습니다.
자바, 웹 개발을 열심히 공부하고 있습니다!