#14503 로봇 청소기

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

골드 5의 문제였다. 골드 5 치고는 좀 어려웠던 느낌? 조건이 너무 많아서 그랬던거 같다. 계속 오류뜨고 답이 다르게 나와서 결국 고수분들의 코드를 보고 해결 하긴 했지만.. 얻어가는건 많았다.

#include<iostream>


using namespace std;

int n, m;
int map[51][51];

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

int ans;

void dfs(int cx, int cy, int cd) {
	if (map[cx][cy] == 0) {
		map[cx][cy] = 2;
		ans++;
	}

	for (int i = 0; i < 4; i++) {
		int nd = (cd + 3 - i) % 4;
		int nx = cx + dx[nd];
		int ny = cy + dy[nd];

		if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
			continue;
		}

		if (map[nx][ny] == 0) {
			dfs(nx, ny, nd);
		}
	}    

	int nd = (cd + 2) % 4;
	int nx = cx + dx[nd];
	int ny = cy + dy[nd];

	if (map[nx][ny] == 1) {
		cout << ans;
		exit(0);
	}
	dfs(nx, ny, cd); //바라보는 방향을 유지한채.....
}


int main(void) {
  freopen("input.txt","r",stdin);
	cin >> n >> m;

	int r, c, dir;
	cin >> r >> c >> dir;

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

	dfs(r, c, dir);

	return 0;
}

🎯 배운 것

1. dx[] 와 dy[]

여태껏 좌표를 이동할때 dx,dy를 사용했었다. 이 문제에서는 바라보고 있는 방향을 토대로 왼쪽을 결정해야했기 때문에 또 사용 할 수 있었다. 바라보고있는 방향 nd를 dx ,dy의 인덱스 값으로 쓴다면 충분히 구현 할 수있었다.

 

2. dfs로도 충분히 가능(?)

문제가 느낌상 bfs를 이용해야할것 같았는데 bfs가 더 복잡했던거 같다. 요새 최단거리, 최단경로, 최소비용 등등의 문제를 자주 풀다보니까 bfs에 꽂혀있었는데 dfs도 연습을 더 해야할 것 같다.