| 2 초 | 512 MB | 59965 | 17667 | 9531 | 26.629% |
문제
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
출력
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
문제 풀이
문제 난이도는 그렇게 높지 않았으나
코드가 길어지면서 실수를 할 여지가 많은 문제였습니다.
조건에 맞게 차근차근 구현을 해 보도록 하겠습니다.
문제의 조건은 아래와 같습니다.
보드의 세로 N
보드의 가로 M
보드의 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다.
. 빈 칸
# 벽
O 탈출
R 빨간 구슬
B 파란 구슬
가장 바깥 행은 막혀있고, 보드에는 구멍이 하나 있다.
빨간 구슬과 파란구슬은 하나씩
빨간 구슬을 빼내는게 목표
파란 구슬을 빼면 실패
동시에 빼도 실패
빨간 구슬과 파란 구슬은 같은 칸에 있을 수 없다.
기울이는 동작을 그만하는 것은 더이상 구슬이 움직이지 않을 때 까지
최소 몇번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하라
최소 몇번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 문제입니다.
최단거리를 구하는 문제이기 때문에 BFS를 이용하여 문제를 해결하면 더 효율적일 것으로 보입니다.
우선 문제의 입력 정보를 변수로 옮기도록 하겠습니다.
세로 N, 가로 M 이라는 내용이 저에게는 직관적이지 않아 row, col으로 변경해서 사용하도록 하겠습니다.
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
보드의 문자열 정보를 받아와야 합니다.
보드에는 빨간 공, 파란 공의 위치도 나타나 있습니다.
이 정보를 저장할 공간이 필요한데 저는 Ball 이라는 클래스를 이용하여 현재 빨간 공의 위치와, 파란 공의 위치, 그리고 진행한 횟수(turn) 정보를 저장해 보도록 하겠습니다.
Ball 클래스입니다.
멤버 접근제한자를 풀어 직접 값을 입력하고, 들고오면 코드를 더 짧게 구현할 수는 있을 것 같습니다.
저는 private 접근 제한자를 사용하였기 때문에 getter와 setter를 열어 놓아 값을 받고, 넣도록 하겠습니다.
class Ball {
private int redRow;
private int redCol;
private int blueRow;
private int blueCol;
private int turn;
public Ball(int redRow, int redCol, int blueRow, int blueCol, int turn) {
this.redRow = redRow;
this.redCol = redCol;
this.blueRow = blueRow;
this.blueCol = blueCol;
this.turn = turn;
}
public Ball() {
}
public int getRedRow() {
return redRow;
}
public void setRedRow(int redRow) {
this.redRow = redRow;
}
public int getRedCol() {
return redCol;
}
public void setRedCol(int redCol) {
this.redCol = redCol;
}
public int getBlueRow() {
return blueRow;
}
public void setBlueRow(int blueRow) {
this.blueRow = blueRow;
}
public int getBlueCol() {
return blueCol;
}
public void setBlueCol(int blueCol) {
this.blueCol = blueCol;
}
public int getTurn() {
return turn;
}
public void setTurn(int turn) {
this.turn = turn;
}
}
문제로 부터 board의 정보를 받아오고, 빨간공과 파란공의 위치는 Ball 클래스에 집어넣도록 하겠습니다.
Character[][] tile_info = new Character[row][col];
Ball ball = new Ball();
ball.setTurn(1);
// 탈출 하는 위치
int[] break_info = new int[2];
for (int i = 0; i < row; i++) {
String tiles = br.readLine();
for (int j = 0; j < col; j++) {
char tile = tiles.charAt(j);
tile_info[i][j] = tile;
if (tile == 'B') {
ball.setBlueRow(i);
ball.setBlueCol(j);
}
if (tile == 'R') {
ball.setRedRow(i);
ball.setRedCol(j);
}
if (tile == 'O') {
break_info[0] = i;
break_info[1] = j;
}
}
}
로직을 구현하기에 앞서 좀 더 간단하게 코드를 구현하기 위해 몇가지 준비를 합니다.
우선 공은 상, 하, 좌, 우로 이동할 수 있습니다.
move_row, move_col 배열을 이용해서 상, 하, 좌, 우 이동하는 코드를 구현하도록 하겠습니다.
아래 코드는 상, 하, 좌, 우로 한칸씩 이동하는 예시 코드입니다.
벽을 만날 때 까지 이동할 것이기 때문에 여기서 while문을 추가해 주면 될 것 같습니다.
그 내용은 뒷부분에서 살펴보도록 하겠습니다.
move_row, movel_col 배열을 준비합니다.
private static int[] move_row = {-1, 1, 0, 0};
private static int[] move_col = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
next_row = current_row + move_row[0]
next_col = current_col + move_col[0]
}
두번째로는 코드의 효율성을 증진시키기 위해 visit[][][][] 배열을 사용하도록 하겠습니다.
벽을 만났을 때 공은 정지할 것입니다.
정지했을 때의 빨간 공의 위치와 파란 공의 위치가 이전에 방문해본 적이 있다면,
이미 최단거리를 구할 수 있는 자격을 상실한 것입니다.
이전에 이미 와본적이 있는 공들이 있기 때문입니다.
아래와 같이 visit[][][][] 배열을 준비하도록 합시다.
private static boolean[][][][] visit;
visit = new boolean[row][col][row][col];
몇 번 만에 탈출을 했는지의 정보를 담고 있는 endTurn 변수와
while 조건문을 탈출 할 수 있도록 도와주는 isEnd 변수를 초기화 해 줍시다.
int endTurn = -1;
boolean isEnd = false;
BFS를 사용할 것이기 때문에 queue를 준비해주고
현재 빨간볼의 위치와, 파란볼의 위치 정보를 담고 있는 Ball 클래스에 넣어줍시다.
Queue<Ball> queue = new LinkedList<>();
queue.add(ball);
준비는 끝났습니다.
가지고 있는 것을 바탕으로 BFS를 구현해보도록 하겠습니다.
queue가 빌 때까지 while문을 돌립니다.
queue에서 Ball을 하나씩 꺼내고, Ball에서 빨간 공의 위치와 파란 공의 현재 위치를 파악합니다.
그리고 10번 내로 탈출을 못할 경우에 종료를 해야 합니다.
해당 내용을 if 문으로 구현합니다.
그리고 탈출 조건을 만족했을 때 탈출을 한다는 조건도 if 문으로 구현을 합니다.
while (!queue.isEmpty()) {
Ball current_ball = queue.remove();
int current_red_row = current_ball.getRedRow();
int current_red_col = current_ball.getRedCol();
int current_blue_row = current_ball.getBlueRow();
int current_blue_col = current_ball.getBlueCol();
int turn = current_ball.getTurn();
if (turn > 10) {
endTurn = -1;
break;
}
if (isEnd) {
break;
}
자 이제 앞서 살펴보았던 코드입니다.
탈출 구멍을 만났는 지에 대한 여부를 저장하는 is_red_goal, is_blue_goal 변수를 초기화 해주고
빨간 공과 파란 공이 벽을 만나기 까지 얼마나 이동을 했는 지에 대한 정보를 저장하는 red_move_distance, blue_move_distance를 초기화 해주도록 하겠습니다.
red_move_distance와 blue_move_distance의 사용 용도는 뒤에서 다시 살펴보도록 하겠습니다.
현재 위치를 기반으로 상, 하, 좌, 우로 한 칸씩 이동합니다.
for (int i = 0; i < 4; i++) {
boolean is_red_goal = false;
boolean is_blue_goal = false;
int red_move_distance = 0;
int blue_move_distnace = 0;
int next_red_row = current_red_row + move_row[i];
int next_red_col = current_red_col + move_col[i];
int next_blue_row = current_blue_row + move_row[i];
int next_blue_col = current_blue_col + move_col[i];
지금 까지는 한 칸만 이동한 것입니다.
while문을 이용해서 벽을 만날 때 까지 계속 이동을 하는 코드를 구현하도록 하겠습니다.
벽을 만날때 까지 이동하는 코드입니다.
빨간 공과, 파란 공 둘다 동일한 로직이기 때문에 빨간 공을 기준으로 설명하도록 하겠습니다.
벽을 만날 때 까지 이동하는 while문을 구현합니다.
벽을 만나기 전에 빨간공이 탈출에 성공한다면 탈출에 성공했다는 flag를 저장하도록 하겠습니다.
벽을 만나지 않았다면 계속해서 이동을 합니다.
마지막으로 while문 밖에 존재하는 next_red_row, next_red_col에 대한 설명입니다.
while문에 대한 조건이 벽을 만날 때 까지 이동하는 것이기 때문에
while문을 벗어난 상태에 빨간 공의 위치는 벽의 위치와 동일합니다.
그렇기 때문에 한 칸 이동하기 전 위치로 돌아가야 합니다.
한칸 전으로 돌아가기 위해서 -= move_row[i], -= move_col[i] 를 더해주도록 합니다.
while (tile_info[next_red_row][next_red_col] != '#') {
// 범위를 벗어나지 않았으면서
if (next_red_row > 0 && next_red_col > 0 && next_red_row < row
&& next_red_col < col) {
// 탈출에 성공하면
if (tile_info[next_red_row][next_red_col] == 'O') {
is_red_goal = true;
break;
}
// 벽을 만나지 않았으면 계속해서 이동
next_red_row += move_row[i];
next_red_col += move_col[i];
red_move_distance ++;
}
}
// 벽을 만났으니, 이전칸으로 이동
next_red_row -= move_row[i];
next_red_col -= move_col[i];
자 동일하게 파란공도 구현을 하셨겠죠??
이제 이동 완료한 공을 확인해 봅시다.
파란공이 탈출했다면 다음 for loop로 돌아갑니다.
빨간공이 탈출했으면 종료를 해야합니다.
종료 flag (isEnd)를 저장해주고
몇 턴만에 성공했는지를 저장 (endTurn)해 줍니다.
// 파란공이 탈출했으면 실패
if (is_blue_goal) {
continue;
}
// 빨간공이 탈출했으면 성공
if (is_red_goal && !is_blue_goal) {
isEnd = true;
endTurn = turn;
continue;
}
만약에 실패도, 성공도 아닌 경우라면 계속해서 이동해야 합니다.
벽을 만날때 까지 이동을 했기 때문에, 빨간 공과 파란 공은 현재 같은 위치에 있을 수도 있습니다.
현재 빨간 공과 파란 공의 위치는 벽 바로 옆에 존재하는 상황일 것입니다.
둘 중 하나는 벽과 두칸 떨어져 있어야 하는 상황입니다.
이 문제를 해결하기 위해서 앞에서 만들어 놓았던 red_move_distance와 blue_move_distance를 이용합니다.
초기 위치가 현재의 위치와 더 많이 떨어져 있는 경우가 별에서 두칸 떨어져야 하는 경우입니다.
이것을 코드로 구현하면 아래와 같습니다.
// 빨간공과 파란공이 같은 위치에 있으면
if (next_red_row == next_blue_row && next_red_col == next_blue_col) {
if (red_move_distance > blue_move_distnace) {
next_red_row -= move_row[i];
next_red_col -= move_col[i];
}
if (red_move_distance < blue_move_distnace) {
next_blue_row -= move_row[i];
next_blue_col -= move_col[i];
}
}
이제 효율성을 위해서 만들어 놓았던 visit 배열을 사용할 차례입니다.
우리는 최단 거리로 빨간공이 통과하는 것을 목표로 하고 있기 때문에
현재 정지한 공의 위치가 이전에 방문 한 적이 없을 경우에만 다시 굴려서 다음 위치를 확인할 예정입니다.
visit 배열이 false 인 경우에만 다음 위치를 확인할 것이고
현재 위치의 visit 배열을 true로 변경을 하고
현재 위치의 Ball을 queue에 넣어주면 문제를 해결할 수 있습니다.
if (!visit[next_red_row][next_red_col][next_blue_row][next_blue_col]) {
visit[next_red_row][next_red_col][next_blue_row][next_blue_col] = true;
queue.add(
new Ball(next_red_row, next_red_col, next_blue_row, next_blue_col, turn + 1));
}
여기까지 오시느라 수고하셨습니다.
전체 코드는 아래에서 확인하실 수 있습니다.
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 baekjoon13460 {
private static boolean[][][][] visit;
private static int[] move_row = {-1, 1, 0, 0};
private static int[] move_col = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
// 보드의 세로 N
// 보드의 가로 M
// 가장 바깥 행은 막혀있고, 보드에는 구멍이 하나 있다.
// 빨간 구슬과 파란구슬은 하나씩
// 빨간 구슬을 빼내는게 목표
// 파란 구슬을 빼면 실패
// 동시에 빼도 실패
// 빨간 구슬과 파란 구슬은 같은 칸에 있을 수 없다.
// 기울이는 동작을 그만하는 것은 더이상 구슬이 움직이지 않을 때 까지
// 최소 몇번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하라
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
Character[][] tile_info = new Character[row][col];
Ball ball = new Ball();
ball.setTurn(1);
// 탈출 하는 위치
int[] break_info = new int[2];
for (int i = 0; i < row; i++) {
String tiles = br.readLine();
for (int j = 0; j < col; j++) {
char tile = tiles.charAt(j);
tile_info[i][j] = tile;
if (tile == 'B') {
ball.setBlueRow(i);
ball.setBlueCol(j);
}
if (tile == 'R') {
ball.setRedRow(i);
ball.setRedCol(j);
}
if (tile == 'O') {
break_info[0] = i;
break_info[1] = j;
}
}
}
visit = new boolean[row][col][row][col];
int endTurn = -1;
boolean isEnd = false;
Queue<Ball> queue = new LinkedList<>();
queue.add(ball);
while (!queue.isEmpty()) {
Ball current_ball = queue.remove();
int current_red_row = current_ball.getRedRow();
int current_red_col = current_ball.getRedCol();
int current_blue_row = current_ball.getBlueRow();
int current_blue_col = current_ball.getBlueCol();
int turn = current_ball.getTurn();
if (turn > 10) {
endTurn = -1;
break;
}
if (isEnd) {
break;
}
for (int i = 0; i < 4; i++) {
boolean is_red_goal = false;
boolean is_blue_goal = false;
int red_move_distance = 0;
int blue_move_distnace = 0;
int next_red_row = current_red_row + move_row[i];
int next_red_col = current_red_col + move_col[i];
int next_blue_row = current_blue_row + move_row[i];
int next_blue_col = current_blue_col + move_col[i];
while (tile_info[next_red_row][next_red_col] != '#') {
// 범위를 벗어나지 않았으면서
if (next_red_row > 0 && next_red_col > 0 && next_red_row < row
&& next_red_col < col) {
// 탈출에 성공하면
if (tile_info[next_red_row][next_red_col] == 'O') {
is_red_goal = true;
break;
}
// 벽을 만나지 않았으면 계속해서 이동
next_red_row += move_row[i];
next_red_col += move_col[i];
red_move_distance ++;
}
}
// 벽을 만났으니, 이전칸으로 이동
next_red_row -= move_row[i];
next_red_col -= move_col[i];
while (tile_info[next_blue_row][next_blue_col] != '#') {
// 범위를 벗어나지 않았으면서
if (next_blue_row > 0 && next_blue_col > 0 && next_blue_row < row
&& next_blue_col < col) {
// 결승선에 도착하면
if (tile_info[next_blue_row][next_blue_col] == 'O') {
is_blue_goal = true;
break;
}
// 벽을 만나지 않았으면 계속해서 이동
next_blue_row += move_row[i];
next_blue_col += move_col[i];
blue_move_distnace ++;
}
}
// 벽을 만났으니 이전 상태로 이동
next_blue_row -= move_row[i];
next_blue_col -= move_col[i];
// 파란공이 탈출했으면 실패
if (is_blue_goal) {
continue;
}
// 빨간공이 탈출했으면 성공
if (is_red_goal && !is_blue_goal) {
isEnd = true;
endTurn = turn;
continue;
}
// 빨간공과 파란공이 같은 위치에 있으면
if (next_red_row == next_blue_row && next_red_col == next_blue_col) {
if (red_move_distance > blue_move_distnace) {
next_red_row -= move_row[i];
next_red_col -= move_col[i];
}
if (red_move_distance < blue_move_distnace) {
next_blue_row -= move_row[i];
next_blue_col -= move_col[i];
}
}
// System.out.printf("%s %s %s %s %s\n", turn, next_red_row, next_red_col, next_blue_row, next_blue_col);
// 다음 이동할 위치가, 이전에 방문한 적이 없다면
// 계속해서 문제를 풀어봅니다.
if (!visit[next_red_row][next_red_col][next_blue_row][next_blue_col]) {
visit[next_red_row][next_red_col][next_blue_row][next_blue_col] = true;
queue.add(
new Ball(next_red_row, next_red_col, next_blue_row, next_blue_col, turn + 1));
}
}
}
System.out.println(endTurn);
}
}
class Ball {
private int redRow;
private int redCol;
private int blueRow;
private int blueCol;
private int turn;
public Ball(int redRow, int redCol, int blueRow, int blueCol, int turn) {
this.redRow = redRow;
this.redCol = redCol;
this.blueRow = blueRow;
this.blueCol = blueCol;
this.turn = turn;
}
public Ball() {
}
public int getRedRow() {
return redRow;
}
public void setRedRow(int redRow) {
this.redRow = redRow;
}
public int getRedCol() {
return redCol;
}
public void setRedCol(int redCol) {
this.redCol = redCol;
}
public int getBlueRow() {
return blueRow;
}
public void setBlueRow(int blueRow) {
this.blueRow = blueRow;
}
public int getBlueCol() {
return blueCol;
}
public void setBlueCol(int blueCol) {
this.blueCol = blueCol;
}
public int getTurn() {
return turn;
}
public void setTurn(int turn) {
this.turn = turn;
}
}