[삼성코테기출문제]구슬탈출 2
구슬탈출 2
1. 문제 설명 및 풀이
상반기 코테 준비할 때 남은 시간이 한 달 안되는 시간이라 삼성sw역량테스트는 BFS/DFS가 많이 나온다는 친구의 말에 BFS/DFS위주로 공부를 했어서 어느정도 수준의 BFS/DFS문제는 쉽게 풀 것이라고 자만하고있었다가 어려워서 혼났던 문제이다. 생각보다 까다로운 조건들이 많았고 그 조건들을 코드로 옮기는 것이 어려웠다.
입력 조건
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다.
다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다.
이 문자열은 ‘.’, ‘#’, ‘O’, ‘R’, ‘B’ 로 이루어져 있다. ‘.’은 빈 칸을 의미하고, ‘#’은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, ‘O’는 구멍의 위치를 의미한다. ‘R’은 빨간 구슬의 위치, ‘B’는 파란 구슬의 위치이다.
입력되는 모든 보드의 가장자리에는 모두 ‘#’이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
출력 조건
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
이 문제의 key point는 동시에 움직이고 최단거리 이다.
int N, M;
char Map[MAX_N][MAX_N];
bool Visit[MAX_N][MAX_N][MAX_N][MAX_N]; //두 구슬을 동시에 방문체크 하기 위함
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
//두 구슬이 동시에 움직이므로 묶어서 관리
typedef struct Pos {
int rx, ry;
int bx, by;
int step;
};
두 구슬이 동시에 움직이므로 처음 맵정보를 입력 받을 때 빨간구슬과 파란구슬의 위치를 큐에 push한다.
그리고 방문체크
void Input() {
int rx, ry, bx, by;
scanf("%d%d\n", &N, &M);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%c", &Map[i][j]);
if (Map[i][j] == 'R')rx = j, ry = i;
if (Map[i][j] == 'B')bx = j, by = i;
}
scanf("\n");
Map[i][M] = '\0';
}
push(rx, ry, bx, by, 0);
Visit[ry][rx][by][bx] = true;
}
구슬이 한 칸씩 움직이는 것이 아니므로 기울였을때 한 방향으로 벽을 만날때까지 구슬이 움직이는
move함수를 만들어 준다.
void Move(int &x, int &y, int &c, int dy, int dx) {
while (Map[y + dy][x + dx] != '#'&&Map[y][x] != 'O') {
x += dx;
y += dy;
c +=1;
}
}
전체 코드
#include<cstdio>
const int MAX_N = 11;
const int MAX_Q = 11 * 11 * 2;
int N, M;
char Map[MAX_N][MAX_N];
bool Visit[MAX_N][MAX_N][MAX_N][MAX_N]; //두 구슬을 동시에 방문체크 하기 위함
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
//두 구슬이 동시에 움직이므로 묶어서 관리
typedef struct Pos {
int rx, ry;
int bx, by;
int step;
};
Pos Q[MAX_Q];
int f, r;
void push(int rx, int ry,int bx,int by,int s) {
Q[r++] = { rx,ry,bx,by,s };
}
Pos pop() {
return Q[f++];
}
void Input() {
int rx, ry, bx, by;
scanf("%d%d\n", &N, &M);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%c", &Map[i][j]);
if (Map[i][j] == 'R')rx = j, ry = i;
if (Map[i][j] == 'B')bx = j, by = i;
}
scanf("\n");
Map[i][M] = '\0';
}
push(rx, ry, bx, by, 0);
Visit[ry][rx][by][bx] = true;
}
void Move(int &x, int &y, int &c, int dy, int dx) {
while (Map[y + dy][x + dx] != '#'&&Map[y][x] != 'O') {
x += dx;
y += dy;
c +=1;
}
}
void BFS() {
Pos cur;
while (f != r) {
cur = pop();
if (cur.step >= 10) break;
for (int i = 0; i < 4; i++) {
//다음 빨간 구슬, 파란구슬 좌표 변수 선언
int nrx = cur.rx, nry = cur.ry;
int nbx = cur.bx, nby = cur.by;
//어떤 공이 더 기울이는 방향으로 앞에 있는지 확인하기 위한 변수
int rc = 0, bc = 0;
int nstep = cur.step + 1;
//각 구슬을 벽이 막을때까지 이동시킨다.
//c는 구슬의 이동한 칸을 카운트 한다.
//더 많이 움직인 구슬이 더 뒤쪽에 있다.
Move(nrx, nry, rc, dy[i], dx[i]);
Move(nbx, nby, bc, dy[i], dx[i]);
//파란구슬이 빠진경우는 실패이므로 제외한다.
if (Map[nby][nbx] != 'O') {
//빨간구슬이 빠지면 종료
if (Map[nry][nrx] == 'O') {
printf("%d\n", nstep);
return;
}
//만약 두 구슬이 같은 위치에 있으면 같이 있을 수 없으므로
//뒷쪽에 있던 구슬을 기울였던 방향과 반대로 한 칸 빼준다.
if (nry == nby && nrx == nbx) {
if (rc > bc)nry -= dy[i], nrx -= dx[i];
else nby -= dy[i], nbx -= dx[i];
}
//움직인 후의 좌표가 방문하지 않은 곳이라면 푸시
if (!Visit[nry][nrx][nby][nbx]) {
Visit[nry][nrx][nby][nbx] = true;
push(nrx,nry,nbx,nby,nstep);
}
}
}
}
//10번 이상 움직였거나 공백 큐가 될때까지 성공하지 못했다면 실패이다.
printf("-1\n");
}
int main() {
freopen("01.in", "r", stdin);
Input();
BFS();
return 0;
}
댓글남기기