[백준] 14503번 로봇청소기 C/C++

//C/C++ 백준 로봇 청소기

//www.acmicpc.net/problem/14503

 

#include <iostream>
#include<queue>
#include<cstring>

using namespace std;

int n, m = 0;

const int dy[] = { -1,0,1,0 }; //북동남서
const int dx[] = { 0,1,0,-1 }; //북동남서


int map[55][55];
int chk[55][55] = { false, };


struct robot
{
int x, y, d;
};

robot r;


int sol() {

int result = 0;
chk[r.y][r.x] = true; // 1) 현재의 위치를 먼저 청소한다.

queue < pair<pair<int, int>, int>>q;
q.push(make_pair(make_pair(r.y,r.x),r.d));

while (!q.empty()) {
int curY = q.front().first.first;
int curX = q.front().first.second;
int curD = q.front().second;
q.pop();

// 3) 만약 앞쪽이 장애물이거나 이미 청소가 되어 있다면
// 처음 방향으로 돌아올 때까지 2번 작업을 반복한다.
//한바퀴 돌았는데 시작한 방향이 맵밖이라면? > 확인할것

int flag = 0;
for (int dir = 0; dir < 4;dir++) {

int nextD = (curD - dir - 1 + 4) % 4; //2)왼쪽으로 회전을 한다.
int nextY = curY + dy[nextD]; //회전한방향으로 이동
int nextX = curX + dx[nextD];

if (nextY < 0 || nextX < 0 || nextY >= n || nextX >= m|| map[nextY][nextX] == 1||chk[nextY][nextX]==true) {//맵탈출하면, 가야할곳이 벽이라면,갔던곳이라면
continue;

}

//2)앞쪽이 장애물이 아니고 청소가 되어 있지 않다면 앞으로 전진하여 1번부터 작업을 반복한다.
if (map[nextY][nextX] != 1 && chk[nextY][nextX] == false) {
flag = 1; //행동했으면
chk[nextY][nextX] = true; // 청소했다고 표시
q.push(make_pair(make_pair(nextY, nextX), nextD));

break;
}


}
//4) 처음의 방향으로 돌아올 때까지 전진을 하지 못했다면

if (flag == 0)
{
//뒤로 한 칸 후진을 한 후

int tempY = curY + dy[(curD + 2) % 4];
int tempX = curX + dx[(curD + 2) % 4];

if (map[tempY][tempX] == 1) {

break;
}

q.push(make_pair(make_pair(tempY, tempX), curD));



}
//만약에 다돌았는데 전진을 못했으면 후진
result = 0;
//true가 몇개인지 저장해두기
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//cout << chk[i][j] << "\n";

if (chk[i][j] == true) {
result = result + 1;
}
}

}

}

return result;

}


int main() {
cin >> n >> m;
cin >> r.y >> r.x >> r.d;
//scanf("%d %d",&n, &m); //맵크기
//scanf("%d %d %d", &r.y, &r.x, &r.d); //로봇의 좌표, 방향

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
}
}

printf("%d",sol());
return 0;


}