문제
https://www.acmicpc.net/problem/13460
이해
NxM 보드에는 빨간색, 파란색 구슬이 1개씩 있다. 보드를 기울여 구슬을 굴릴 수 있다. 왼쪽으로 기울면 모든 구슬이 왼쪽 끝으로 간다.
보드에는 구멍이 1개가 있다. 게임의 목적은 구슬을 굴려서 빨간색 구슬만 구멍으로 빼내야 한다.
최소한으로만 움직여서 빨간색 구슬을 빼낼 때 최소 횟수를 출력해야 한다. 빼낼 수 없다면 -1을 출력한다.
접근
시뮬레이션과 탐색이 합쳐진 문제라고 생각했다. 기본적인 BFS로 빨간구슬과 파란구슬의 방문여부를 체크해야 한다. 한 가지 특이한 점은 본래의 보드 탐색 문제는 1칸씩 움직이지만 본 문제는 기울이기 때문에 보드의 끝으로 이동한다.
또한 2개의 구슬은 같은 위치에 있을 수 없으며 동시에 움직인다. 이 동작의 시뮬레이션을 구현하는 것이 문제의 핵심이다.
[기울이기]
동시에 움직이며 같은 위치에 있을 수 없기 때문에 구슬의 위치 관계를 고려해서 움직여야 한다.
만일 위로 움직인다고 하면 위치한 열이 겹칠 이유가 없기 때문에 단순하게 움직이면 된다. 하지만 열이 같다면 당연하게도 작은 행에 위치한 구슬이 먼저 움직여야 한다. 이를 고려한 분기문을 작성해야 한다.
[구슬은 구멍으로 빠져나간다]
위 같은 시뮬레이션에서 벽이나 다른 구슬과 맞닿으면 그 전 위치에서 정지하지만 구멍을 만나면 빠져나간다. 구슬 1개라도 빠져나가면 성공 혹은 실패이기 때문에 분기를 종료한다.
풀이
[방향에 따른 구슬 우선순위 결정]
class Node {
public:
xy r;
xy b;
bool directionCheck(int d) const {
switch (d) {
case 0:
return r.x < b.x;
case 1:
return r.y > b.y;
case 2:
return r.x > b.x;
case 3:
return r.y < b.y;
default:
return false;
}
}
};Node는 BFS의 큐에 들어갈 클래스이다. directionCheck 함수는 방향에 따라 r, b 구슬의 우선순위를 결정한다.
Node getNextNode(Node cur, int d) {
xy nextR = cur.r;
xy nextB = cur.b;
if (cur.directionCheck(d)) {
while (true) {
int nx = nextR.x + dir[0][d];
int ny = nextR.y + dir[1][d];
if (board[nx][ny] == 'O') {
nextR.x = nx;
nextR.y = ny;
break;
} else if (board[nx][ny] != '.') {
board[nextR.x][nextR.y] = '#';
break;
}
nextR.x = nx;
nextR.y = ny;
}
while (true) {
int nx = nextB.x + dir[0][d];
int ny = nextB.y + dir[1][d];
if (board[nx][ny] == 'O') {
nextB.x = nx;
nextB.y = ny;
break;
} else if (board[nx][ny] != '.') {
board[nextB.x][nextB.y] = '#';
break;
}
nextB.x = nx;
nextB.y = ny;
}
} else {
while (true) {
int nx = nextB.x + dir[0][d];
int ny = nextB.y + dir[1][d];
if (board[nx][ny] == 'O') {
nextB.x = nx;
nextB.y = ny;
break;
} else if (board[nx][ny] != '.') {
board[nextB.x][nextB.y] = '#';
break;
}
nextB.x = nx;
nextB.y = ny;
}
while (true) {
int nx = nextR.x + dir[0][d];
int ny = nextR.y + dir[1][d];
if (board[nx][ny] == 'O') {
nextR.x = nx;
nextR.y = ny;
break;
} else if (board[nx][ny] != '.') {
board[nextR.x][nextR.y] = '#';
break;
}
nextR.x = nx;
nextR.y = ny;
}
}
board[nextR.x][nextR.y] = '.';
board[nextB.x][nextB.y] = '.';
board[hole.x][hole.y] = 'O';
return {nextR, nextB};
}굉장히 더러운 코드이다. 위의 함수를 사용해서 우선순위대로 구슬을 굴린다. 기본적으로 while 루프를 사용하고 벽이나 다른 구슬을 만나면 멈춘다. 예외사항으로 구멍을 만나면 해당 위치로 초기화하고 루프를 멈춘다.
함수를 종료할 땐 보드를 원복한다.
[BFS]
int bfs() {
queue<Node> q;
q.push({r, b});
visited[r.x][r.y][b.x][b.y] = true;
int round = 0;
while (q.size() > 0 && round < 10) {
int size = q.size();
while (size-- > 0) {
Node cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
Node nextNode = getNextNode(cur, i);
if (visited[nextNode.r.x][nextNode.r.y][nextNode.b.x][nextNode.b.y]) continue;
bool rf = hole == nextNode.r ? true : false;
bool bf = hole == nextNode.b ? true : false;
if (bf) {
continue;
} else if (rf) {
return round + 1;
}
visited[nextNode.r.x][nextNode.r.y][nextNode.b.x][nextNode.b.y] = true;
q.push(nextNode);
}
}
round++;
}
return -1;
}BFS는 Node 클래스 큐를 활용한다. 방문처리는 4차원 배열을 사용했다. round는 최대 10번만 진행하기 때문에 while문의 조건으로 포함시켰다.
다음 노드를 판단할 때는 구멍 위치를 비교해서 어떤 구슬이 빠져나갔는지 체크한다.
코드
#include <iostream>
#include <queue>
#include <string>
using namespace std;
class xy {
public:
int x;
int y;
bool operator==(const xy &other) const {
return x == other.x && y == other.y;
}
};
class Node {
public:
xy r;
xy b;
bool directionCheck(int d) const {
switch (d) {
case 0:
return r.x < b.x;
case 1:
return r.y > b.y;
case 2:
return r.x > b.x;
case 3:
return r.y < b.y;
default:
return false;
}
}
};
const int dir[2][4] = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
int N, M;
char board[10][10];
bool visited[10][10][10][10];
xy hole;
xy r, b;
void init() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
string s;
cin >> s;
for (int j = 0; j < M; j++) {
board[i][j] = s[j];
if (board[i][j] == 'O') {
hole.x = i;
hole.y = j;
} else if (board[i][j] == 'R') {
r.x = i;
r.y = j;
board[i][j] = '.';
} else if (board[i][j] == 'B') {
b.x = i;
b.y = j;
board[i][j] = '.';
}
}
}
}
Node getNextNode(Node cur, int d) {
xy nextR = cur.r;
xy nextB = cur.b;
if (cur.directionCheck(d)) {
while (true) {
int nx = nextR.x + dir[0][d];
int ny = nextR.y + dir[1][d];
if (board[nx][ny] == 'O') {
nextR.x = nx;
nextR.y = ny;
break;
} else if (board[nx][ny] != '.') {
board[nextR.x][nextR.y] = '#';
break;
}
nextR.x = nx;
nextR.y = ny;
}
while (true) {
int nx = nextB.x + dir[0][d];
int ny = nextB.y + dir[1][d];
if (board[nx][ny] == 'O') {
nextB.x = nx;
nextB.y = ny;
break;
} else if (board[nx][ny] != '.') {
board[nextB.x][nextB.y] = '#';
break;
}
nextB.x = nx;
nextB.y = ny;
}
} else {
while (true) {
int nx = nextB.x + dir[0][d];
int ny = nextB.y + dir[1][d];
if (board[nx][ny] == 'O') {
nextB.x = nx;
nextB.y = ny;
break;
} else if (board[nx][ny] != '.') {
board[nextB.x][nextB.y] = '#';
break;
}
nextB.x = nx;
nextB.y = ny;
}
while (true) {
int nx = nextR.x + dir[0][d];
int ny = nextR.y + dir[1][d];
if (board[nx][ny] == 'O') {
nextR.x = nx;
nextR.y = ny;
break;
} else if (board[nx][ny] != '.') {
board[nextR.x][nextR.y] = '#';
break;
}
nextR.x = nx;
nextR.y = ny;
}
}
board[nextR.x][nextR.y] = '.';
board[nextB.x][nextB.y] = '.';
board[hole.x][hole.y] = 'O';
return {nextR, nextB};
}
int bfs() {
queue<Node> q;
q.push({r, b});
visited[r.x][r.y][b.x][b.y] = true;
int round = 0;
while (q.size() > 0 && round < 10) {
int size = q.size();
while (size-- > 0) {
Node cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
Node nextNode = getNextNode(cur, i);
if (visited[nextNode.r.x][nextNode.r.y][nextNode.b.x][nextNode.b.y]) continue;
bool rf = hole == nextNode.r ? true : false;
bool bf = hole == nextNode.b ? true : false;
if (bf) {
continue;
} else if (rf) {
return round + 1;
}
visited[nextNode.r.x][nextNode.r.y][nextNode.b.x][nextNode.b.y] = true;
q.push(nextNode);
}
}
round++;
}
return -1;
}
int solution() {
int ret = bfs();
return ret;
}
int main() {
init();
int ans = solution();
cout << ans;
}결과
SW 0년차 개발자입니다.