그래프 문제인척 하는 구현문제였다. 문제 자체는 쉬웠는데 북 동 남 서 방향 전환 방식을 생각하지 못해 하드코딩 한 탓에 코드가 길어지고 중간 중간 실수가 많이 나왔다.
오답
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>
#include <set>
#define endl "\n"
using namespace std;
int robot[51][51];
bool clean[51][51];
int cnt;
int n, m;
int a, b, d;
void solve(int x, int y, int d) {
clean[x][y] = true;
cout << x << " " << y << "이동" << endl;
cnt++;
if (d == 0) {
if (d == 0 && robot[x][y + 1] == 0 && clean[x][y+1] == false) {
solve(x, y + 1, 0);
}
//가야 할 칸이 이미 청소되어 있을때
else if (d == 0 && robot[x][y + 1] == 0 && clean[x][y + 1] == true || robot[x][y + 1] == 1) {
int count = 0;
int z = d;
int flag = 0;
while (count < 4) {
z++;
if (z == 0) {
if (robot[x][y + 1] == 0 && clean[x][y + 1] == false) {
flag = 1;
break;
}
}
if (z == 1) {
if (robot[x + 1][y] == 0 && clean[x + 1][y] == false) {
flag = 1;
break;
}
}
if (z == 2) {
if (robot[x][y - 1] == 0 && clean[x][y - 1] == false) {
flag = 1;
break;
}
}
if (z == 3) {
if (robot[x - 1][y] == 0 && clean[x - 1][y] == false) {
flag = 1;
break;
}
}
}
if (flag == 1) {
if (z == 0) {
solve(x,y + 1,z);
}
if (z == 1) {
solve(x + 1,y, z);
}
if (z == 2) {
solve(x, y - 1, z);
}
if (z == 3) {
solve(x - 1, y, z);
}
}
else if (flag == 0) {
if (z == 3) {
solve(x, y + 1, z);
}
if (z == 2) {
solve(x + 1, y, z);
}
if (z == 1) {
solve(x, y - 1, z);
}
if (z == 0) {
solve(x - 1, y, z);
}
}
}
}
else if (d == 1) {
if (robot[x + 1][y] == 0 && clean[x+1][y] == false) {
solve(x + 1, y, 1);
}
else if (robot[x + 1][y] == 0 && clean[x + 1][y] == true || robot[x + 1][y] == 1) {
int count = 0;
int z = d;
int flag = 0;
while (count < 4) {
z++;
if (z == 0) {
if (robot[x][y + 1] == 0 && clean[x][y + 1] == false) {
flag = 1;
break;
}
}
if (z == 1) {
if (robot[x + 1][y] == 0 && clean[x + 1][y] == false) {
flag = 1;
break;
}
}
if (z == 2) {
if (robot[x][y - 1] == 0 && clean[x][y - 1] == false) {
flag = 1;
break;
}
}
if (z == 3) {
if (robot[x - 1][y] == 0 && clean[x - 1][y] == false) {
flag = 1;
break;
}
}
}
if (flag == 1) {
if (z == 0) {
solve(x, y + 1, z);
}
if (z == 1) {
solve(x + 1, y, z);
}
if (z == 2) {
solve(x, y - 1, z);
}
if (z == 3) {
solve(x - 1, y, z);
}
}
else if (flag == 0) {
if (z == 3) {
solve(x, y + 1, z);
}
if (z == 2) {
solve(x + 1, y, z);
}
if (z == 1) {
solve(x, y - 1, z);
}
if (z == 0) {
solve(x - 1, y, z);
}
}
}
}
else if (d == 2) {
if(robot[x][y - 1] == 0 && clean[x][y-1] == false) {
solve(x, y - 1, 2);
}
else if (robot[x][y - 1] == 0 && clean[x][y - 1] == true || robot[x][y - 1] == 1) {
int count = 0;
int z = d;
int flag = 0;
while (count < 4) {
z++;
if (z == 0) {
if (robot[x][y + 1] == 0 && clean[x][y + 1] == false) {
flag = 1;
break;
}
}
if (z == 1) {
if (robot[x + 1][y] == 0 && clean[x + 1][y] == false) {
flag = 1;
break;
}
}
if (z == 2) {
if (robot[x][y - 1] == 0 && clean[x][y - 1] == false) {
flag = 1;
break;
}
}
if (z == 3) {
if (robot[x - 1][y] == 0 && clean[x - 1][y] == false) {
flag = 1;
break;
}
}
}
if (flag == 1) {
if (z == 0) {
solve(x, y + 1, z);
}
if (z == 1) {
solve(x + 1, y, z);
}
if (z == 2) {
solve(x, y - 1, z);
}
if (z == 3) {
solve(x - 1, y, z);
}
}
else if (flag == 0) {
if (z == 3) {
solve(x, y + 1, z);
}
if (z == 2) {
solve(x + 1, y, z);
}
if (z == 1) {
solve(x, y - 1, z);
}
if (z == 0) {
solve(x - 1, y, z);
}
}
}
}
else if (d == 3) {
if (robot[x - 1][y] == 0 && clean[x-1][y] == false) {
solve(x - 1, y, 3);
}
else if (robot[x - 1][y] == 0 && clean[x - 1][y] == true || robot[x - 1][y] == 1) {
int count = 0;
int z = d;
int flag = 0;
while (count < 4) {
z++;
if (z == 0) {
if (robot[x][y + 1] == 0 && clean[x][y + 1] == false) {
flag = 1;
break;
}
}
if (z == 1) {
if (robot[x + 1][y] == 0 && clean[x + 1][y] == false) {
flag = 1;
break;
}
}
if (z == 2) {
if (robot[x][y - 1] == 0 && clean[x][y - 1] == false) {
flag = 1;
break;
}
}
if (z == 3) {
if (robot[x - 1][y] == 0 && clean[x - 1][y] == false) {
flag = 1;
break;
}
}
}
if (flag == 1) {
if (z == 0) {
solve(x, y + 1, z);
}
if (z == 1) {
solve(x + 1, y, z);
}
if (z == 2) {
solve(x, y - 1, z);
}
if (z == 3) {
solve(x - 1, y, z);
}
}
else if (flag == 0) {
if (z == 3) {
solve(x, y + 1, z);
}
if (z == 2) {
solve(x + 1, y, z);
}
if (z == 1) {
solve(x, y - 1, z);
}
if (z == 0) {
solve(x - 1, y, z);
}
}
}
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
cin >> a >> b >> d;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> robot[i][j];
}
}
solve(a , b, d);
cout << cnt;
return 0;
}
정답
#include <iostream>
#include <vector>
#define endl "\n"
using namespace std;
int robot[51][51];
bool clean[51][51];
int cnt;
int n, m;
int a, b, d;
// 북, 동, 남, 서 방향을 나타내는 배열
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void solve(int x, int y, int d) {
// 현재 칸 청소
if (!clean[x][y]) {
clean[x][y] = true;
cnt++;
}
// 4 방향 탐색
for (int i = 0; i < 4; i++) {
// 반시계 방향으로 회전
d = (d + 3) % 4;
int nx = x + dx[d];
int ny = y + dy[d];
// 청소하지 않은 빈 칸이 있는 경우
if (nx >= 0 && ny >= 0 && nx < n && ny < m && robot[nx][ny] == 0 && !clean[nx][ny]) {
solve(nx, ny, d);
return;
}
}
// 4 방향 모두 청소가 되어있거나 벽인 경우
int back = (d + 2) % 4;
int bx = x + dx[back];
int by = y + dy[back];
// 뒤로 갈 수 있는 경우
if (bx >= 0 && by >= 0 && bx < n && by < m && robot[bx][by] == 0) {
solve(bx, by, d);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
cin >> a >> b >> d;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> robot[i][j];
}
}
solve(a, b, d);
cout << cnt << endl;
return 0;
}
