문제
내가 생각했을때 문제에서 원하는부분
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다.
다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다.
이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다.
'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다.
구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다.
만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.내가 이 문제를 보고 생각해본 부분
State 클래스: 빨간 구슬과 파란 구슬의 위치(rx, ry, bx, by)와 현재 움직임 횟수(depth)를 저장한다.
move 함수: 한 구슬을 주어진 방향으로 가능한 한 멀리 보드의 벽이나 구멍까지 움직인다.
움직인 후 좌표와 몇 칸 이동했는지 반환한다.
bfs 함수:
상태 공간을 큐에 넣고 BFS 탐색 시작한다.
방문 여부는 빨간 구슬과 파란 구슬의 위치 조합으로 기록한다.
각 단계마다 4가지 방향으로 구슬을 움직여 새로운 상태를 만든다.
파란 구슬이 구멍에 빠진 상태는 무시한다.
빨간 구슬과 파란 구슬이 겹치면, 더 많이 이동한 구슬을 한 칸 뒤로 옮겨 겹치지 않게 조정한다.
빨간 구슬이 구멍에 빠지면 현재 움직임 횟수를 반환한다.
10회 이상 움직이면 -1 반환한다.
main 함수에서 입력을 읽고, 초기 구슬 위치를 찾은 후 BFS를 호출하여 결과를 출력한다.코드로 구현
package baekjoon.baekjoon_33;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// 백준 13460번 문제
public class Main1323 {
static int N, M;
static char[][] board;
static boolean[][][][] visited;
// 빨강과 파랑 구슬 위치를 가지는 상태 클래스
static class State {
int rx, ry, bx, by, depth;
State(int rx, int ry, int bx, int by, int depth) {
this.rx = rx; this.ry = ry; this.bx = bx; this.by = by; this.depth = depth;
}
}
// 상, 하, 좌, 우
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
// 구슬 하나를 한 방향으로 이동시키고, 이동한 칸 수를 반환하는 함수
static int[] move(int x, int y, int dir) {
int count = 0;
while (true) {
if (board[x + dx[dir]][y + dy[dir]] == '#')
break;
x += dx[dir];
y += dy[dir];
count++;
if (board[x][y] == 'O')
break;
}
return new int[] {x, y, count};
}
static int bfs(int rx, int ry, int bx, int by) {
Queue<State> queue = new LinkedList<>();
queue.add(new State(rx, ry, bx, by, 0));
visited = new boolean[N][M][N][M];
visited[rx][ry][bx][by] = true;
while (!queue.isEmpty()) {
State cur = queue.poll();
if (cur.depth > 10)
break;
if (board[cur.rx][cur.ry] == 'O') {
return cur.depth;
}
for (int dir = 0; dir < 4; dir++) {
int[] nRed = move(cur.rx, cur.ry, dir);
int[] nBlue = move(cur.bx, cur.by, dir);
// 파란 구슬이 구멍에 빠지면 실패 경로
if (board[nBlue[0]][nBlue[1]] == 'O')
continue;
// 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우 위치 조정
if (nRed[0] == nBlue[0] && nRed[1] == nBlue[1]) {
if (nRed[2] > nBlue[2]) { // 더 많이 움직인 쪽을 뒤로
nRed[0] -= dx[dir];
nRed[1] -= dy[dir];
} else {
nBlue[0] -= dx[dir];
nBlue[1] -= dy[dir];
}
}
if (!visited[nRed[0]][nRed[1]][nBlue[0]][nBlue[1]]) {
visited[nRed[0]][nRed[1]][nBlue[0]][nBlue[1]] = true;
queue.add(new State(nRed[0], nRed[1], nBlue[0], nBlue[1], cur.depth + 1));
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new char[N][M];
int redX = 0, redY = 0, blueX = 0, blueY = 0;
for (int i = 0; i < N; i++) {
board[i] = br.readLine().toCharArray();
for (int j = 0; j < M; j++) {
if (board[i][j] == 'R') {
redX = i; redY = j;
} else if (board[i][j] == 'B') {
blueX = i; blueY = j;
}
}
}
System.out.println(bfs(redX, redY, blueX, blueY));
br.close();
}
}
마무리
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.
Junior backend developer