[백준] 13460번 구슬탈출2(삼성역량)
- 삼성역량 특성상 +
- 이 문제의 조건
- " 10번 이하로 움직여 빨간 구슬을 구멍을 통해 빼낼 수 없다면 -1 출력 " —> depth제한을 주었다.
- "N과 M이 10이하"
를 보면, 완전탐색을 이용 해도 되는 문제인 듯 하다.
-
백트랙킹 + bfs를 하도록 한다.
- 현재의 red, blue위치를 저장한다.
-
각 방향으로 기울이기를 할 때, 매 번, 이런것을 확인해야하는가?
- 각 상태를 저장하도록 한다. backtracking 할 수있도록 .
- 왼쪽 or 오른쪽으로 기울이기라면, red, blue가 같은 row에 있는지 확인,
- 왼쪽기울이기이면, 왼쪽에 있는 구슬부터 이동시키기
- 오른쪽기울이기이면, 오른쪽에 있는 구슬부터 이동시키기
- 위로 or 아래로 기울이기라면, red, blue 가 같은 col에 있는지 확인
- 이미 해당 red, blue 구슬과 같은 위치를 방문한적 있다면 —> pass
- blue가 구멍에 들어가는 경우 무조건 실패
- 즉, 같은 기울이기에서, red가 먼저 구멍에 들어가고 blue가 들어가도 —>실패
- blue가 먼저 구멍에 들어가도 —> 실패
-
기울이기 구현???
기울이기 구현
- 나는 while문을 사용하여, 경우를 나누는 유형을 잘 못하는 것 같다. 실제 코테에서도 당황하여 풀지 못했던 적이 있다. 이 문제 역시 많은 어려움을 겪었다. 먼저.. 풀 수 있을 것 같지만 모든 경우를 생각하는 것에 어려움을 겪어 문제를 처음 보고 이주 후에서야 풀이를 시작했다.
- 천천히 한 번 풀어보도록 하자.
- 장애물? —>'#', '다른 구슬' ,'O'
- 구슬을 실제 board에 위치시키는게 맞을까? → 구슬을 이동시키는 것을 구현할 때, 실제 board상에서 이동시키면, 다시 되돌려 놓는 과정이 필요하다.
- 나는 이것이 번거로울 것이라 생각하여
- 구슬의 위치는 다른 변수에 저장.
- 구슬을 실제 board에 위치시키는게 맞을까? → 구슬을 이동시키는 것을 구현할 때, 실제 board상에서 이동시키면, 다시 되돌려 놓는 과정이 필요하다.
- 이 direction은 종료한다. 라는 말은
- 이 direction 결과 나오는 red, blue의 위치는 q에 넣지 않음을 의미한다. + ( 더불에, direction을 종료하는 경우가 아닌, red만 성공적으로 구멍에 빠진 경우에도, q에 넣지 않고, visit여부를 체크하지 않고 종료하도록 한다. 사실 red만 구멍에 빠지는 경우는 여러가지가 있을수도 있기 때문이다 )
- 하나의 direction으로의 기울이기를 할 때 마다, Red 를 먼저 움직이고 → Blue를 움직인다. ( 중복되는 곳을 계속 시도하려 할 수도 있는가? )
- Red를 움직이다가 Blue에 막히면 Blue를 다 움직이고 Red를 움직인다.
- blue에 막힌 경우 : Blue를 이동시킨다.
- Blue를 이미 이동시킨 적 있는 경우 → red의 이동을 취소하고 , RED의 이동을 멈춘다. (direction 자체를 fail시키는 것이 아니다 )
- Blue를 아직 이동시킨 적 없는 경우 Blue를 이동 시킨다
- Blue가 더 이상 움직일 수 없는 곳 인 경우(Blue를 움직이고나서도, Red와 위치가 같은 경우 ) → Red를 후퇴시키고, 이 direction은 종료한다
- Blue를 더 움직일 수 있는 곳인 경우 → 이후 Red를 더 움직인다.
- Blue를 움직였는데 Blue가 'o'에 빠지는 경우 —> 이 direction을 아예 종료한다.
- Blue를 움직일 수 있고, Blue가 'o'에 빠지지 않는 경우 → 일단 다 이동시킨다.
- Blue에 막히지 않은 경우
- Red를 움직이다가 'O'에 빠진 경우
- Red만 빠지는 경우 → red만 빠지는게 fail은 아니지만, 이렇게 빠지게 되는 경우, q에 이 때의 red, blue가 들어가서는 안 되기 때문에, fail을 check해 주어야 한다.
- Red가 빠진 후, Blue도 이 하나의 이동에서 'O'로 빠지게 되는 경우 (ex: B R .. O .. 인 경우 )
- 위와 같이 두 가지 경우가 있을 수가 있다. 하지만 지금 나는 Red부터 움직이려고 하니, 당장 Red가 빠졌을 때는 위의 둘 중 어느 경우인지 알 수 없다. —> 따라서, flag를 두도록 한다. —> redOut = true; 로 체크한다.
- 나머지 경우 —> 일단 다 이동시킨다.
- Red를 움직이다가 'O'에 빠진 경우
- blue에 막힌 경우 : Blue를 이동시킨다.
- Red를 움직이고 Blue를 움직이는 경우
- Red에 막히는 경우 : 이미 앞에서 Red를 움직인 거라 여기서는 Red를 움직이지 않는다.
- Blue를 이동할 수 있는만큼이동시킨다. ( 어차피 이 과정들 이후, red, blue의 위치를 visit한 적 있는지 볼거라서 )
- Blue가 'O'에 빠지는 경우 —> 이 방향의 direction을 종료 한다.
- 나머지 경우는 이동 할 수 있는 만큼 이동시킨다.
- Red에 막히는 경우 : 이미 앞에서 Red를 움직인 거라 여기서는 Red를 움직이지 않는다.
- Red를 움직이다가 Blue에 막히면 Blue를 다 움직이고 Red를 움직인다.
- visit 체크는, red, blue의 위치 둘 다를 해 줘야 한다 → visit을 4차원으로 생성한다.
22프로에서 틀렸다
반례
7 7
#######
#...BR#
#.#####
#.....#
#####.#
#O....#
#######
// -1- 내가 해 주지 않았던 예외처리 : Red가 Blue에 의해서 block되면 → Blue를 먼저 이동시키도록 구현했었음. 그런데 이 때 인지하는 상황은,
- 이동한 Red가 Blue의 위치와 같고, Blue를 이동시키지 않았던 경우임.
- 그래서,Red가 Blue의 위치와 같고, Blue를 이동시킨 경우, 그냥 Red를 이동시켜 Blue와 코드가 같게 되는 결과가 나와버렸음
최종 결과
import java.io.*;
import java.util.*;
public class Main {
public static int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}}; //오른쪽 , 왼쪽, 아래로, 위로 기울이기
public static boolean[][][][] visit = new boolean[10][10][10][10];
public static int[] red = new int[2];
public static int[] blue = new int[2];
public static int n,m;
// String으로 받을까?
public static char[][] board;
public static void Setting() 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];
visit = new boolean[n][m][n][m];
// board setting
String temp="";
for(int r=0;r<n;r++){
temp = br.readLine();
for(int c=0;c<m;c++){
board[r][c]= temp.charAt(c);
if(temp.charAt(c) =='R') {
board[r][c] ='.';
red[0] = r;
red[1]=c;
}
else if(temp.charAt(c) =='B'){
board[r][c] ='.';
blue[0] = r;
blue[1]=c;
}
}
}
}
// q에 넣을 때 , 모든 조건을 확인하고 넣는다.
public static int bfs(){
int min = 11;
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{red[0],red[1],blue[0],blue[1],0}); //red location, blue location, depth
visit[red[0]][red[1]][blue[0]][blue[1]] = true;
// q에는 red, blue의 위치,depth 를 저장한다.
while(q.isEmpty()==false) {
int[] cur = q.poll(); // cur[0]: ry, cur[1]:rx, cur[2]:by, cur[3]:bx
// depth가 10이상인 순간 반복문을 종료
if(cur[4]>9) break;
boolean loopr=true,loopb=true;
for (int dir = 0; dir < dirs.length; dir++) {
int nry=cur[0],nrx=cur[1],nby=cur[2],nbx=cur[3];
boolean alreadyMoved = false;
boolean fail = false;
boolean redOut = false;
// RED 먼저 움직이다가, BLUE에 의해 BLOCKED되면 BLUE를 움직이기
// 어차피 #을 만나면 멈추기 때문에 loop condition을 true로 해 두자
while(loopr){
nry+= dirs[dir][0];
nrx+= dirs[dir][1];
// 1. block by blue + blue를 아직 움직인적 없는 경우
if(nry == nby && nrx==nbx && alreadyMoved==false) {
// blue를 먼저 움직이기
while (true) {
alreadyMoved = true;
nby += dirs[dir][0];
nbx += dirs[dir][1];
// blue가 구멍에 빠지는 경우 -> 이 direction 으로의 이동이 실패하는 거임
if (board[nby][nbx] == 'O') {
fail = true;
break;
}
// blue가 이동한 곳이 '.'이 아닌 경우 ('O'였으면 이미 위에서 걸려서 break) -> '#'
else if(board[nby][nbx]!='.') {
nby -= dirs[dir][0];
nbx -= dirs[dir][1];
break;
}
}
// blue가 구멍에 빠진 경우 -> 이 direction을 아예 종료
if(fail) break;
}
// Blue를 통해 이 direction을 종료해야한다고 판단 -> 이 direction을 아예 종료
if(fail) break;
// BLue에의해 막혔고, 이미 BLUE에 의해 막혔어서, Blue를 이동시킨 후인경우
if(nry == nby && nrx==nbx && alreadyMoved) {
// 일단 red의 이동을 취소
nry-= dirs[dir][0];
nrx-= dirs[dir][1];
break;
}
// Blue에 막히지 않은 경우
// Red를 움직이다 'O'에 빠진 경우
if(board[nry][nrx]=='O') {
redOut=true;
break;
}
// Red를 움직이다 '#'에 가로막힌 경우 -> red이동을 취소한다
else if(board[nry][nrx]=='#') {
nry-= dirs[dir][0];
nrx-= dirs[dir][1];
break;
}
}
// RED loop 만 돌았는데 이 direction은 종료해야겠다 싶은 경우
if(fail)continue;
// BLUE를 움직인다
while(loopb){
nby += dirs[dir][0];
nbx+= dirs[dir][1];
// RED에 막히는 경우 && red가 구멍을 통해 빠져나간게 아닌 경우
if(nby == nry && nbx == nrx&& !redOut){
nby -= dirs[dir][0];
nbx -= dirs[dir][1];
break;
}
// blue가 'O'에 빠지는 경우
if(board[nby][nbx]=='O'){
fail = true;
break;
}
// blue가 '#'에 막히는 경우
if(board[nby][nbx]!='.'){
nby -= dirs[dir][0];
nbx -= dirs[dir][1];
break;
}
}
// 이 방향으로 기울이기가 실패인 경우 --> fail이라는 것은, 이 direction으로의 기울이기가 아예 실패인 경우임.
if(fail) continue;
// red만 빠진 경우 -> min을 update한다. red가 구멍에 빠진 경우를 q에 넣지 않게 주의
if(redOut){
if(min>cur[4]+1) {
min = cur[4]+1;
}
continue;
}
// 여기서 나온 nry,nrx,nby,nbx가 이미 visit된 적 있는 경우
if(visit[nry][nrx][nby][nbx]) continue;
// 다른 경우는 q에 넣는다.
q.add(new int[]{nry,nrx,nby,nbx,cur[4]+1});
visit[nry][nrx][nby][nbx] = true;
}
}
return min;
}
public static void main(String[] args) throws IOException {
Setting();
int ans = bfs();
//System.out.println(ans);
if(ans > 10) System.out.println(-1);
else System.out.println(ans);
}
}예시들
10 10
##########
#R#...##B#
#.....##.#
#####.##.#
#......#.#
#.######.#
#.#......#
#.#.#.#..#
#...#.O.##
##########
10 10
##########
#R#...##B#
#.....##.#
#####.##.#
#......#.#
#.######.#
#.#.....##
#.#.#.#.##
#...#O..##
##########
10 10
##########
#R#...##B#
#.....##.#
#####.##.#
#......#.#
#.######.#
#.#....###
#.#.##..##
#...#.#O##
##########
3 10
##########
#.R.B..O.#
##########
3 10
##########
#.B.R..O.#
##########
7 7
#######
#...BR#
#.#####
#.....#
#####.#
#O....#
#######
// -1
8 8
########
#.####.#
#...#B##
#.##.R.#
######.#
##.##O.#
###.##.#
########
//7
