https://www.acmicpc.net/problem/15653
1. 아이디어
기존 구슬 탈출 2 문제에서 이제 구슬이 탈출할 수 있을 때까지 시도하고 불가능한 경우면 -1을 출력하는 문제로 dist가 10 초과면 -1d을 출력하던 조건만 없애면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 13460번 - 구슬 탈출 2 [Java])
2. 문제풀이
아이디어 그대로 해당 라인만 수정했다.
3. 코드
import java.io.*;
import java.util.*;
public class Main {
private static final char[] order = {'U', 'D', 'L', 'R'};
private static class Point {
int r;
int c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
public Point(Point p) {
this.r = p.r;
this.c = p.c;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
Point red = null;
Point blue = null;
Point exit = null;
char[][] map = new char[N][M];
for (int i = 0; i < N; i++) {
map[i] = br.readLine().toCharArray();
for (int j = 0; j < M; j++) {
if (map[i][j] == 'R') red = new Point(i, j);
else if (map[i][j] == 'B') blue = new Point(i, j);
else if (map[i][j] == 'O') exit = new Point(i, j);
}
}
int dist = bfs(red, blue, exit, N, M, map);
System.out.println(dist);
}
private static int bfs(Point startRed, Point startBlue, Point exit, int N, int M, char[][] map) {
Queue<Point> q = new ArrayDeque<>();
q.offer(startRed);
q.offer(startBlue);
boolean[][][][] visited = new boolean[N][M][N][M];
visited[startRed.r][startRed.c][startBlue.r][startBlue.c] = true;
int dist = 0;
while (!q.isEmpty()) {
int len = q.size();
for (int i = 0; i < len / 2; i++) {
Point red = q.poll();
Point blue = q.poll();
if (isSamePosition(red, exit) && !isSamePosition(blue, exit)) return dist;
for (int dir = 0; dir < 4; dir++) {
Point[] points = move(order[dir], map, new Point(red), new Point(blue));
int redNr = points[0].r;
int redNc = points[0].c;
int blueNr = points[1].r;
int blueNc = points[1].c;
if (visited[redNr][redNc][blueNr][blueNc]) continue;
q.offer(new Point(redNr, redNc));
q.offer(new Point(blueNr, blueNc));
visited[redNr][redNc][blueNr][blueNc] = true;
}
}
dist++;
}
return -1;
}
private static boolean isSamePosition(Point p1, Point p2) {
return p1.r == p2.r && p1.c == p2.c;
}
// 두 구슬의 위치관계를 기반으로 order에 대한 이동을 수행하고 최종 위치를 반환하는 메서드
private static Point[] move(char order, char[][] map, Point red, Point blue) {
if (order == 'U') {
if (red.c == blue.c) {
if (red.r < blue.r) {
while (map[red.r - 1][red.c] != '#' && map[red.r][red.c] != 'O') {
red.r--;
}
while (map[blue.r - 1][blue.c] != '#' && map[blue.r][blue.c] != 'O' && (map[red.r][red.c] == 'O' || blue.r - 1 != red.r)) {
blue.r--;
}
} else {
while (map[blue.r - 1][blue.c] != '#' && map[blue.r][blue.c] != 'O') {
blue.r--;
}
while (map[red.r - 1][red.c] != '#' && map[red.r][red.c] != 'O' && (map[blue.r][blue.c] == 'O' || red.r - 1 != blue.r)) {
red.r--;
}
}
} else {
while (map[red.r - 1][red.c] != '#' && map[red.r][red.c] != 'O') {
red.r--;
}
while (map[blue.r - 1][blue.c] != '#' && map[blue.r][blue.c] != 'O') {
blue.r--;
}
}
} else if (order == 'D') {
if (red.c == blue.c) {
if (red.r > blue.r) {
while (map[red.r + 1][red.c] != '#' && map[red.r][red.c] != 'O') {
red.r++;
}
while (map[blue.r + 1][blue.c] != '#' && map[blue.r][blue.c] != 'O' && (map[red.r][red.c] == 'O' || blue.r + 1 != red.r)) {
blue.r++;
}
} else {
while (map[blue.r + 1][blue.c] != '#' && map[blue.r][blue.c] != 'O') {
blue.r++;
}
while (map[red.r + 1][red.c] != '#' && map[red.r][red.c] != 'O' && (map[blue.r][blue.c] == 'O' || red.r + 1 != blue.r)) {
red.r++;
}
}
} else {
while (map[red.r + 1][red.c] != '#' && map[red.r][red.c] != 'O') {
red.r++;
}
while (map[blue.r + 1][blue.c] != '#' && map[blue.r][blue.c] != 'O') {
blue.r++;
}
}
} else if (order == 'L') {
if (red.r == blue.r) {
if (red.c < blue.c) {
while (map[red.r][red.c - 1] != '#' && map[red.r][red.c] != 'O') {
red.c--;
}
while (map[blue.r][blue.c - 1] != '#' && map[blue.r][blue.c] != 'O' && (map[red.r][red.c] == 'O' || blue.c - 1 != red.c)) {
blue.c--;
}
} else {
while (map[blue.r][blue.c - 1] != '#' && map[blue.r][blue.c] != 'O') {
blue.c--;
}
while (map[red.r][red.c - 1] != '#' && map[red.r][red.c] != 'O' && (map[blue.r][blue.c] == 'O' || red.c - 1 != blue.c)) {
red.c--;
}
}
} else {
while (map[red.r][red.c - 1] != '#' && map[red.r][red.c] != 'O') {
red.c--;
}
while (map[blue.r][blue.c - 1] != '#' && map[blue.r][blue.c] != 'O') {
blue.c--;
}
}
} else if (order == 'R') {
if (red.r == blue.r) {
if (red.c > blue.c) {
while (map[red.r][red.c + 1] != '#' && map[red.r][red.c] != 'O') {
red.c++;
}
while (map[blue.r][blue.c + 1] != '#' && map[blue.r][blue.c] != 'O' && (map[red.r][red.c] == 'O' || blue.c + 1 != red.c)) {
blue.c++;
}
} else {
while (map[blue.r][blue.c + 1] != '#' && map[blue.r][blue.c] != 'O') {
blue.c++;
}
while (map[red.r][red.c + 1] != '#' && map[red.r][red.c] != 'O' && (map[blue.r][blue.c] == 'O' || red.c + 1 != blue.c)) {
red.c++;
}
}
} else {
while (map[red.r][red.c + 1] != '#' && map[red.r][red.c] != 'O') {
red.c++;
}
while (map[blue.r][blue.c + 1] != '#' && map[blue.r][blue.c] != 'O') {
blue.c++;
}
}
}
return new Point[]{red, blue};
}
}4. 후기
'코딩테스트 준비 > 백준' 카테고리의 다른 글
| [백준] 1302번 - 베스트셀러 [Java] (0) | 2025.01.20 |
|---|---|
| [백준] 10821번 - 정수의 개수 [Java] (0) | 2025.01.20 |
| [백준] 15644번 - 구슬 탈출 3 [Java] (0) | 2025.01.17 |
| [백준] 13460번 - 구슬 탈출 2 [Java] (0) | 2025.01.17 |
| [백준] 13459번 - 구슬 탈출 [Java] (0) | 2025.01.17 |
