어흥
[백준 15644] 구슬 탈출 3 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/15644
1. 주의할 점
- DFS를 통해 10번이상 실행하지 않도록 설계한다.
- 구슬이 겹쳐지는 경우 따로 처리한다
2. 구현
- 최대 횟수가 10번이므로 DFS를 호출하고, 다음 DFS를 호출할 수 있는 경우 실행한 명령값을 이전의 명령에 더해서 넘긴다
- Start함수(DFS 함수)의 첫줄에 If문을 통해 최단경로보다 많은 명령을 수행하려는 경우 더 이상 검사하지 않도록 한다 -> 최단 경로를 갱신할때마다 이동경로를 갱신해도 되는 이유
함수를 더 깔끔하게 다듬는 연습이 필요하다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int row, col, result = 10000;
string ss;
struct info {
int x, y;
};
info tmp;
vector<info> red;
vector<info> blue;
char arr[10][10];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
void start(int cnt, string ans) {
if (cnt > 9 || cnt >= result) return;
int crx, cry, cbx, cby, nrx, nry, nbx, nby;
crx = red[0].x; cry = red[0].y;
cbx = blue[0].x; cby = blue[0].y;
for (int i = 0; i < 4; i++) {
nrx = crx + dx[i];
nry = cry + dy[i];
nbx = cbx + dx[i];
nby = cby + dy[i];
bool r_finish = false, b_finish = false;
if (arr[nry][nrx] != '#') {
if (arr[nry][nrx] == 'O')
r_finish = true;
else {
while (1) {
nrx += dx[i];
nry += dy[i];
if (arr[nry][nrx] == 'O') {
r_finish = true;
break;
}
else if (arr[nry][nrx] == '#') {
nrx -= dx[i];
nry -= dy[i];
break;
}
}
}
}
else {
nrx -= dx[i];
nry -= dy[i];
}
if (arr[nby][nbx] != '#') {
if (arr[nby][nbx] == 'O')
b_finish = true;
else {
while (1) {
nbx += dx[i];
nby += dy[i];
if (arr[nby][nbx] == 'O') {
b_finish = true;
break;
}
else if (arr[nby][nbx] == '#') {
nbx -= dx[i];
nby -= dy[i];
break;
}
}
}
}
else {
nbx -= dx[i];
nby -= dy[i];
}
if (b_finish) continue;
if (r_finish) {
result = min(result, cnt + 1);
if (i == 0) ss = ans + "U";
else if (i == 1) ss = ans + "R";
else if (i == 2) ss = ans + "D";
else if (i == 3) ss = ans + "L";
return;
}
if (nrx == nbx && nry == nby) {
if (i == 0) {
if (cry > cby) nry += 1;
else nby += 1;
}
else if (i == 1) {
if (crx > cbx) nbx -= 1;
else nrx -= 1;
}
else if (i == 2) {
if (cry > cby) nby -= 1;
else nry -= 1;
}
else if (i == 3) {
if (crx > cbx) nrx += 1;
else nbx += 1;
}
}
red[0].x = nrx;
red[0].y = nry;
blue[0].x = nbx;
blue[0].y = nby;
if(i==0) start(cnt + 1,ans+"U");
else if (i == 1) start(cnt + 1, ans + "R");
else if (i == 2) start(cnt + 1, ans + "D");
else if (i == 3) start(cnt + 1, ans + "L");
red[0].x = crx;
red[0].y = cry;
blue[0].x = cbx;
blue[0].y = cby;
}
}
int main() {
cin >> row >> col;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
cin >> arr[i][j];
if (arr[i][j] == 'B') {
tmp.x = j;
tmp.y = i;
blue.push_back(tmp);
arr[i][j] = '.';
}
else if (arr[i][j] == 'R') {
tmp.x = j;
tmp.y = i;
red.push_back(tmp);
arr[i][j] = '.';
}
}
start(0,"");
if (result == 10000) result = -1;
cout << result;
if (result != -1) cout << '\n'<<ss;
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 5213] 과외맨 (C++) (0) | 2020.03.24 |
---|---|
[백준 11725] 트리의 부모 찾기 (C++) (0) | 2020.03.24 |
[백준 15653] 구슬 탈출 4 (C++) (0) | 2020.03.23 |
[백준 2011] 암호코드 (C++) (0) | 2020.03.23 |
[백준 18809] Gaaaaaaaaaarden (C++) (0) | 2020.03.21 |
Comments