https://www.acmicpc.net/problem/13459
1. 아이디어
BFS를 통한 시뮬레이션으로 해결할 수 있다.
2. 문제풀이
빨간 구슬, 파란 구슬, 구멍의 위치를 Point 객체에 담아서 관리했다. 객체에 대한 시뮬레이션이라 원본이 변경되지 않는게 중요하다고 생각해서 깊은 복사를 하기도 쉽고 직관적이어서 활용했다.
BFS는 Queue에는 빨간 구슬, 파란 구슬을 같이 담고 같이 빼는 방식으로 구현했고 방문 체크는 4차원 배열로 빨간 구슬의 위치와 파란 구슬의 위치를 같이 기록했다. 빨간 구슬의 위치가 일정해도 파란 구슬의 위치가 달라지면 다른 상황이라 같이 기록해야한다.
Queue가 빌 때까지 BFS를 진행하는데 두 구슬을 같이 넣었으니 같이 빼서 다루고 빨간 구슬이 구멍에 위치하고 파란 구슬이 구멍이 아닌 곳에 위치하면 1을 반환했다. 두 구슬을 빼니 Queue 크기의 절반만큼 반복해야한다.
move는 상하좌우 기울이는 방향과 보드, 두 구슬의 위치로 이동 후 다음 구슬들의 위치를 반환하는데 이를 통해 다음 구슬의 위치를 Queue에 넣고 방문 체크를 한다. 이때 깊은 복사로 새 객체를 넣어줘야 각 상하좌우에 대한 시뮬레이션이 독립적으로 돌아간다. isSamePosition은 객체의 equals랑 같은 역할을 하게 구현했다.
move는 두 구슬의 위치관계에 따라 이동시키는 것으로 위로 기울였을 때 더 위에 있는 구슬이 먼저 이동해야한다거나 하는 상황이 있어서 조건 분기가 됐고 각 구슬은 구멍에 위치하면 더 이동시키지 않았다.
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 1;
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++;
if (dist > 10) return 0;
}
return 0;
}
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. 후기
'코딩테스트 준비 > 백준' 카테고리의 다른 글
| [백준] 15644번 - 구슬 탈출 3 [Java] (0) | 2025.01.17 |
|---|---|
| [백준] 13460번 - 구슬 탈출 2 [Java] (0) | 2025.01.17 |
| [백준] 1926번 - 그림 [Java] (0) | 2025.01.17 |
| [백준] 2667번 - 단지번호붙이기 [Java] (0) | 2025.01.17 |
| [백준] 2606번 - 바이러스 [Java] (0) | 2025.01.17 |
