[JAVA] 백준 6087 : 레이저 통신

문제

6087번: 레이저 통신

해결 방법

C에서 C로 길을 찾는데 방향을 바꾸기 위해서는 거울을 사용한다.

사용할 거울을 최소로 하는 길을 찾는 문제이다.

 

보자마자 우선순위 큐를 활용해서 최단 거리를 구하면 되지 않을까 생각하고 구현해보았다.

중간에 visit 배열의 조건을 부여하는 부분에서 제가 짠 코드보다 아래 블로그의 코드가 쉽고 보기 좋아서 참고해서 수정하였다.

 

참고한 블로그 -> velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%806087-%EB%A0%88%EC%9D%B4%EC%A0%80-%ED%86%B5%EC%8B%A0

 

C가 시작 지점이자 끝지점이 되기 때문에 C의 좌표를 startX, startY를 통해 입력해주었고 탐색에 들어가기 전에 .으로 바꾸어주어 맵에 남겨져 있는 C를 하나만 두어 찾아가도록 구성하였다.

그리고 Node 클래스에 좌표뿐만 아니라 방향과 현재까지 사용한 거울 수(즉, 방향이 전환된 횟수)를 입력할 수 있게 설정했다.

 

탐색은 visit배열을 사용하는데 visit 배열은 각 칸까지 도달한 탐색이 거울을 몇 개를 사용했는지 나타내고 있으며, 만약 현재 탐색 중인 값이 이미 탐색하고 지나간 사용한 거울의 숫자보다 크다면 재탐색해서 더 적게 거울을 사용한 탐색의 값이 들어가게 된다.

쉽게 이야기하면 1번 째 탐색이 거울을 두번 사용해서 (2, 2)를 지나갔는데 2번 째 탐색이 거울을 한 번 사용해서 (2, 2)를 지나갈 수 있다면 값을 바꿔주고 다시 탐색을 하는 것이다.

 

그렇게 탐색 후에 목표 지점에 도착하면 값을 반환해준다.

우선순위 큐를 사용했기 때문에 처음 도착한 값이 가장 작은 값이 된다.

설명을 하지않은 부분은 코드에 주석을 달아 두었다.

 

최적의 코드는 아니지만 내가 아는 선에서는 최적인 것 같다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};
	
	static int W, H;
	static char[][] map;
	static int[][] visit;
	
	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];
		visit = new int[H][W];
		int startX = 0;
		int startY = 0;
		
		for (int i = 0; i < H; i++) {
			String input = br.readLine();
			for (int j = 0; j < W; j++) {
				map[i][j] = input.charAt(j);
				if (map[i][j] == 'C') {
					startX = i;
					startY = j;
				}
			}
		}
		for (int i = 0; i < H; i++) {
			Arrays.fill(visit[i], Integer.MAX_VALUE);
			// 최대 값으로 초기화
		}
		
		map[startX][startY] = '.';
		bfs(startX, startY);
	}
	
	static void bfs(int x, int y) {
		Queue<Node> q = new PriorityQueue<>();
		q.offer(new Node(x, y, 5, -1)); 
		// 초기값은 방향을 다르게 주고 거울 수를 -1로 시작함.
		visit[x][y] = 0;
		
		while (!q.isEmpty()) {
			Node node = q.poll();
			
			if (map[node.x][node.y] == 'C') {
				System.out.println(node.mirror);
				return;
			}
			
			for (int i = 0; i < 4; i++) {
				int newX = node.x + dx[i];
				int newY = node.y + dy[i];
				
				if (newX < 0 || newY < 0 || newX >= H || newY >= W) continue;
				if (map[newX][newY] == '*') continue;
				// * 이거나 범위에 맞지 않으면 넘김.
				
				int temp = node.mirror;
				if (node.direction != i) temp++; // 방향이 전과 다르다면 1 더해줌
				if (visit[newX][newY] < temp) continue;
				
				visit[newX][newY] = temp;
				q.offer(new Node(newX, newY, i, temp));
			}
		}
	}
}

class Node implements Comparable<Node>{
	int x;
	int y;
	int direction;
	int mirror;
	
	Node (int x, int y, int direction, int mirror) {
		this.x = x;
		this.y = y;
		this.direction = direction;
		this.mirror = mirror;
	}

	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return mirror - o.mirror;
	}
}