백준 14503번 로봇 청소기 (C++)

 골드 4정돈 되야할 것 같은데 골드5이다.

이 문제는 각 위치에서 따져야 할 것이 많다. 일단 4방향을 봐야하는데 순서가 정해져있고, 바라보는 방향까지 고려해야한다. 게다가 후진까지 한다; (가지가지한다) 그래서 각 위치에서 따져줄 수 있는 DFS 가 맞는 풀이법이다. 시간을 고려해서 문제에서 사이즈도 50까지 크지 않게 주었다. dfs에는 위치정보, 방향정보, 그리고 뒤로 돌아올때는 청소로 치지 않으니 돌아왔는지를 체크한다.

dfs를 공부한다면 풀어보면 좋을 것 같은 문제이다.

백준에서는 개인적으로 100줄을 넘어가는 걸 안좋아하는데 방향을 따지고 방향에 따라 순서가 또 달라지니 코드가 길어졌다. 다른 사람들은 나머지연산으로 멋있게 풀었던데 난 그 생각은 나지 않아서 노가다로 모두 적어주었다.

 

#include <iostream>
#define MAX 51
using namespace std;

int N, M, D;
int boad[MAX][MAX] = { 0, };
int sx, sy;

int Ndx[] = { 0,1,0,-1 };
int Ndy[] = { -1,0,1,0 };
int Wdx[] = { 1,0,-1,0 };
int Wdy[] = { 0,1,0,-1 };
int Sdx[] = { 0,-1,0,1 };
int Sdy[] = { 1,0,-1,0 };
int Edx[] = { -1,0,1,0 };
int Edy[] = { 0,-1,0,1 };
int answer = 0;
bool visited[MAX][MAX] = { false, };

void dfs(int x, int y, int d, bool Back) {
	if (visited[x][y] == true)
		return;
	else
		visited[x][y] = true;
	if(Back == false)
		answer++;

	int Backx = 0;
	int Backy = 0;

	if (d == 0) {		// 북
		Backx = x + 1;
		Backy = y;
		for (int i = 0; i < 4; i++) {
			int nx = x + Ndx[i];
			int ny = y + Ndy[i];

			if (nx > -1 && ny > -1 && nx < N && ny < M && boad[nx][ny] == 0 && visited[nx][ny] == false) {
				if (i == 0)
					dfs(nx, ny, 3, false);		// 서
				else if (i == 1)	
					dfs(nx, ny, 2, false);		// 남
				else if (i == 2)
					dfs(nx, ny, 1, false);		// 동
				else if (i == 3)
					dfs(nx, ny, 0, false);		// 북
			}
		}
	}
	else if (d == 1) {	// 동
		Backx = x;
		Backy = y - 1;
		for (int i = 0; i < 4; i++) {
			int nx = x + Edx[i];
			int ny = y + Edy[i];

			if (nx > -1 && ny > -1 && nx < N && ny < M && boad[nx][ny] == 0 && visited[nx][ny] == false) {
				if (i == 0)
					dfs(nx, ny, 0, false);		// 북
				else if (i == 1)
					dfs(nx, ny, 3, false);		// 서		
				else if (i == 2)
					dfs(nx, ny, 2, false);		// 남
				else if (i == 3)
					dfs(nx, ny, 1, false);		// 동
			}
		}
	}
	else if (d == 2) {	// 남
		Backx = x - 1;
		Backy = y;
		for (int i = 0; i < 4; i++) {
			int nx = x + Sdx[i];
			int ny = y + Sdy[i];

			if (nx > -1 && ny > -1 && nx < N && ny < M && boad[nx][ny] == 0 && visited[nx][ny] == false) {
			if(i == 0)
				dfs(nx, ny, 1, false);
			else if (i == 1)
				dfs(nx, ny, 0, false);
			else if (i == 2)
				dfs(nx, ny, 3, false);
			else if (i == 3)
				dfs(nx, ny, 2, false);
			}
		}
	}
	else if (d == 3) {	// 서
		Backx = x;
		Backy = y + 1;
		for (int i = 0; i < 4; i++) {
			int nx = x + Wdx[i];
			int ny = y + Wdy[i];

			if (nx > -1 && ny > -1 && nx < N && ny < M && boad[nx][ny] == 0 && visited[nx][ny] == false) {
				if (i == 0)
					dfs(nx, ny, 2, false);
				else if (i == 1)
					dfs(nx, ny, 1, false);
				else if (i == 2)
					dfs(nx, ny, 0, false);
				else if (i == 3)
					dfs(nx, ny, 3, false);
			}
		}
	}

	if (boad[Backx][Backy] == 0 && Backx > -1 && Backx < N && Backy > -1 && Backy < M) {
		visited[Backx][Backy] = false;
		dfs(Backx, Backy, d, true);
		visited[Backx][Backy] = true;

		exit(0);
	}
	cout << answer << endl;
}

int main() {
	cin >> N >> M >> sx >> sy >> D;
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> boad[i][j];
			if (boad[i][j] == 0)
				cnt++;
		}
	}
	dfs(sx, sy, D, false);
}

많은 틀렸습니다가 나왔는데 진짜 어이없는 이유로 틀렸다.

글쎄, <가 아니라 << 로 적었던 것이다... 손떨었나..?

더 짜증나는 건 이렇게 썼는데도 컴파일 오류도 안나고 모든 Test Case, 질문게시판의 모든 반례도 전부 맞았다는 거다. 대체 어떻게 맞은거지