반응형
흐어ㅠㅠ 시뮬레이션 문제 너무 싫습니다
map boundary check에서 +1, -1 혹은 N, M 같은거 하나씩 실수했는데
그거 틀린거 찾느라 너무 어려웠다.
다음번에 다시 풀면 지금보다 구성을 깔끔하게 코드를 짜보고 싶다.
수도 코드
C언어 구현코드
#include < iostream >
#include < string >
using namespace std;
int N, M;
char map[10][10] = { 0, };
// 동서남북
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
// _b : 방향
// 0 : 위
// 1 : 아래
// 2 : 오른쪽 ->
// 3 : 왼쪽 <-
int func(int _depth, int _b, int _rb,
int _r_x, int _r_y, int _b_x, int _b_y) {
// 1. rb==2
// R만 고려하여도 됌
// --------------------------------------------------------------------
if (_rb == 2) {
switch (_b)
{
case 0: // 위
while (_r_x-1 > 0) {
if (map[_r_x-1][_r_y]=='O') {
// 구멍
return 1;
}
else if (map[_r_x - 1][_r_y] == '#') {
break;
}
_r_x--;
}
break;
case 1: // 아래
while (_r_x+1 < N-1) {
if (map[_r_x + 1][_r_y] == 'O') {
// 구멍
return 1;
}
else if (map[_r_x + 1][_r_y] == '#') {
break;
}
_r_x++;
}
break;
case 2:
while (_r_y+1 < M-1) {
if (map[_r_x][_r_y+1] == 'O') {
// 구멍
return 1;
}
else if (map[_r_x][_r_y+1] == '#') {
break;
}
_r_y++;
}
break;
case 3:
while (_r_y - 1 > 0) {
if (map[_r_x][_r_y-1] == 'O') {
// 구멍
return 1;
}
else if (map[_r_x][_r_y-1] == '#') {
break;
}
_r_y--;
}
break;
}
}
// 2. rb==3 -> r,b 둘다 움직임 가능
// --------------------------------------------------------------------------
else if (_rb==3) {
switch (_b)
{
case 0: // 위
// 같은 열에서 r,b 더 위의 행에 위치하는 것
if (_r_y == _b_y && _r_x < _b_x) { // red가 더 위에 위치하고 있음.
// 먼저 움직임
// 빨간 구슬 움직임
bool flagSuccess = false;
while (_r_x -1> 0) { // _r_x==1 ->벽때문에 어차피 못움직이니까 처리X
if (map[_r_x - 1][_r_y] == 'O') {
// 구멍
_r_x--;
flagSuccess = true;
break;
}
else if (map[_r_x - 1][_r_y] == '#') {
break;
}
_r_x--;
}
// 파란 구슬 움직임
while (_b_x -1 > 0) {
if (map[_b_x - 1][_b_y] == 'O') {
// 구멍
return 0;
}
else if (map[_b_x - 1][_b_y] == '#') {
break;
}
else if (_r_x == _b_x-1 && _r_y == _b_y) {
break;
}
_b_x--;
}
if (flagSuccess == true) {
return 1;
}
}
else {
// 파란 구슬 움직임
while (_b_x -1 > 0) {
if (map[_b_x - 1][_b_y] == 'O') {
// 구멍
return 0;
}
else if (map[_b_x - 1][_b_y] == '#') {
break;
}
_b_x--;
}
// 빨간 구슬 움직임
while (_r_x -1 > 0) {
if (map[_r_x - 1][_r_y] == 'O') {
// 구멍
return 1;
}
else if (map[_r_x - 1][_r_y] == '#') {
break;
}
else if (_r_x-1==_b_x && _r_y==_b_y) {
break;
}
_r_x--;
}
}
break;
case 1: // 아래
// 같은 열에서 r,b 더 아래의 행에 위치하는 것
if (_r_y == _b_y && _r_x > _b_x) { // red가 더 아래에 위치하고 있음.
// 먼저 움직임
// 빨간 구슬 움직임
bool flagSuccess = false;
while (_r_x+1 < N) {
if (map[_r_x + 1][_r_y] == 'O') {
// 구멍
_r_x++;
flagSuccess = true;
break;
}
else if (map[_r_x + 1][_r_y] == '#') {
break;
}
_r_x++;
}
// 파란 구슬 움직임
while (_b_x+1 < N) {
if (map[_b_x + 1][_b_y] == 'O') {
// 구멍
return 0;
}
else if (map[_b_x + 1][_b_y] == '#') {
break;
}
else if (_r_x == _b_x+1 && _r_y == _b_y) {
break;
}
_b_x++;
}
if (flagSuccess == true) {
return 1;
}
}
else {
// 파란 구슬 움직임
while (_b_x+1 < N) {
if (map[_b_x + 1][_b_y] == 'O') {
// 구멍
return 0;
}
else if (map[_b_x + 1][_b_y] == '#') {
break;
}
_b_x++;
}
// 빨간 구슬 움직임
while (_r_x +1 < N) {
if (map[_r_x + 1][_r_y] == 'O') {
// 구멍
return 1;
}
else if (map[_r_x + 1][_r_y] == '#') {
break;
}
else if (_r_x+1 == _b_x && _r_y == _b_y) {
break;
}
_r_x++;
}
}
break;
case 2: // 오른쪽
// 같은 행에서 r,b 더 오른쪽의 행에 위치하는 것
if (_r_x == _b_x && _r_y > _b_y ) { // red가 더 오른쪽에 위치하고 있음.
// 먼저 움직임
// 빨간 구슬 움직임
bool flagSuccess = false;
while (_r_y + 1 < M) {
if (map[_r_x][_r_y+1] == 'O') {
// 구멍
_r_y++;
flagSuccess = true;
break;
}
else if (map[_r_x][_r_y+1] == '#') {
break;
}
_r_y++;
}
// 파란 구슬 움직임
while (_b_y + 1 < M) {
if (map[_b_x][_b_y+1] == 'O') {
// 구멍
return 0;
}
else if (map[_b_x][_b_y+1] == '#') {
break;
}
else if (_r_x == _b_x && _r_y == _b_y+1) {
break;
}
_b_y++;
}
if (flagSuccess == true) {
return 1;
}
}
else {
// 파란 구슬 움직임
while (_b_y + 1 < M) {
if (map[_b_x][_b_y+1] == 'O') {
// 구멍
return 0;
}
else if (map[_b_x][_b_y+1] == '#') {
break;
}
_b_y++;
}
// 빨간 구슬 움직임
while (_r_y + 1 < M) {
if (map[_r_x][_r_y+1] == 'O') {
// 구멍
return 1;
}
else if (map[_r_x][_r_y+1] == '#') {
break;
}
else if (_r_x== _b_x && _r_y+1 == _b_y) {
break;
}
_r_y++;
}
}
break;
case 3: // 왼쪽
// 같은 행에서 r,b 더 왼쪽쪽의 행에 위치하는 것
if (_r_x == _b_x && _r_y < _b_y) { // red가 더 왼쪽에 위치하고 있음.
// 먼저 움직임
// 빨간 구슬 움직임
bool flagSuccess = false;
while (_r_y -1 > 0) {
if (map[_r_x][_r_y - 1] == 'O') {
// 구멍
flagSuccess = true;
_r_y--;
break;
}
else if (map[_r_x][_r_y - 1] == '#') {
break;
}
_r_y--;
}
// 파란 구슬 움직임
while (_b_y - 1 >0) {
if (map[_b_x][_b_y - 1] == 'O') {
// 구멍
return 0;
}
else if (map[_b_x][_b_y - 1] == '#') {
break;
}
else if (_r_x == _b_x && _r_y == _b_y - 1) {
break;
}
_b_y--;
}
if (flagSuccess == true) {
return 1;
}
}
else {
// 파란 구슬 움직임
while (_b_y -1 > 0) {
if (map[_b_x][_b_y - 1] == 'O') {
// 구멍
return 0;
}
else if (map[_b_x][_b_y - 1] == '#') {
break;
}
_b_y--;
}
// 빨간 구슬 움직임
while (_r_y - 1 > 0) {
if (map[_r_x][_r_y - 1] == 'O') {
// 구멍
return 1;
}
else if (map[_r_x][_r_y - 1] == '#') {
break;
}
else if (_r_x == _b_x && _r_y - 1 == _b_y) {
break;
}
_r_y--;
}
}
break;
}
}
// 3. _depth 확인, 탈출조건
if (_depth == 9) {
return 0;
}
// 4. 4방항 dfs
for (int b = 0; b < 4; b++) {
if (func(_depth+1, b, _rb, _r_x, _r_y, _b_x, _b_y) == 1) {
return 1;
}
}
return 0;
}
int main(void) {
int r_x,r_y, b_x, b_y;
// 1. 입력
cin >> N >> M;
for (int i = 0; i < N; i++) {
string str;
cin >> str;
for (int j = 0; j < M; j++) {
if (str[j] == 'R') {
r_x = i;
r_y = j;
map[i][j] = '.';
}
else if (str[j] == 'B') {
b_x = i;
b_y = j;
map[i][j] = '.';
}
else {
map[i][j] = str[j];
}
}
}
// 2. R,B 사방이 벽으로 막혀있는지, 움직임 가능한지 확인 -> rb
// 1) R 사방이 벽으로 막혀있음.
// -> 종료 -> print 0
int k = 0;
while( 1 ) { // k=0,1,2,3
if (k == 4) {
cout << "0" << endl;
return 0;
}
int x = r_x + dx[k];
int y = r_y + dy[k];
if ((x<0 || x>N)||
(y<0 || y>M)) { // boundary check
continue;
}
if (map[x][y] != '#') {
break;
}
k++;
}
// 2) B사방이 벽으로 막혀있음
int rb = 2;
for (int k = 0; k < 4; k++) {
int x = b_x + dx[k];
int y = b_y + dy[k];
if ((x<0 || x>N) ||
(y<0 || y>M)) { // boundary check
continue;
}
if (map[x][y] != '#') {
rb = 3; // r,b 둘 다 움직임 가능
break;
}
}
func(0, 3, rb, r_x, r_y, b_x, b_y);
// 3. 사방향으로 모두 dfs
for (int b = 0; b < 4; b++) {
if ( func(0, b, rb, r_x, r_y, b_x, b_y) == 1) {
cout << "1" << endl;
return 0;
}
}
cout << "0" << endl;
return 0;
}
반응형