https://www.acmicpc.net/problem/13460
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
최종 풀이
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ13460_1
//
// Created by Hwayeon on 2021/10/17.
//
#include <iostream>
#include <queue>
using namespace std;
int N, M;
char board[10][10] = {'.',};
int visit[10][10][10][10] = {0, };
struct State{
int rx;
int ry;
int bx;
int by;
int cnt = 0;
};
State st;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
queue<State> q;
void move(int& x, int& y, int& dis, int& d){
while(board[y+dy[d]][x+dx[d]] != '#' && board[y][x] != 'O'){
x += dx[d];
y += dy[d];
dis ++;
}
}
void bfs(){
while(!q.empty()){
int rx = q.front().rx;
int ry = q.front().ry;
int bx = q.front().bx;
int by = q.front().by;
int cnt = q.front().cnt;
q.pop();
if(cnt >= 10) break;
for(int d=0; d<4; d++){
int nrx = rx;
int nry = ry;
int r_dis = 0;
int nbx = bx;
int nby = by;
int b_dis = 0;
int ncnt = cnt+1;
move(nrx, nry, r_dis, d);
move(nbx, nby, b_dis, d);
if(board[nby][nbx] == 'O') continue;
if(board[nry][nrx] == 'O'){
cout << ncnt << endl;
return;
}
if(nrx == nbx && nry == nby){
if(r_dis > b_dis){
nrx -= dx[d];
nry -= dy[d];
}
else{
nbx -= dx[d];
nby -= dy[d];
}
}
if(visit[nrx][nry][nbx][nby]) continue;
visit[nrx][nry][nbx][nby] = 1;
q.push({nrx, nry, nbx, nby, ncnt});
}
}
cout << -1 << endl;
}
int main(int argc, const char * argv[]) {
cin >> N >> M;
for(int y=0; y<N; y++){
for(int x=0; x<M; x++){
cin >> board[y][x];
if(board[y][x] == 'R'){
st.rx = x;
st.ry = y;
board[y][x] = '.';
}
else if(board[y][x] == 'B'){
st.bx = x;
st.by = y;
board[y][x] = '.';
}
}
}
q.push(st);
visit[st.rx][st.ry][st.bx][st.by] = 1;
bfs();
return 0;
}풀이 과정
방향에 따라, 그리고 빨간 구슬과 파란 구슬의 위치에 따라 각각 나눠서 처리해줬는데 테스트케이스는 맞았지만, 자꾸 틀렸습니다가 나왔다...
모든 경우에 대해 코드를 작성하다보니 복잡하기도 했고, 내 한계에 머물러있는 코딩 실력을 뛰어넘기 위해 다른 사람의 코드를 참고해보기로 결정했다.
bfs 알고리즘으로 간단하게 해결할 수 있었던 문제였고 덕분에 배울 수 있었다!!
핵심은 일단 빨간 구슬과 파란 구슬을 구멍에 빠지거나 벽을 만나기 직전까지 움직이고, 두 구슬이 같은 위치에 있을 때 거리값을 비교해서 더 많이 움직인 구슬을 한 칸 뒤로 물러주는 것이다!!
이는, 코드를 보며 이해하는 것이 더 좋을 것이니 아래 코드와 주석을 확인해보자
#include <iostream>
#include <queue>
using namespace std;
int N, M;
char board[10][10] = {'.',};
//두 구슬의 위치 조합을 중복해서 탐색하지 않기 위해 조합에 대한 방문처리를 한다
//visit[rx][ry][bx][by] = 1 -> 이전에 빨간구슬 = (rx, ry), 파란구슬 = (bx, by)의 위치 조합을 탐색한 경우
//visit[rx][ry][bx][by] = 1 -> 아직 빨간구슬 = (rx, ry), 파란구슬 = (bx, by)의 위치 조합을 탐색하지 않은 경우
int visit[10][10][10][10] = {0, };
struct State{
//빨간 구슬의 위치
int rx;
int ry;
//파란 구슬의 위치
int bx;
int by;
//움직인 횟수
int cnt = 0;
};
State st;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
queue<State> q;
void move(int& x, int& y, int& dis, int& d){
//구슬이 구멍에 빠지지 않았고, 구슬의 다음 칸이 벽이 아닌 경우, 계속 d 방향으로 이동한다
while(board[y+dy[d]][x+dx[d]] != '#' && board[y][x] != 'O'){
x += dx[d];
y += dy[d];
//이동 거리 1 증가
dis ++;
}
}
void bfs(){
while(!q.empty()){
//현재 구슬의 위치와 이동 횟수를 담는다
int rx = q.front().rx;
int ry = q.front().ry;
int bx = q.front().bx;
int by = q.front().by;
int cnt = q.front().cnt;
q.pop();
//이미 10번 이상 이동하였는데 구슬이 탈출하지 못한 경우, 실패
if(cnt >= 10) break;
//4 방향에 대한 구슬 이동
for(int d=0; d<4; d++){
int nrx = rx;
int nry = ry;
//빨간 구슬이 이동한 거리
int r_dis = 0;
int nbx = bx;
int nby = by;
//파란 구슬이 이동한 거리
int b_dis = 0;
//이동 횟수 1 증가
int ncnt = cnt+1;
//빨간 구슬을 d 방향으로 이동시킨다
move(nrx, nry, r_dis, d);
//파란 구슬을 d 방향으로 이동시킨다
move(nbx, nby, b_dis, d);
//파란 구슬이 구멍에 빠진 경우, 더이상 이어나가지 않는다
if(board[nby][nbx] == 'O') continue;
//빨간 구슬만 구멍에 빠진 경우, 해당 이동 횟수가 가장 최소 이동 횟수이므로, 출력 후 함수를 종료한다
if(board[nry][nrx] == 'O'){
cout << ncnt << endl;
return;
}
//파란 구슬과 빨간 구슬이 구멍에 빠지지 않은 경우,
//파란 구슬과 빨간 구슬의 위치가 같은 경우, 위치 조정이 필요하다
if(nrx == nbx && nry == nby){
//빨간 구슬이 이동한 거리가 더 큰 경우, 빨간 구슬을 뒤로 한 칸 이동시킨다
if(r_dis > b_dis){
nrx -= dx[d];
nry -= dy[d];
}
//파란 구슬이 이동한 거리가 더 큰 경우, 파란 구슬을 뒤로 한 칸 이동시킨다
else{
nbx -= dx[d];
nby -= dy[d];
}
}
//새로운 구슬 위치의 조합을 이전에 탐색한 적이 있는 경우, 더이상 진행하지 않는다
if(visit[nrx][nry][nbx][nby]) continue;
//새로운 구슬 위치의 조합인 경우, 방문처리 후 큐에 추가한다
visit[nrx][nry][nbx][nby] = 1;
q.push({nrx, nry, nbx, nby, ncnt});
}
}
//10번 이하의 구슬 이동으로 탈출하지 못한 경우, 실패
cout << -1 << endl;
}
int main(int argc, const char * argv[]) {
cin >> N >> M;
for(int y=0; y<N; y++){
for(int x=0; x<M; x++){
cin >> board[y][x];
//빨간 구슬인 경우, st에 위치를 담고 빈 칸으로 바꾼다
if(board[y][x] == 'R'){
st.rx = x;
st.ry = y;
board[y][x] = '.';
}
//파란 구슬인 경우, st에 위치를 담고 빈 칸으로 바꾼다
else if(board[y][x] == 'B'){
st.bx = x;
st.by = y;
board[y][x] = '.';
}
}
}
//현재 두 구슬의 상태 큐에 담고, 구슬의 위치 조합을 방문 처리한다
q.push(st);
visit[st.rx][st.ry][st.bx][st.by] = 1;
//구슬 탈출 시작
bfs();
return 0;
}이전 풀이
풀이 시간 3시간 42분
이 문제는 구현+BFS를 활용하여 해결했다. 그래서 구현 과정이 까다로웠고 풀이 시간이 오래 걸렸고 구현 후 제출한 결과 실패도 ㅁㅏㄴㅎ았다. 이 과정 끝에 나는 마침내 문제를 해결했고 그 풀이를 아래에 차근차근 설명해보겠다.
1. 전역 변수 선언
int N, M;
char board[10][10];
bool visit[10][10][10][10] = {false, };
int answer = 11;
struct location{
int x;
int y;
};
location r_loc, b_loc, h_loc;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};먼저, 전역변수로 보드의 세로 크기 N, 가로 크기 M, 보드 board를 선언한다.
visit[10][10][10][10]를 빨간 공과 파란 공의 위치의 조합이 중복되는지 아닌지를 판별하기 위해 선언하고 모든 요소는 false로 초기화 해준다. 자세한 설명은 아래 구슬 탈출을 진행하는 과정에서 설명하도록 하겠다.
결과값인 answer은 문제에서 10번 이하로 움직여 빨간 구슬을 빼낼 수 있는 최소 횟수를 출력하라고 했기 때문에 11로 초기화 한다.
구조체를 활용하여 위치를 나타내는 location을 만들고, 빨간 구슬, 파란 구슬, 구멍의 위치를 담을 r_loc, b_loc, h_loc을 선언한다.
구슬은 상, 하, 좌, 우로만 움직이기 때문에 dx[4], dy[4]를 위와 같이 선언하였다.
2. 입력 받아오기
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> board[i][j];
if(board[i][j] == 'B'){
board[i][j] = '.';
b_loc.x = j;
b_loc.y = i;
}
else if(board[i][j] == 'R'){
board[i][j] = '.';
r_loc.x = j;
r_loc.y = i;
}
else if(board[i][j] == 'O'){
h_loc.x = j;
h_loc.y = i;
}
}
}board에 입력값들을 넣어준다. 이때, 입력 값이 'R'과 'B'인 경우, '.'로 board에 넣어준다. 그리고 전역변수로 선언한 r_loc과 b_loc에 현재 빨간 구슬과 파란 구슬의 위치를 저장해준다. 'O'인 경우에는 h_loc에 위치를 저장해준다.(board에는 그대로 'O'를 넣어준다.)
3. escape_bead(), BFS
이제, 구슬 탈출 게임을 구현해보자. 구슬 탈출 게임은 간단히 말해, 빨간 구슬과 파란 구슬을 동시에 기울인 방향으로 움직이 멈출 때까지 기울이는 동작을 진행하여 빨간 공만 구멍에 탈출시키는 것이다. 현재 빨간 구슬과 파란 구슬의 위치에서 상, 하, 좌, 우 중에 기울이는 방향을 선택하여 구슬을 이동시키고, 그 위치에서 다시 상, 하, 좌, 우 중 한 방향으로 기울여 구슬을 이동시켜 나가야 한다는 점에서 BFS로 구현하기로 하였다.
이 때, 중요한 점은 처음에 왼쪽으로 기울였다면, 두번째로 오른쪽으로 기울이지 않아도 된다는 점이다. 왜냐하면 다시 오른쪽으로 기울이면 처음 상황으로 다시 돌아가기 때문에 의미 없는 반복이 이뤄지기 때문이다. 이를 방지하기 위해 위에서 visit[10][10][10][10]를 선언한 것이다. 탐색이 시작되는 빨간 구슬의 위치와 파란 구슬의 위치는 queue<pair<pair<location, location>, int>> q에 담겨지며, 담기 전에 해당 빨간 구슬과 파란 구슬의 위치의 조합이 이전에 탐색되었는지를 visit배열을 통해 체크하고, 탐색된 적이 없다면 q에 담아주는 것이다. queue<pair<pair<location, location>, int>> q는 (빨간 구슬의 위치, 파란 구슬의 위치, cnt)로 이루어진다.
여기서 cnt의 역할은 현재 담긴 빨간 구슬과 파란 구슬의 위치가 몇 번 기울인 이후의 위치인지를 알 수 있게 해준다.
그럼 아래에서 구체적인 구현 방법을 살펴보자.
void escape_bead(){
int cnt = 0;
queue<pair<pair<location, location>, int>> q;
q.push(make_pair(make_pair(r_loc, b_loc), cnt));
while(cnt < 10 && !q.empty()){
location r = q.front().first.first;
location b = q.front().first.second;
cnt = q.front().second;
visit[r.y][r.x][b.y][b.x] = true;
q.pop();
for(int i=0; i<4; i++){
r_loc.x = r.x;
r_loc.y = r.y;
b_loc.x = b.x;
b_loc.y = b.y;
int new_rx = r.x + dx[i];
int new_ry = r.y + dy[i];
int new_bx = b.x + dx[i];
int new_by = b.y + dy[i];
while((board[new_ry][new_rx]=='.' && !(new_rx==b_loc.x && new_ry==b_loc.y)) || (board[new_by][new_bx]=='.' && !(new_bx==r_loc.x && new_by==r_loc.y))){
if(board[new_ry][new_rx]=='.' && !(new_rx==b_loc.x && new_ry==b_loc.y)){
r_loc.x = new_rx;
r_loc.y = new_ry;
new_rx += dx[i];
new_ry += dy[i];
}
if(board[new_by][new_bx]=='.' && !(new_bx==r_loc.x && new_by==r_loc.y)){
b_loc.x = new_bx;
b_loc.y = new_by;
new_bx += dx[i];
new_by += dy[i];
}
}
if(board[new_ry][new_rx] == '#' || (new_rx==b_loc.x && new_ry==b_loc.y)){
if(board[new_by][new_bx] == '#' || (new_bx==r_loc.x && new_by==r_loc.y)){
if(!visit[new_ry - dy[i]][new_rx - dx[i]][new_by - dy[i]][new_bx - dx[i]]){
location new_r, new_b;
new_r.x = new_rx-dx[i];
new_r.y = new_ry-dy[i];
new_b.x = new_bx-dx[i];
new_b.y = new_by-dy[i];
q.push(make_pair(make_pair(new_r, new_b), cnt+1));
}
}
}
else if(board[new_ry][new_rx] == 'O'){
if(board[new_by+dy[i]][new_bx+dx[i]] != 'O'){
if(answer == -1) answer = cnt+1;
else{
if(cnt+1 < answer) answer = cnt+1;
}
}
}
}
}
if(answer == 11) answer = -1;
}
- q 초기화
int cnt = 0;
queue<pair<pair<location, location>, int>> q;
q.push(make_pair(make_pair(r_loc, b_loc), cnt));처음 빨간 구슬과 파란 구슬의 위치와 cnt = 0을 q에 push한다.
- BFS 탐색
1) q의 front에 담긴 빨간 구슬의 위치와 파란 구슬의 위치를 location r, b에 넣어주고, cnt를 설정한다. 이 때, 현재 빨간 구슬과 파란 구슬의 위치를 탐색할 것이므로 visit[r.y][r.x][b.y][b.x] = true한 후, q.pop() 해준다.
이 과정은 기울임이 10번 이하이고(cnt < 10), 구슬이 또 움직일 수 있으면(!q.empty()) 반복된다.
while(cnt < 10 && !q.empty()){
location r = q.front().first.first;
location b = q.front().first.second;
cnt = q.front().second;
visit[r.y][r.x][b.y][b.x] = true;
q.pop();
2) for문을 통해 상, 하, 좌, 우로 구슬을 움직이며 탐색한다.
for(int i=0; i<4; i++){
r_loc.x = r.x;
r_loc.y = r.y;
b_loc.x = b.x;
b_loc.y = b.y;
int new_rx = r.x + dx[i];
int new_ry = r.y + dy[i];
int new_bx = b.x + dx[i];
int new_by = b.y + dy[i];
while((board[new_ry][new_rx]=='.' && !(new_rx==b_loc.x && new_ry==b_loc.y)) || (board[new_by][new_bx]=='.' && !(new_bx==r_loc.x && new_by==r_loc.y))){
if(board[new_ry][new_rx]=='.' && !(new_rx==b_loc.x && new_ry==b_loc.y)){
r_loc.x = new_rx;
r_loc.y = new_ry;
new_rx += dx[i];
new_ry += dy[i];
}
if(board[new_by][new_bx]=='.' && !(new_bx==r_loc.x && new_by==r_loc.y)){
b_loc.x = new_bx;
b_loc.y = new_by;
new_bx += dx[i];
new_by += dy[i];
}
}이 때, 기울인 방향으로 구슬은 움직임이 없을 때까지 이동되기 때문에, while문을 활용해 구현한다. while문은 빨간 구슬의 위치가 보드의 '.' 이면서 파란 구슬의 위치와 같지 않아서(두 구슬은 같은 곳에 위치할 수 없다.), 더 굴러 갈 수 있음을 의미하거나, 파란구슬의 위치가 보드의 '.' 이면서 빨간 구슬의 위치와 같지 않을 때까지 반복된다.
이는 [1] 빨간 구슬과 파란 구슬이 둘 다 움직일 수 있음, [2] 파란 구슬은 못 움직이지만 빨간 구슬은 움직일 수 있음, [3] 빨간 구슬은 못 움직이지만 파란 구슬은 움직일 수 있음. 이 세가지 경우 중 하나라면 while문이 반복된다.
반복되는 동안, 빨간 구슬과 파란 구슬의 위치가 달라지면 r_loc과 b_loc를 업데이트 해준다.
3) 빨간 구슬과 파란 구슬 모두 움직임이 멈춘 경우 아래 조건문을 실행한다.
if(board[new_ry][new_rx] == '#' || (new_rx==b_loc.x && new_ry==b_loc.y)){
if(board[new_by][new_bx] == '#' || (new_bx==r_loc.x && new_by==r_loc.y)){
if(!visit[new_ry - dy[i]][new_rx - dx[i]][new_by - dy[i]][new_bx - dx[i]]){
location new_r, new_b;
new_r.x = new_rx-dx[i];
new_r.y = new_ry-dy[i];
new_b.x = new_bx-dx[i];
new_b.y = new_by-dy[i];
q.push(make_pair(make_pair(new_r, new_b), cnt+1));
}
}
}
else if(board[new_ry][new_rx] == 'O'){
if(board[new_by+dy[i]][new_bx+dx[i]] != 'O'){
if(answer == -1) answer = cnt+1;
else{
if(cnt+1 < answer) answer = cnt+1;
}
}
}먼저, 두 구슬의 위치가 [1] 벽인 경우, [2] 다른 구슬의 위치와 같을 경우, [3] 구멍의 위치와 같은 경우, 이 세 가지의 경우 중 하나에 해당하면 위의 while문에서 빠져나오게 된다. 따라서, 해당 경우에 따른 조건문을 구현해야한다.
두 구슬이 모두 [1]이나 [2]인 경우는 해당 위치에서 또 다시 상, 하, 좌, 우로 기울여봐야 한다.
따라서, visit[new_ry - dy[i]][new_rx - dx[i]][new_by - dy[i]][new_bx - dx[i]]인 경우(두 구슬의 위치 조합이 탐색이 된 적이 없는 경우)에 new_r.x, new_b.x를 각각 -dx[i] 해주고, new_r.y, new_b.y를 -dy[i] 하여 한 칸 전으로 이동시킨다. 이를 q.push(make_pair(make_pair(new_r, new_b), cnt+1)) 하여 다음 탐색이 이뤄질 수 있도록 한다.
빨간 구슬이 [3]인 경우는 파란 구슬도 구멍에 빠졌는지 아닌지를 따져줘야한다. 파란 구슬이 구멍에 빠지지 않았다면 게임에 성공했으므로, answer값을 cnt+1로 업데이트 해준다.
이 과정이 반복되어 cnt가 10 초과이면서 구슬 탈출에 성공한 적이 없다면 if(answer == 11), answer = -1 해준다.
참고
[알고리즘] BFS와 DFS
BFS와 DFS는 가능한 모든 경우의 수를 탐색하는 완전 탐색 알고리즘이다. BFS는 Breadth-First Search로 너비 우선 탐색을 의미하고 자료구조는 Queue를 사용한다. DFS는 Depth-First Search로 깊이 우선 탐색..
hwayomingdlog.tistory.com
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 13458 시험 감독 C++ (0) | 2021.06.30 |
|---|---|
| 백준 14891 톱니바퀴 C++ (0) | 2021.01.22 |
| 백준 14888 연산자 끼워넣기 C++ (0) | 2021.01.17 |
| 백준 14890 경사로 C++ (0) | 2021.01.14 |
| 백준 14502 연구소 C++ (0) | 2021.01.11 |