문제 유형
문제 접근
- 답
- 빨간공이 구멍에 도달하기 위한 최소 움직임 횟수
- 주어지는 정보
⇒ 완전 탐색 가능(전체 보드의 크기가 매우 작으므로)
- “최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다”
⇒ BFS(최소라는 단어가 붙었으므로, DFS는 적합하지 않다)
import java.util.*;
import java.io.*;
class Ball
{
public int rx,ry;
public int bx,by;
public int cnt;
Ball(int rx, int ry, int bx, int by, int cnt)
{
this.rx = rx;
this.ry = ry;
this.bx = bx;
this.by = by;
this.cnt = cnt;
}
}
public class Main {
static int R,C;
static char[][] board;
static int[][] move = {{-1,0},{0,-1},{1,0},{0,1}};
public static void print_board()
{
for(int i = 0; i<R; i++)
{
for(int j = 0; j<C; j++)
{
System.out.print(board[i][j]);
}
System.out.println();
}
}
static int result = -1;
public static int bfs(int rx, int ry, int bx, int by)
{
Queue<Ball>q = new LinkedList<>();
q.add(new Ball(rx,ry,bx,by,0));
boolean[][][][] visited = new boolean[11][11][11][11];
visited[rx][ry][bx][by] = true;
while(!q.isEmpty())
{
Ball ball = q.peek();
q.remove();
//판을 10번 넘게 움직이면 실패
if(ball.cnt > 10)
{
return -1;
}
//빨간공이 O에 들어가면 성공
if(board[ball.ry][ball.rx] == 'O')
{
return ball.cnt;
}
//파란공이 O에 들어가면 실패
else if(board[ball.by][ball.bx] == 'O')
{
continue;
}
for(int i = 0; i<4; i++)
{
int red_x = ball.rx;
int red_y = ball.ry;
int red_distance = 0;
//빨간공 움직이기
while(board[red_y + move[i][0]][red_x + move[i][1]] != '#')
{
red_distance++;
red_y += move[i][0];
red_x += move[i][1];
//공이 O에 도달하면 움직일 수 없음
if(board[red_y][red_x] == 'O')
{
break;
}
}
//파란공 움직이기
int blue_x = ball.bx;
int blue_y = ball.by;
int blue_distance = 0;
while(board[blue_y + move[i][0]][blue_x + move[i][1]] != '#')
{
blue_distance++;
blue_y += move[i][0];
blue_x += move[i][1];
if(board[blue_y][blue_x] == 'O')
{
break;
}
}
//공 2개가 겹치면 뒤늦게 도착한 공이 밀려남
if(red_x == blue_x && red_y == blue_y)
{
if(board[red_y][red_x] == 'O')
{
continue;
}
if(red_distance > blue_distance)
{
red_y -= move[i][0];
red_x -= move[i][1];
}
else
{
blue_y -= move[i][0];
blue_x -= move[i][1];
}
}
if(visited[red_x][red_y][blue_x][blue_y] == true)
{
continue;
}
visited[red_x][red_y][blue_x][blue_y] = true;
q.add(new Ball(red_x,red_y,blue_x,blue_y,ball.cnt+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());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
board = new char[R+1][C+1];
//make board
for(int i = 0; i<R; i++)
{
String s = br.readLine();
for(int j = 0; j<C; j++)
{
board[i][j] = s.charAt(j);
}
}
int rx = 0;
int ry = 0;
int bx = 0;
int by = 0;
//collect ball
for(int i = 0; i<R; i++)
{
for(int j = 0; j<C; j++)
{
if(board[i][j] == 'R')
{
rx = j;
ry = i;
board[i][j] = '.';
}
else if(board[i][j] == 'B')
{
bx = j;
by = i;
board[i][j] = '.';
}
}
}
System.out.println(bfs(rx,ry,bx,by));
}
}
나의 틀린 답안
- 문제 접근(DFS)
- 이유
- 메모리 제한으로 인해 DFS로 푸는 게 좋겠다고 생각했음
- BFS는 판을 움직이고 난 이후에, 해당 판을 다시 되돌리는 과정을 하려면 판을 복사해야했음. 판 복사 시, 최대 40억byte((99)(4byte^10))가 필요하므로 BFS는 적절치 못하다고 판단
⇒ 틀렸다. 판을 복사하는 것 외에도 다른 방법 많음.
- DFS는 재귀 호출이 끝난 이후에, 해당 판을 반대로 움직이면 메모리를 절약할 수 있겠다고 판단
⇒ 틀렸다. 문제는 최소 값을 구하는 것이므로, DFS는 처음부터 잘못된 접근.
import java.util.*;
import java.io.*;
class Ball
{
public int x,y;
// 0 = Red, 1 = Blue
public char color;
Ball(int x,int y,char color)
{
this.x = x;
this.y = y;
this.color = color;
}
}
public class Main {
static int R,C;
static char[][] board;
static List<Ball> balls = new ArrayList<>();
static int[][] move = {{-1,0},{0,-1},{1,0},{0,1}};
public static void print_board()
{
for(int i = 0; i<R; i++)
{
for(int j = 0; j<C; j++)
{
System.out.print(board[i][j]);
}
System.out.println();
}
}
public static void print_ball()
{
for(Ball ball : balls)
{
System.out.println("x : " + ball.x);
System.out.println("y : " + ball.y);
if(board[ball.y][ball.x] == 'O')
{
System.out.println("success");
}
}
System.out.println("-----------");
}
public static void move_ball(int x,int y)
{
for(Ball ball : balls)
{
int move_x = ball.x + x;
int move_y = ball.y + y;
if(move_x >= 0 && move_x < C && move_y >= 0 && move_y < R)
{
if(board[move_y][move_x] == '.' || board[move_y][move_x] == 'O')
{
ball.x = move_x;
ball.y = move_y;
continue;
}
else if(board[move_y][move_x] == '#')
{
continue;
}
int cur_x = move_x;
int cur_y = move_y;
while(board[cur_y][cur_x] == 'R' || board[cur_y][cur_x] == 'B')
{
cur_x += x;
cur_y += y;
if(cur_x < 0 || cur_x >= C || cur_y < 0 || cur_y >= R)
{
break;
}
else
{
if(board[cur_y][cur_x] == '.' || board[cur_y][cur_x] == 'O')
{
ball.x = move_x;
ball.y = move_y;
break;
}
else if(board[cur_y][cur_x] == '#')
{
break;
}
}
}
}
}
}
public static boolean find_ball()
{
for(Ball ball : balls)
{
if(board[ball.y][ball.x] == 'O' && ball.color == 'R')
{
return true;
}
}
return false;
}
static int result = -1;
public static void dfs(int cnt)
{
if(cnt > 10)
{
return;
}
if(find_ball())
{
result = cnt;
return;
}
int x;
int y;
for(int i = 0; i<4; i++)
{
x = move[i][0];
y = move[i][1];
move_ball(x,y);
dfs(cnt+1);
move_ball(-x,-y);
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
board = new char[R][C];
//make board
for(int i = 0; i<R; i++)
{
String s = br.readLine();
for(int j = 0; j<C; j++)
{
board[i][j] = s.charAt(j);
}
}
//collect ball
for(int i = 0; i<R; i++)
{
for(int j = 0; j<C; j++)
{
if(board[i][j] == 'B' || board[i][j] == 'R')
{
Ball ball = new Ball(j,i,board[i][j]);
balls.add(ball);
}
}
}
dfs(0);
System.out.println(result);
}
}