1. 문제에 대하여 📦
(1) 조건 분석 📊
- 격자판을 기울이면, 기울어진 쪽 끝까지 이동한다. (한 칸씩 x)
- 만약 구멍으로 Red 구슬, Blue 구슬 둘 다 들어가면 이건 실패로 간주한다.
- 기울인 거 한번 == 움직임 한 번으로 간주한다.
2. 코드가 나오기까지 🛠️
KEY WORD: 시뮬레이션, BFS
개빡구현 시뮬레이션이다. 필자가 봤을 때, 구현이 어려운 포인트를 집어봤다.
- 방문처리를 어떻게 할 것인지
- 기울임 = 움직임 한 번 체크는 어떻게 할 것인지
- 구슬 두 개가 하나의 좌표로 모이는 경우
- RED가 구멍에 들어갔을 때, Blue가 구멍에 들어갔을 떄, 둘 다 들어갔을 때 처리
하나씩 살펴보자.
(1) 방문 처리를 어떻게 할 것인지
우리가 방문 처리를 하는 이유는 '같은 계산을 반복하지 않기 위해서' 이다.
이미 방문한 자리를 다시 접근한다면, 이후 후속 움직임은 이미 전에 계산한 움직임과 똑같다.
만약 RED와 BLUE 에 대해 따로 방문처리를 한다면 위의 목적에서 멀어진다.
왜냐하면, RED가 이미 방문한 적 있는 좌표에 있어도, BLUE의 위치가 지난 방문과 다르다면 또 다른 양상이 펼쳐지기 때문이다. 즉 후속 움직임은 전혀 다른 양상으로 펼쳐진다.
따라서, RED와 BLUE 의 위치 조합마다 방문 처리를 해줘야 원래의 방문처리 목적과 의미가 맞아진다. 위치 조합마저 같다면, 그 이후의 양상은 이미 계산한 내용과 같아지기 때문이다.
필자는 해당 계산을 위해 4차원 배열을 사용했다.check[red 행 위치][red 열 위치][blue 행 위치][blue 열 위치] 로 나타내서 방문 처리를 했다.
(2) 기울임 = '움직임 한 번' 체크는 어떻게 할 것인지
기존 한 칸 씩 움직이던 BFS를 '#'을 만날 때까지 움직이는 걸로 바꾸면 된다.
RED와 BLUE를 각각 움직이고, 둘 다 벽에 부딪혔을 떄, 계산을 끝낸다.
BLUE부터 움직이는 것이 추가 boolean flag 가 필요없이 수월하다, 왜냐하면 blue를 먼저 계산했는데, 구멍에 들어갔다면, 유효하지 않은 경우의 수임으로, red 구술 움직임부터 뒤의 계산은 할 필요가 없기 때문이다.
(3) 구슬 두 개가 하나의 좌표로 모이는 경우
현실에서는 벌어질 수 없는 일이지만, 우리는 구슬의 움직임을 (2)번과 같이 표현했기 떄문에, red와 blue가 일자 통로에 존재하는 경우, 같은 벽에 부딪히고, 같은 좌표에 놓이게 된다.
##########
#......RB#
##########이때는 사용했던 방향 배열의 값에 따라 답이 달라진다.
이제 예시를 통해 알아보자.
밑에 나오는 예시들은 기울이기 전 보드의 모습임을 유의하자.
A. 왼쪽으로 기울인 경우
##########
#......RB#
##########출발 시점에서 뒤에 있던 녀석이 늦게 도착한 것이므로, 한 칸 오른쪽으로 이동시킨다.
위의 예시에서는 R이 먼저 도착하고, B가 도착할 것이니, B가 오른쪽으로 이동해야한다.
B. 오른쪽으로 기울인 경우
##########
#RB......#
##########이 경우는 반대로, R이 왼쪽으로 한 칸 이동해야 할 것이다.
C. 아래로 기울인 경우
###
#R#
#B#
#.#
#.#
#.#
#.#
#.#
#.#
#.#
###이 경우는 늦게 도착한 쪽이 한 칸 위로 올라가야 한다. 위의 예시에서는 R이 맨 마지막에 와서는 위로 한 칸 움직일 것이다.
D. 위로 기울인 경우
###
#.#
#.#
#.#
#.#
#.#
#.#
#.#
#R#
#B#
###이제 감을 잡았을 것 같다. 위의 경우는 B를 한 칸 내려야 한다.
(4) 구멍에 구슬이 들어갔을 때 처리
- 중복적인 처리를 방지하기 위해 모든 조건을 무효화 시키는 BLUE 부터 계산한다.
- BLUE가 만약에 구멍에 빠지면, 현 계산은 즉시 종료하고 다음 경우의 수로 넘어간다.
- RED 계산은 이미 BLUE가 구멍에 안 들어갔음이 전제되었음으로, 들어간 경우, 지금까지의 움직임을 계산하여 답을 반환한다.
(1) 시간복잡도 분석 ⏳
- 10번의 움직임 이내로 계산되는 경우만 구하라고 하여서, 시간복잡도의 tight함을 요구하는 문제가 아니었다.
- 따라서 시간복잡도 분석은 생략하겠다.
3. 코드 🌐
(1) SUDO CODE 💬
0. 입력 받기
1. BFS 시작
(1) 현재 red 구슬과 blue 구슬을 하나씩 4개의 방향배열 끝까지 움직여보기
(2) 만약 BLUE가 구멍에 들어갔다면 현 계산을 종료하고 다음 경우의 수 계산으로 넘어간다.
(3) 만약 RED가 구멍에 들어갔다면 이제까지의 움직임 수를 저장하고 BFS를 종료한다.
(4) 아무것도 구멍에 들어가지 않았다면 다음을 계산한다.
a. 구슬이 같은 좌표에 있는지 확인 후, 사용한 방향 배열에 따라 올바른 위치로 조정
b. 이미 방문한 위치 조합이면 뒤의 계산 안하고 다음 경우의 수 계산으로 넘어가기
c. 현 위치 조합 방문 처리하고 bfs queue에 넣기(2) JAVA CODE ☕
import java.util.*;
import java.io.*;
public class Main {
static int R,C;
static int answer = Integer.MAX_VALUE;
static boolean [][][][] check;
static char [][] board;
static int [][] dir = new int [][] {{0,1},{0,-1},{1,0},{-1,0}}; // 동,서,남,북
static class Bead {
int rx;
int ry;
int bx;
int by;
int cnt;
public Bead() {
this.cnt = 0;
};
public Bead(int rx, int ry, int bx, int by) {
this.rx = rx;
this.ry = ry;
this.bx = bx;
this.by = by;
this.cnt = 0;
};
public Bead(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 static void main(String[] args) throws Exception {
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];
Bead start = new Bead();
for(int i = 0; i < R; i++){
String row = br.readLine();
for(int j = 0; j < C; j++){
board[i][j] = row.charAt(j);
if(board[i][j] == 'R') {start.rx = i; start.ry = j;}
if(board[i][j] == 'B') {start.bx = i; start.by = j;}
}
}
bfs(start);
System.out.println(answer>10? -1 : answer);
}
public static void bfs(Bead start) {
ArrayDeque<Bead> aq1 = new ArrayDeque<>();
check = new boolean [R][C][R][C];
check[start.rx][start.ry][start.bx][start.by] = true;
aq1.add(start);
while(!aq1.isEmpty()){
Bead now = aq1.poll();
LOOP:
for(int i = 0; i < 4; i++){
int nrx = now.rx;
int nry = now.ry;
int nbx = now.bx;
int nby = now.by;
int dx = dir[i][0];
int dy = dir[i][1];
while(!OOB(nbx+dx, nby+dy)){
nbx += dx;
nby += dy;
if(board[nbx][nby] == 'O') continue LOOP;
}
while(!OOB(nrx+dx, nry+dy)){
nrx += dx;
nry += dy;
if(board[nrx][nry] == 'O') {
answer = Math.min(answer, now.cnt+1);
return;
}
}
if(nrx == nbx && nry == nby) {
switch (i){
case 0: {
if(now.ry < now.by) nry -= 1;
else nby -= 1;
break;
}
case 1: {
if(now.ry < now.by) nby += 1;
else nry += 1;
break;
}
case 2: {
if(now.rx < now.bx) nrx -= 1;
else nbx -= 1;
break;
}
case 3: {
if(now.rx < now.bx) nbx += 1;
else nrx += 1;
break;
}
}
}
if(check[nrx][nry][nbx][nby]) continue;
check[nrx][nry][nbx][nby] = true;
aq1.add(new Bead(nrx, nry, nbx, nby, now.cnt+1));
}
}
}
private static boolean OOB(int r, int c){
return r < 0 || c < 0 || r >= R || c >= C || board[r][c] == '#';
}
}
4. 트러블 슈팅 or 배운 점📝
- 옛날 삼성 SW 역량테스트 문제였다는데… ㄷㄷㄷ 개어렵군…
