[백준OJ] 14503번 로봇 청소기

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

---

 

-풀이-

문제에 나온대로했지만, 순서를 다르게했다.

 

먼저 자기자리를 청소한뒤,

첫번째로 a를 체크하고, 두번째론 d, 세번째론 c, 네번째론 b를 if-elseif로 체크해가면서 로직을 실행시켰다.

a,b,c,d,순서대로 조건을 검사하게된다면, 사방이 전부 벽이거나 청소한 구간일때, 청소기는 무한으로 돌기만하고 끝날것이고, c다음으로 d를 검사하면, 네방향이 벽인경우에 무조건 후진을 하는 c에 걸리기 때문이다.

 

-시간복잡도-

로봇청소기가 전부 다 뽈뽈 돌아다니는것이 최악이므로 O(N*M)이 된다.

 

-코드-

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int maze[50][50];
int n, m,d;
int mv[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
pair<int, int> c;


void input() {
	cin >> n >> m;
	cin >> c.first >> c.second >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maze[i][j];
		}
	}
}

bool check(int x, int y) {
	if ((maze[x + 1][y] == -1||maze[x+1][y]==1) && (maze[x - 1][y] == -1|| maze[x - 1][y] == 1)
		&& (maze[x][y + 1] == -1|| maze[x][y + 1] == 1) && (maze[x][y - 1] == -1|| maze[x][y - 1] == 1)) {
		return true;
	}
	else {
		return false;
	}
}

void solve() {
	while (true) {
		maze[c.first][c.second] = -1;
		if (maze[c.first + mv[d == 0 ? 3 : d-1][0]][c.second + mv[d == 0 ? 3 : d-1][1]] == 0) {
			d == 0 ? d = 3 : d--;
			c.first = c.first + mv[d][0];
			c.second = c.second + mv[d][1];
		}
		else if (check(c.first, c.second) && maze[c.first+mv[(d+2)%4][0]][c.second+mv[(d+2)%4][1]]==1) {
			break;
		}
		else if (check(c.first, c.second)) {
			c.first = c.first + mv[(d + 2) % 4][0];
			c.second = c.second + mv[(d + 2) % 4][1];
		}
		else if (maze[c.first + mv[d == 0 ? 3 : d-1][0]][c.second + mv[d == 0 ? 3 : d-1][1]] != 0) {
			d == 0 ? d = 3 : d--;
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maze[i][j] == -1) cnt++;
		}
	}
	cout << cnt << "\n";
}

int main(){
	input();
	solve();
}