문제 이해 단계
https://www.acmicpc.net/problem/13460
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
NxM 크기의 맵이 존재하고, 빨간 구슬과 파란 구슬이 존재한다.
맵의 테두리는 모두 벽으로 막혀있고, 하나의 구멍이 존재한다.
목표는 파란 구슬은 구멍은 남겨둔 채, 빨간 구슬을 구멍을 통해 빼내는 것.
할 수 있는 동작은 상하좌우로 기울이는 것이다.
기울인다는 것은 해당 쪽에 벽에 닿을 때까지 쭉 흐른다는 것.
예를 들어, 오른쪽으로 기울이면 오른쪽 벽에 닿을 때까지 구슬이 굴러간다.
빨간 구슬과 파란 구슬은 동시에 움직인다.
그리고 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패로 간주한다.
해당 조건일 때, 최소 몇 번만에 성공할 수 있는지를 출력하는 문제.
만약 10번 이하로 성공할 수 없다면 -1을 출력하도록 한다.
'.' : 지나갈 수 있는 길
' # ' : 장애물 또는 벽
' 0 ' : 구멍
' R ' : 빨간 구슬
' B ' : 파란 구슬
문제 접근 단계
제한 사항으로부터 얻을 수 있는 힌트
제한사항부터 살펴보자.
맵의 크기 N, M은 최대 10x10까지 가능하다.
엄청나게 작은 것을 알 수 있다.
따라서 뭘 하든 간에 웬만하면 시간초과가 뜨지 않아서
문제를 푸는 방식에는 그다지 큰 제한을 두지 않아도 될 것 같다.
한마디로 완전 탐색이니, 백트래킹이니, O(N^2)니 심지어 N! 까지도 가능하다.
이 점을 잡고 넘어가자.
최단 경로? 가능한 경로?
NxM맵이 주어지기도 했고, 상하좌우로 기울이는 선택지가 존재한다.
그래서 처음에는 BFS가 떠올랐다. 어쨌거나 최소 동선으로 빨간 구슬을 빼내는 거니까..
근데 애초에 기울이다는 게 한 칸씩 이동하는 게 아니라,
벽에 위치에 따라서 2칸이 될 수도 3칸이 될 수도 있다.
그러다 보니 BFS로 최단거리를 구할 수 있는 게 맞긴 할까?
라는 생각이 들었다.
그래서 뭔가 다른 방법을 찾아야 한다.
그래서 맵의 크기도 작고, 완전탐색도 가능하니까
차라리 모든 경우의 수를 다 해보는 게 좋지 않나?
문제에서 친절하게 최대 10번이라고 제한도 해줬다.
그리고 한번 움직일 때 선택지도 상하좌우밖에 없다.
차라리 가능한 모든 패턴을 구한 뒤에,
그걸로 시뮬레이션을 돌려보자고 생각했다.
블로그에도 포스팅했지만,
이런 비슷한 문제를 다룬 적이 있었다.
아래에 링크를 달아두겠다. https://howudong.tistory.com/321
[C++] 백준 12100 - 2048(Easy) 큐를 이용한 풀이
문제 이해 단계 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며,
howudong.tistory.com
위 링크에서 기본적인 아이디어도 백트래킹을 통해 모든 패턴을 구하는 것부터 시작했다.
그래서 일단은 백트래킹으로 모든 패턴을 구하고 시작하자.
이 생각부터 시작했다.
구슬의 특징(어떤 공부터 먼저?)
여기서는 2개의 구슬이 존재한다.
게다가 구슬들은 각각 한 칸씩을 차지하고 겹치지 않아야 한다.
이 점이 문제를 어렵게 만든다.
2개의 구슬 중에 어떤 것부터 먼저 움직여야 할까?
이런 고민을 하는 이유가 아래와 같은 케이스가 나올 수 있기 때문이다.
오른쪽으로 기울였을 때, 빨간 구슬이 파란 구슬에게 한 칸 막혀야지만
나중에 구멍으로 나갈 수 있는 구조이다.
만약 여기서 움직이는 순서를 고려해주지 않거나,
한 칸씩 차지하고 있는 것을 체크해주지 않는다면,
빨간 구슬이 파란 구슬 위치에 있는 곳으로 들어가 버리는 상황이 벌어진다.
여기서는 파란 구슬을 움직인 다음, 빨간 구슬을 움직여야 한다.
그럼 무조건 파란 구슬 -> 빨간 구슬 순으로 움직여야 할까? 그렇지 않다.
위와 같은 구조는 빨간 구슬이 파란 구슬보다 먼저 이동해야 한다.
여기서 알 수 있는 점은 이동하는 방향과,
구슬의 위치를 고려해서 움직이는 우선순위를 정해야 한다는 것이다.
만약 오른쪽으로 이동한다고 하자.
(x, y)로 친다면 y좌표가 더 높은 쪽이 더 먼저 움직여야 한다.
그래야지 그 뒤에 있는 구슬이
바로 부딪히는 상황을 방지할 수 있기 때문이다.
기울였을 때 움직이기
이제 제일 중요한 것이 기울였을 때
움직이는 것을 어떻게 구현할까이다.
사실 시간복잡도가 크게 상관이 없기 때문에 BFS를 기반으로 반복문을 돌려줬다.
dx [] = {-1,1,0,0}
dy [] = {0,0,-1,1}
으로 해서 0 ~ 3으로 상하좌우를 나타낸다.
현재 위치에서 1칸 움직였을 때, 벽에 막히지 않는다면 1칸 더 움직인다.
그래도 벽에 막히지 않는다면 1칸 더 움직인다.
이를 반복한다.
벽에 막힌다면 벽에 막히기 이전까지
움직인 위치가 이동위치가 된다.
그리고 1칸씩 움직이다가 중간에 '0' 즉 구멍을 발견하면
공을 없애고 탈출했다는 플래그를 만들어준다.
이는 나중에 코드로 보는 것이 더 빠르기 때문에 코드로 처리하겠다.
물론 빨간 공이 탈출했다고 바로 끝내면 되는 것이 아니라,
파란 공도 해당 횟수까지는 시뮬레이션 돌려줘야 한다.
왜냐하면 동시에 탈출하면 실패로 간주하기 때문에,
파란 공도 탈출하는지 봐줘야 하기 때문이다.
이 문제는 그래프 탐색 문제이기도 하지만, 구현문제이기도 하다.
그래서 코드로 설명하는 것이 훨씬 낫다.
바로 문제 구현 단계로 가보자.
문제 구현 단계
vector<vector<int>> patterns; // 모든 패턴을 담을 벡터
// v : 현재까지 담은 움직임, vertical : 세로로 움직일까?
void getPattern(vector<int> v, bool vertical){
// 움직임이 10개가 되면 patterns에 저장하고 종료
if(v.size() >= 10) {
patterns.push_back(v);
return;
}
for(int i = 0; i < 4; i++){
// 세로로 움직일 때는 가로 움직임 고려 x
if(vertical && (i == 0 || i == 1)) continue;
// 가로로 움직일 때는 세로 움직임 고려 x
if(!vertical && (i == 2 || i == 3)) continue;
v.push_back(i);
// 이번에 세로로 움직였다면, 다음엔 가로로 움직이고
// 가로로 움직였다면, 다음엔 세로로
getPattern(v,!vertical);
v.pop_back();
}
}모든 패턴을 찾아서 patterns에 담는다.
백트래킹 방식을 사용하였다.
매개변수로 vertical로 가로와 세로인 것을 구분해 주는 이유는,
이전에 가로로 움직였다면 다시 가로로 움직일 필요가 없기 때문이다.
만약 오른쪽으로 기울였다고 가정해 보자.
다음에 왼쪽으로 기울이는 것은 이전 상태로 돌아가는 것이라 그냥 횟수 낭비이다.
그래서 최소 횟수를 구하는 것에서는 필요 없다.
그리고 오른쪽으로 가는 한번 더 가는 것은,
사실상 우리는 오른쪽으로 갈 수 있는 최대치를 갔기 때문에
한번 더 오른쪽으로 기울여봤자 움직일 수 없다.
즉, 유의미한 움직임을 할 수 있는 것은 위 또는 아래이다.
세로로 움직였을 때도 마찬가지이다.
#define INF 99999999
int N,M;
char map[11][11];
char cmap[11][11];
Point redBall;
Point blueBall;
Point ball[2];
// 해당 패턴에 해당하는 시뮬레이션 돌리기
int simulation(vector<int> pattern){
ball[0] = redBall;
ball[1] = blueBall;
memcpy(cmap,map,sizeof(map)); // 맵을 복사해둠
for(int i = 0; i < pattern.size(); i++){
int dir = pattern[i]; // 이번에 움직이는 방향
switch(dir){
// 위
case 0:
// x 좌표가 더 작은 것을 먼저 실행
if(ball[0].x > ball[1].x) swap(ball[0],ball[1]);
// 아래
break;
case 1:
// x 좌표가 더 큰 것을 먼저 실행
if(ball[0].x < ball[1].x) swap(ball[0],ball[1]);
break;
// y 좌표가 더 작은 것을 먼저 실행
case 2:
if(ball[0].y > ball[1].y) swap(ball[0],ball[1]);
break;
// y 좌표가 더 큰것을 먼저 실행
case 3:
if(ball[0].y < ball[1].y) swap(ball[0],ball[1]);
break;
}
// flag = -1 : 파란 공이 들어감, 0 : 아무 공도 들어가지 않음 1: 빨간 공만 들어감
int flag = move(ball,dir);
if(flag == -1) return INF;
else if(flag == 1) return i+1;
}
return INF;
}정해진 패턴을 가지고 실질적을 시뮬레이션을 돌리는 코드이다.
여기서 두 구슬 중 먼저 움직일 것의 우선순위를 정한다.
맵을 복사 해서 cmap으로 사용하는 이유는
시뮬레이션을 한 번만 돌리는 것이 아니기 때문,
우선순위는 방향에 따라 다른데,
이는 코드를 보는 것이 훨씬 빠르다.
우선순위가 정해졌으면 인덱스 0인 구슬부터 move라는 함수를 호출한다.
move함수는 -1,0,1을 반환하는데, 각각 위의 주석과 같은 의미를 가진다.
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
// 이동하는 코드
int move(Point ball[], int dir){
bool redGoal = false; // 빨간 공 들어갔는가
bool blueGoal = false; // 파란 공 들어갔는가
for(int k = 0; k < 2; k++){
int x = ball[k].x;
int y = ball[k].y;
int offset = 0; // 움직임 배수
char ch = cmap[x][y]; // 공의 색깔을 임시 저장
cmap[x][y] = '.'; // 공이 있던 자리를 .으로 초기화
// N과 M이 최대 10까지 이므로 10을 넘을 순 없음
for(int i = 1; i <= 10; i++){
int nx = x + dx[dir]*i;// 1 ~ 10까지 배수
int ny = y + dy[dir]*i;
if(nx < 1 || ny < 1 || nx > N || ny > M || cmap[nx][ny] == '#'
|| cmap[nx][ny] == 'R' || cmap[nx][ny] == 'B'){
// 벽을 만나면 그 배수 이전에 배수를 offset으로
offset = i-1;
break;
}
// 움직이던 중 구멍을 만나면
if(cmap[nx][ny] == 'O'){
// 해당 색의 goal을 true로 만듬
if(ch == 'R') redGoal = true;
if(ch == 'B') blueGoal = true;
break;
}
}
// 공이 들어간 경우, 아래의 작업은 하지 않음
if((redGoal && ch == 'R') || blueGoal && ch == 'B') continue;
// 움직인 칸을 구슬(R,B)로 치환
int nx = x + dx[dir]*offset;
int ny = y + dy[dir]*offset;
cmap[nx][ny]= ch;
ball[k] = {nx,ny};
}
// 파란 공이 들어갔을 때
if(blueGoal) return -1;
// 빨간 공만 들어가고 파란공은 들어가지 않음
else if(redGoal && !blueGoal) return 1;
return 0;
}위에서 설명한 일반적인 BFS에 i에 배수를 줘서 한 칸 두 칸 세 칸,
이런 식으로 한 번에 여러 칸을 건너가게 한다.
여기서 중요한 것은 어떤 공이 들어갔는지가 중요하기 때문에
빨간 공과 파란 공이 들어갔는지를 체크하는 변수를 각각 만든다.
움직일 때마다 해당 위치를 '. '으로 초기화하고
움직여서 도착한 곳을 구슬의 문자로 바꿔주는 작업을 반복한다.
자세한 것을 주석을 참고하도록 한다.
이상 핵심적은 코드에 대한 풀이는 여기까지이고,
전체 코드를 아래에 올리고 끝내도록 하겠다.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 99999999
struct Point{
int x,y;
};
struct Info{
int count;
int dir;
};
int N,M;
char map[11][11];
char cmap[11][11];
Point redBall;
Point blueBall;
Point ball[2];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
vector<vector<int>> patterns; // 모든 패턴을 담을 벡터
// v : 현재까지 담은 움직임, vertical : 세로로 움직일까?
void getPattern(vector<int> v, bool vertical){
// 움직임이 10개가 되면 patterns에 저장하고 종료
if(v.size() >= 10) {
patterns.push_back(v);
return;
}
for(int i = 0; i < 4; i++){
// 세로로 움직일 때는 가로 움직임 고려 x
if(vertical && (i == 0 || i == 1)) continue;
// 가로로 움직일 때는 세로 움직임 고려 x
if(!vertical && (i == 2 || i == 3)) continue;
v.push_back(i);
// 이번에 세로로 움직였다면, 다음엔 가로로 움직이고
// 가로로 움직였다면, 다음엔 세로로
getPattern(v,!vertical);
v.pop_back();
}
}
// 이동하는 코드
int move(Point ball[], int dir){
bool redGoal = false; // 빨간 공 들어갔는가
bool blueGoal = false; // 파란 공 들어갔는가
for(int k = 0; k < 2; k++){
int x = ball[k].x;
int y = ball[k].y;
int offset = 0; // 움직임 배수
char ch = cmap[x][y]; // 공의 색깔을 임시 저장
cmap[x][y] = '.'; // 공이 있던 자리를 .으로 초기화
// N과 M이 최대 10까지 이므로 10을 넘을 순 없음
for(int i = 1; i <= 10; i++){
int nx = x + dx[dir]*i;// 1 ~ 10까지 배수
int ny = y + dy[dir]*i;
if(nx < 1 || ny < 1 || nx > N || ny > M || cmap[nx][ny] == '#'
|| cmap[nx][ny] == 'R' || cmap[nx][ny] == 'B'){
// 벽을 만나면 그 배수 이전에 배수를 offset으로
offset = i-1;
break;
}
// 움직이던 중 구멍을 만나면
if(cmap[nx][ny] == 'O'){
// 해당 색의 goal을 true로 만듬
if(ch == 'R') redGoal = true;
if(ch == 'B') blueGoal = true;
break;
}
}
// 공이 들어간 경우, 아래의 작업은 하지 않음
if((redGoal && ch == 'R') || blueGoal && ch == 'B') continue;
// 움직인 칸을 구슬(R,B)로 치환
int nx = x + dx[dir]*offset;
int ny = y + dy[dir]*offset;
cmap[nx][ny]= ch;
ball[k] = {nx,ny};
}
// 파란 공이 들어갔을 때
if(blueGoal) return -1;
// 빨간 공만 들어가고 파란공은 들어가지 않음
else if(redGoal && !blueGoal) return 1;
return 0;
}
// 해당 패턴에 해당하는 시뮬레이션 돌리기
int simulation(vector<int> pattern){
ball[0] = redBall;
ball[1] = blueBall;
memcpy(cmap,map,sizeof(map)); // 맵을 복사해둠
for(int i = 0; i < pattern.size(); i++){
int dir = pattern[i]; // 이번에 움직이는 방향
switch(dir){
// 위
case 0:
// x 좌표가 더 작은 것을 먼저 실행
if(ball[0].x > ball[1].x) swap(ball[0],ball[1]);
// 아래
break;
case 1:
// x 좌표가 더 큰 것을 먼저 실행
if(ball[0].x < ball[1].x) swap(ball[0],ball[1]);
break;
// y 좌표가 더 작은 것을 먼저 실행
case 2:
if(ball[0].y > ball[1].y) swap(ball[0],ball[1]);
break;
// y 좌표가 더 큰것을 먼저 실행
case 3:
if(ball[0].y < ball[1].y) swap(ball[0],ball[1]);
break;
}
// flag = -1 : 파란 공이 들어감, 0 : 아무 공도 들어가지 않음 1: 빨간 공만 들어감
int flag = move(ball,dir);
if(flag == -1) return INF;
else if(flag == 1) return i+1;
}
return INF;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N >> M;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
cin >> map[i][j];
if(map[i][j] == 'B') blueBall = {i,j};
if(map[i][j] == 'R') redBall = {i,j};
}
}
// 가능한 모든 패턴 얻기
vector<int> tmp;
getPattern(tmp,true);
getPattern(tmp,false);
int ans = INF;
for(auto it : patterns) ans = min(ans,simulation(it));
if(ans != INF) cout << ans;
else cout << "-1";
}
시행착오
상당히 고려해야 할 점이 많은 그래프 탐색 문제이자 구현 문제였다.
처음에는 일반 BFS처럼 풀다가
아예 잘못 풀었다는 것을 깨닫고 처음부터 다시 풀었다.
거의 다 풀었을 때 AC를 받지 못했는데,
그 원인은 두 공이 동시에 들어가는 경우를 고려하지 못했다.
복잡하긴 했는데 그래도 해볼 만한 문제긴 했다.
생활비..