백준 6087번 : 레이저 통신 [Java]
Algorithm/백준
6087번: 레이저 통신
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서
www.acmicpc.net
전형적인 백트래킹 문제다.
문제의 요점은 탐색 + 백트래킹 장치를 거는 것이다.
여기서 백트래킹 장치라는 것은 레이저를 회전시키는 최소 횟수를 구하는 것이니, 회전이라는 것은 탐색하면서 방향을 트는 횟수가 최소가 되게 하면 된다는 것이다.
따라서 주어진 지도와 같은 크기의 turnCnt 배열을 생성한다.
탐색하는 과정에서 특정 위치 x, y에 도착하였을때 지금까지 방향을 몇 번 틀었나 체크를 해주게 되고, 이 방향 튼 횟수를 turnCnt[x][y]에 기록하면 된다.
글로 보면 이해가 안될것이다. 예제를 하나 들어보자.
예를 들어 아래와 같은 입력이 주어진다고 하자.
4 4
C.**
..**
....
...C
그리고 turnCnt 배열의 초기값은 최대값으로 해준다.
| INT_MAX | INT_MAX | INT_MAX | INT_MAX |
| INT_MAX | INT_MAX | INT_MAX | INT_MAX |
| INT_MAX | INT_MAX | INT_MAX | INT_MAX |
| INT_MAX | INT_MAX | INT_MAX | INT_MAX |
시작 위치는 왼쪽 상단 C 위치인 (0, 0) 부터 시작하여 도착 위치인 (3, 3)으로 이동하면서 체크해야 할 부분은 다음과 같다.
1, 4방향 탐색을 진행한다.
2. 다음 좌표에까지 방향 전환 횟수가 지금까지 오면서 꺽은 횟수보다 많거나 같으면 갱신하면서 재 탐색해준다.
3. 그렇지 않으면 이전으로 가서 다시 탐색한다.
[0, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[0, 1, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[0, 1, 2147483647, 2147483647]
[2147483647, 2, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 2147483647, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 2147483647, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 2147483647]
[2147483647, 2147483647, 2147483647, 2147483647]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[2147483647, 2147483647, 2147483647, 2147483647]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[2147483647, 2147483647, 2147483647, 6]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[2147483647, 2147483647, 6, 6]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[2147483647, 7, 6, 6]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[7, 7, 6, 6]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[7, 6, 6, 6]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[7, 6, 6, 6]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[4, 6, 6, 6]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[4, 5, 6, 6]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[4, 5, 5, 6]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 5, 5, 5]
[4, 5, 5, 5]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[4, 2, 5, 5]
[4, 5, 5, 5]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 5, 5]
[4, 5, 5, 5]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 5]
[4, 5, 5, 5]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 5, 5, 5]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 5, 5, 4]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 5, 4, 4]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 5, 4, 4]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[4, 2, 4, 4]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 4, 4]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 3, 4]
[0, 1, 2147483647, 2147483647]
[3, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[3, 2, 3, 3]
[3, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 3, 3]
[3, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 3, 3]
[3, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 3]
[3, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[3, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[3, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[3, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[1, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[1, 2, 3, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[1, 2, 2, 3]
[0, 1, 2147483647, 2147483647]
[1, 2, 2147483647, 2147483647]
[1, 2, 2, 2]
[1, 2, 2, 2]계속해서 백트래킹해주면서 탐색해주면 목적지에 최소 회전 값이 갱신되어 있을 것이다.
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st = null;
static final char EMPTY = '.';
static final char WALL = '*';
static final char C = 'C';
static final int START = 0;
static final int END = 1;
static int w, h, idx;
static char[][] map;
static Point[] p;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
p = new Point[2];
map = new char[h][w];
visited = new boolean[h][w];
turnCnt = new int[h][w];
idx = 0;
for (int i = 0; i < h; i++) {
String line = br.readLine();
for (int j = 0; j < w; j++) {
map[i][j] = line.charAt(j);
if (map[i][j] == C) {
p[idx++] = new Point(i, j);
}
}
Arrays.fill(turnCnt[i], Integer.MAX_VALUE);
}
min = Integer.MAX_VALUE;
visited[p[START].x][p[START].y] = true;
dfs(p[START].x, p[START].y,-1, 0);
System.out.println(turnCnt[p[END].x][p[END].y] - 1);
}
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
static boolean[][] visited;
static int[][] turnCnt;
static int min;
private static void printMap(int[][] map)
{
for (int i=0; i<map.length; i++){
System.out.println(Arrays.toString(map[i]));
}
System.out.println();
}
private static void dfs(int x, int y, int exDir, int turn) {
if (x == p[END].x && y == p[END].y) {
turnCnt[x][y] = turn;
return;
}
turnCnt[x][y] = turn;
// printMap(turnCnt);
for (int dir = 0; dir < 4; dir++) {
int nx, ny;
nx = x + dx[dir];
ny = y + dy[dir];
if (0 <= nx && nx < h && 0 <= ny && ny < w && !visited[nx][ny]
&& map[nx][ny] != WALL)
{
// System.out.println(nx+" "+ny);
// System.out.println("dir : "+dir +" exDir : "+exDir+" turn : "+turn+" turnCnt[nx][ny] : "+turnCnt[nx][ny]);
visited[nx][ny] = true;
if (dir == exDir)
{
if (turnCnt[nx][ny] >= turn)
{
dfs(nx, ny, dir, turn);
}
}
else
{
if (turnCnt[nx][ny] >= turn + 1)
{
dfs(nx, ny, dir, turn + 1);
}
}
visited[nx][ny] = false;
}
}
}
public static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
'Algorithm > 백준' 카테고리의 다른 글
| 백준 11066번 : 파일 합치기 [Java] (0) | 2020.12.10 |
|---|---|
| 백준 6549번 : 히스토그램에서 가장 큰 직사각형 [Java] (0) | 2020.12.09 |
| 백준 9376번 : 탈옥 [Java] (0) | 2020.12.07 |
| 백준 10830번 : 행렬 제곱 with Java (0) | 2020.12.02 |
| 백준1655번 : 가운데를 말해요 [java] (0) | 2020.11.30 |