[백준] #13460. 구슬 탈출 2
문제는 여기서 확인할 수 있다. BaekJoon #13460. 구슬 탈출 2
📌 POINT
-
보드를 기울였을 때 빨간 구슬'만' 도착지에 도착하는가
-
10번의 시도 안에 성공한다면 몇 번만에 도착하는가
👉 이동 + 횟수 = BFS 알고리즘 -
주의할 점
- 조건 : Red, Blue는 같은 칸에 위치할 수 없다.
Red, Blue 공이 같은 line 상에 존재했고 굴린 결과 위치가 같아진다면 후 처리 필요
- 경로 중 도착지가 있는지 확인 필요
🚀 풀이
Ready
- Red, Blue 공의 위치 정보가 항상 묶여 다닐 예정. 가독성을 위해서라도 위치 정보를 담을 구조체를 미리 준비한다.
struct pos{
int x;
int y;
pos(int X, int Y) : x(X), y(Y) {}
};
- 지도, 보드 같은 경우에는 각 칸의 상태를 미리 숫자로 바꿔서 처리한다.(많은 경우 문자열 비교가 더 성가셨다.) 그리고 숫자로 바꾼 상태는 보기 쉽게
#define
해준다.
#define WALL -1
#define BLANK 0
#define HOLE 1
GO
1. 기본적인 BFS 틀을 만들어준다.
1.1. game_on 함수는 시작 시 공의 위치를 받아서 성공한다면 시도한 횟수를, 10번 이내 성공하지 못하면 -1을 리턴한다.
1.2. day별로 움직인 결과 red, blue의 위치 정보쌍을 큐에 담는다.
int game_on(pos start_red, pos start_blue){
queue<pair<pos, pos>> q;
q.push(make_pair(start_red, start_blue));
int day = 1;
bool hole_in = false;
for(; day<=10; day++){
int qsize = q.size();
for(int i=0; i<qsize; i++){
// tilt
pos red = q.front().first;
pos blue = q.front().second;
q.pop();
hole_in = tilt_board(red, blue, q);
if(hole_in) return day;
}
}
return -1;
}
2. 사방으로 이동
2.1. 이동 결과 목적지 도착 여부를 bool 타입으로 받는다.
2.2. red, blue 둘 다 도착하지 않았다면 큐에 담겨서 돌아온다.
bool tilt_board(pos &red, pos &blue, queue<pair<pos, pos>> &q){
if(tilt_left(red, blue, q)) return true;
if(tilt_right(red, blue, q)) return true;
if(tilt_up(red, blue, q)) return true;
if(tilt_down(red, blue, q)) return true;
return false;
}
3. 기울인 결과 저장
위 코드에서 봤듯이 위 아래 좌 우 함수를 따로 만들었다. 뭔가 합칠 수 있을 것 같지만... 일단 모르겠으니 아는 방법으로 작성했다.
3.1. 이동하고 도착 여부 조사
is_red_in = move(next_red, move_dir[0]);
is_blue_in = move(next_blue, move_dir[0]);
3.2. 같은 라인에 두 공이 존재했는지 > 이동 후에 겹쳐졌는지
// 같은 라인 상에 존재하는지
// right (방향에 따라 코드 차이 발생)
if(red.x == blue.x){
if(next_red.y == next_blue.y){
if(red.y < blue.y) next_red.y--;
else next_blue.y--;
}
}
3.3. 도착 여부 리턴
if(is_red_in && !is_blue_in) return true;
else if(!is_blue_in){
q.push(make_pair(next_red, next_blue));
}
return false
4. 보드를 기울였을 때 공 움직이기
move_dir
배열을 사용하면 코드가 한결 깔-끔
// right, left, down, up
int move_dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool move(pos &ball, int dir[]){
while(true){
pos next = ball;
next.x += dir[0];
next.y += dir[1];
if(board[next.x][next.y] == HOLE){
return true;
}
else if(board[next.x][next.y] == BLANK){
ball = next;
}
else { // WALL
return false;
}
}
}
주저리
삼성 SW 역량 테스트를 약 일주일 앞두고 기출 풀이를 시작한다. 기출에서 크게 벗어나는 알고리즘은 나오지 않는다는 후기가 많아서 매일 스터디 진행하고 풀이를 정리하는 것이 도움이 될 것 같다. 오늘부터 매일 한문제씩!!
Author And Source
이 문제에 관하여([백준] #13460. 구슬 탈출 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mttw2820/백준-13460.-구슬-탈출-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)