BOJ : 14503 로봇 청소기

---

[BOJ 14503(G5) 리뷰]

1월에 있을 삼성SDS 알고리즘 교육을 대비하여 시간이 날때마다 하루 1~2문제씩 풀고있다.

이 문제는 삼성SW역량테스트 기출문제이다. 예전에도 한번 풀려고 했던적이 있는데 그땐 뭣모르고 DFS로만 풀어야하는 줄 알아 이리저리 머리 굴려보다 포기했던 문제다.

시간이 지나고 다시 문제를 천천히 읽어보니 굳이 DFS를 사용하지 않고도 구현을 할 수 있을것같아 시도했다.
푸는데는 1시간정도 걸린거같다.

일단 조건들은 문제에 친절히 설명이 되어있다. 따라서 설명에 맞게만 구현해주면 된다. 다만 방향을 바꾸는 부분, 후진하는 부분에 조금 헷갈리는게 있어 그 부분에서 시간을 꽤 잡아먹었다.

방향을 바꾸는것과 후진하는것은 %연산을통해 하도록했고, cnt변수를 통해 네 방향을 모두 탐색했을시 후진하도록 했다. 코드를 보면 알겠지만 정말 문제에 주어진 조건 그대로 코딩했다... 끝이다.

/*
	20.12.29
	BOJ : 14503 로봇 청소기 (https://www.acmicpc.net/problem/14503)
	구현
*/

#include <iostream>
using namespace std;

int N, M;
int map[51][51];
int vis[51][51];

int dx[4] = { -1,0,1,0, };
int dy[4] = { 0,1,0,-1 };

int curDir;
int cx, cy;

int main() {
	cin >> N >> M;
	cin >> cx >> cy >> curDir;

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

	int ans = 1;
	vis[cx][cy] = 1;
	int cnt = 0;
	while (1) {
		int nDir = (curDir + 3) % 4;
		int nx = cx + dx[nDir];
		int ny = cy + dy[nDir];
		cnt++;
		if (map[nx][ny] == 0 && vis[nx][ny] == 0) { //방문하지 않았고 벽이 아닌 경우
			cx = nx;
			cy = ny;
			curDir = nDir;
			vis[nx][ny] = 1;
			ans++;
			cnt = 0;
		}
		else if (cnt < 4 && (map[nx][ny] == 1 || vis[nx][ny] == 1)) { //벽이거나 방문했을경우 방향만 바꿈.
			curDir = nDir;
		}
		else if (cnt == 4) { //네방향 모두 탐색함.
			int bDir = (nDir + 2) % 4;
			int bx = cx + dx[bDir];
			int by = cy + dy[bDir];

			if (map[bx][by] == 1) {
				cout << ans;
				return 0;
			}
			else {
				curDir = nDir;
				cx = bx;
				cy = by;
				cnt = 0;
			}
		}
	}
}