문제
해결 방법
빛은 일직선으로 나아가고, 45도 각도의 거울을 사용해서 이동방향을 바꿔 목적지에 도착하도록 하는 문제이다.
그래서 현재 방향이 어디인지 저장할 dir을 사용하고, cnt를 사용해서 거울을 몇 번 사용했는지 체크하게끔 class를 구성했다.또 우선순위 큐를 사용해서 가장 거울을 적게 사용한 결괏값이 제일 먼저 목적지에 도착하도록 하였다.
시작점과 도착점이 문제와 같이 2개만 주어지는 문제는 처음 입력을 받을 때 해당 지점을 체크해두고 푸는 방식을 자주 사용했다.위 문제에서 보면 시작점과 도착점을 '#'으로 표시하는데 입력을 받을 때 '#'의 지점을 startX, startY에 저장해둔 뒤남은 '#' 을 찾아가는 방향으로 푸는 방식이다.그래서 startX, startY 지점은 '.'으로 추후에 초기화를 시켜 map 배열에 '#'이 하나만 존재하게 만들었다.
방문 배열은 4방향에 따라 체크를 하기 위해 3차원 배열을 사용했고,시작점은 모든 방향에서 모두 true로 해서 방문 설정을 하였다.
또 처음 시작하는 곳에서 어느 방향으로 빛이 나아갈 수 있는지 체크해야 하기 때문에,첫 시작점의 방향을 상관없는 숫자인 4로 지정해두고, 가능한 방향을 체크한 뒤에 배열에 먼저 넣어주었다.
그 뒤엔 거울을 만난다면, 현재 진행 방향이 좌우라면 상하로 바꾸어서 나아가게끔하고, 그 반대라면 반대의 경우를 설정하고
거울을 세울 수 있는 위치에 거울을 세우지 않고 그냥 진행되게 할 수도 있기 때문에 이와 같은 경우도 추가해주었다.
코드에 부분마다 주석을 달아두었다.좀 더 짧게 코드를 짤 수 있을 것 같긴한데, 길게 풀어놓은 코드가 이해는 더 쉽지 않을까 해서 첨부한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Main {
static char[][] map;
static boolean[][][] visit;
static int N;
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new char[N][N];
visit = new boolean[N][N][4];
int startX = 0, startY = 0;
for (int i = 0; i < N; i++) {
String temp = br.readLine();
for (int j = 0; j < temp.length(); j++) {
map[i][j] = temp.charAt(j);
if (map[i][j] == '#') {
startX = i;
startY = j;
}
}
}
map[startX][startY] = '.';
bfs(startX, startY);
}
static void bfs(int startX, int startY) {
PriorityQueue<Node> q = new PriorityQueue<>();
q.offer(new Node(startX, startY, 4, 0));
for (int i = 0; i < 4; i++) {
// 시작점 모든 방향으로 방문완료 처리
visit[startX][startY][i] = true;
}
while (!q.isEmpty()) {
Node node = q.poll();
// 목적지를 만나면 값 출력 후 종료
if (map[node.x][node.y] == '#') {
System.out.println(node.cnt);
return;
}
if (node.dir == 4) {
// 시작점에서 갈 수 있는 방향 찾기
for (int i = 0; i < 4; i++) {
int newX = node.x + dx[i];
int newY = node.y + dy[i];
if (!checkRange(newX, newY)) continue;
if (map[newX][newY] != '*') {
q.offer(new Node(newX, newY, i, node.cnt));
visit[newX][newY][i] = true;
}
}
// 시작점이 아닌 경우
} else {
if (map[node.x][node.y] == '!') {
if (node.dir == 0 || node.dir == 1) { // 좌우로 움직이는 중이면
for (int i = 2; i < 4; i++) {
// 거울을 세워 위 아래로 움직이는 경우
int newX = node.x + dx[i];
int newY = node.y + dy[i];
if (!checkRange(newX, newY)) continue;
if (map[newX][newY] != '*' && !visit[newX][newY][i]) {
q.offer(new Node(newX, newY, i, node.cnt + 1));
visit[newX][newY][i] = true;
}
}
}
if (node.dir == 2 || node.dir == 3) { // 위 아래로 움직이는 중이면
for (int i = 0; i < 2; i++) {
// 거울을 세워 좌우로 움직이는 경우
int newX = node.x + dx[i];
int newY = node.y + dy[i];
if (!checkRange(newX, newY)) continue;
if (map[newX][newY] != '*' && !visit[newX][newY][i]) {
q.offer(new Node(newX, newY, i, node.cnt + 1));
visit[newX][newY][i] = true;
}
}
}
}
// 거울을 세우지 않고 진행되는 경우
int newX = node.x + dx[node.dir];
int newY = node.y + dy[node.dir];
if (!checkRange(newX, newY)) continue;
if (map[newX][newY] != '*' && !visit[newX][newY][node.dir]) {
q.offer(new Node(newX, newY, node.dir, node.cnt));
visit[newX][newY][node.dir] = true;
}
}
}
}
static boolean checkRange(int x, int y) {
return x >= 0 && y >= 0 && x < N && y < N;
}
}
class Node implements Comparable<Node>{
int x;
int y;
int dir;
int cnt;
Node (int x, int y, int dir, int cnt) {
this.x = x;
this.y = y;
this.dir = dir;
this.cnt = cnt;
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
return cnt - o.cnt;
}
}
'Algorithm > BaekJoon' 카테고리의 다른 글
[JAVA] 백준 13913 : 숨바꼭질 4 (0) | 2021.07.07 |
---|---|
[JAVA] 백준 16946 : 벽 부수고 이동하기 4 (0) | 2021.06.02 |
[JAVA] 백준 11657 : 타임머신 (0) | 2021.05.04 |
[JAVA] 백준 1240 : 노드사이의 거리 (0) | 2021.04.23 |
[JAVA] 백준 8972 : 미친 아두이노 (0) | 2021.04.21 |