[백준 6087]https://www.acmicpc.net/problem/6087
테스트케이스가 허술해서 맞았던 문제이다. 저격 테케가 추가되어 처음부터 다시 풀어봤다.
문제 조건
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.
'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.
레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.
초기 상태 최소 거울로 연결한 상태
7 . . . . . . . 7 . . . . . . .
6 . . . . . . C 6 . . . . . /-C
5 . . . . . . * 5 . . . . . | *
4 * * * * * . * 4 * * * * * | *
3 . . . . * . . 3 . . . . * | .
2 . . . . * . . 2 . . . . * | .
1 . C . . * . . 1 . C . . * | .
0 . . . . . . . 0 . \-------/ .
0 1 2 3 4 5 6 0 1 2 3 4 5 6문제 입력
첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)
둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.
. : 빈 칸
* : 벽
C : 레이저로 연결해야 하는 칸
'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.
문제 풀기 전 설계
출발 지점과 목표 지점을 저장하고 출발 지점에서부터 방문 여부를 거울의 개수로 하여 저장하면서 목표 지점에 도달하면 최소 거울의 개수인지 비교하면 될 것이다.
문제 코드
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_6087 {
static int w, h;
static char[][] map;
static Node[] target = new Node[2];
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, -1, 0, 1};
static class Node implements Comparable<Node> {
int x, y, dir, mirrors;
public Node(int x, int y, int dir, int mirrors) {
this.x = x;
this.y = y;
this.dir = dir;
this.mirrors = mirrors;
}
@Override
public int compareTo(Node o) {
return this.mirrors - o.mirrors;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new char[h][w];
for (int i = 0, idx = 0; i < h; i++) {
String s = br.readLine();
map[i] = s.toCharArray();
for (int j = 0; j < w; j++) {
if (map[i][j] == 'C') target[idx++] = new Node(i, j, -5, -1);
}
}
System.out.println(bfs(target[0]));
}
private static int bfs(Node start) {
int min = Integer.MAX_VALUE;
Node goal = target[1];
PriorityQueue<Node> q = new PriorityQueue<>();
int[][][] visited = new int[4][h][w];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < h; j++) {
Arrays.fill(visited[i][j], Integer.MAX_VALUE);
}
}
q.offer(start);
while (!q.isEmpty()) {
Node now = q.poll();
if (now.x == goal.x && now.y == goal.y) {
min = Math.min(min, now.mirrors);
continue;
}
for (int i = 0; i < 4; i++) {
int nextX = now.x + dx[i];
int nextY = now.y + dy[i];
int nextMirrors = (now.dir == i) ? now.mirrors : now.mirrors + 1;
if (!isInRange(nextX, nextY) || map[nextX][nextY] == '*' || Math.abs(now.dir - i) == 2) continue;
if (visited[i][nextX][nextY] > nextMirrors) {
q.offer(new Node(nextX, nextY, i, nextMirrors));
visited[i][nextX][nextY] = nextMirrors;
}
}
}
return min;
}
private static boolean isInRange(int x, int y) {
return x >= 0 && x < h && y >= 0 && y < w;
}
}문제 풀이
설계대로 문제가 잘 풀리지 않아서 무엇을 빼먹었을까 생각해봤는데, 어떤 칸에 도달할 때 레이저의 방향도 중요했다. 만약 어떤 칸 A(x, y)에서 왼쪽 칸 B(x, y - 1)로 이동한다고 가정하면,
이전 레이저의 방향(A에 들어오는 레이저의 방향)
- 왼쪽을 바라봄 = 거울 필요 없음
- 위 / 아래를 바라봄 = 거울 1개 추가
- 오른쪽을 바라봄 = 이동 불가능 (또는 고려할 필요 없음)
위의 세 가지 경우로 나뉘게 된다. 따라서 방문 여부를 관리하는 visited 배열을 x좌표, y좌표 그리고 레이저의 방향을 저장하도록 3차원 배열을 사용해야 한다.
이것이 해결되고 나면 문제 자체는 다른 BFS 문제처럼 풀면 된다. 조금 다른 점은 방문 처리를 할 때 이미 방문한 점이더라도 새로 방문하는 경우의 거울 사용 횟수가 더 적다면 배열 값을 갱신하고 다시 큐에 넣는다는 것이다.
2023-02-05 bfs 방식 개선(일반 큐 -> 우선순위 큐)
Review
재채점 결과를 보면 저격당한 풀이가 나 외에도 굉장히 많다 ㅋㅋ
알고리즘 문제 풀이에 있어서 불필요한 반복을 줄이는 건 중요하지만, 그렇다고 고려해야 하는 점을 빼먹으면 안된다는 걸 몸소 배운 문제였다.
