[백준 - Java] 6087번 : 레이저 통신

문제

www.acmicpc.net/problem/6087

6087번: 레이저 통신

설명

2020 카카오 인턴십 문제로 나왔던 경주로 건설과 비슷한 문제이다.

 

자세한 설명은 경주로 건설 포스팅을 참고해주세요.

 

[프로그래머스 - Java] 경주로 건설 (2020 카카오 인턴십)

 

경주로 건설은 직선, 코너 도로마다 비용이 부과되는데 둘을 적절히 사용해 가장 적은 비용으로 경주로를 건설해야 한다.

레이저 통신도 마찬가지이다. 

레이저를 쏘는데 거울을 가장 적게 쓰는 방법으로 C에서 다른 C까지의 경로를 만들어야 한다.

 

즉 경주로 건설에서 직선 코스에서 요금을 부과하는 것을 빼고, 코너 도로일 때 +1씩 추가해 총 몇 개의 거울을 설치했는지 구하면 된다.

코너 도로라는 것이 바로 거울을 설치할 지점이다.

왜냐하면 거울은 레이저가 쏴지는 원래 방향에서 다른 방향으로 꺾일 때 사용되기 때문이다.

 

bfs를 수행하면서 최단거리를 찾되, 이미 갔던 지점이라도 설치되는 거울의 수가 적다면 다시 갈 수 있도록 구현해야 한다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static Point startPoint, endPoint;
	static int W, H;
	static int min = Integer.MAX_VALUE;
	static char[][] map;
	static int[][] visited;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};

	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; i < H; i++) {
			String str = br.readLine();
			for(int j = 0; j < W; j++) {
				map[i][j] = str.charAt(j);

				if(map[i][j] == 'C') {
					if(startPoint == null)
						startPoint = new Point(i, j, -1, 0);
					else 
						endPoint = new Point(i, j, -1, 0);
				}
			}
		}

		bfs();

		System.out.println(min);
	}

	public static void bfs() {
		Queue<Point> queue = new LinkedList<>();
		queue.add(startPoint);

		visited = new int[H][W];
		visited[startPoint.x][startPoint.y] = 1;

		while(!queue.isEmpty()) {
			int cx = queue.peek().x;
			int cy = queue.peek().y;
			int cd = queue.peek().dir;
			int cm = queue.poll().mirror;

			if(cx == endPoint.x && cy == endPoint.y) {
				min = Math.min(min, cm);
				continue;
			}

			for(int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				int nd = i;

				if(nx < 0 || nx >= H || ny < 0 || ny >= W || map[nx][ny] == '*')
					continue;

				int nm = cm; // 새로운 거울 개수 저장할 변수 (꺾이면 +1 됨)

				// 처음 시작이 아니고, 뱡향이 다른 경우 -> 꺾임 -> 거울 설치해야 함
				if(cd != -1 && cd != nd) { 
					nm += 1; // 꺽임 
				}

				if(visited[nx][ny] == 0) { // 방문하지 않은 경우 
					visited[nx][ny] = nm; // 구해진 거울 값으로 초기화 
					queue.add(new Point(nx, ny, nd, nm));
				} else if(visited[nx][ny] >= nm) { 
					// 이미 방문한 곳이지만 새롭게 구해진 거울 개수가 더 작은 경우 
					visited[nx][ny] = nm; // 새롭게 구해진 값으로 변경 
					queue.add(new Point(nx, ny, nd, nm)); // 다시 그 곳부터 bfs를 위해 큐에 넣어줌 
				}
			}
		}
	}

}

class Point {
	int x;
	int y;
	int dir; // 레이저의 현재 방향 
	int mirror; // 현재 위치까지 설치된 거울의 개수 

	Point(int x, int y, int dir, int mirror) {
		this.x = x;
		this.y = y;
		this.dir = dir;
		this.mirror = mirror;
	}
}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%236087/src/Main.java