14503 로봇청소기

문제 링크

코드 설명

dfs방식의 구현 코드이다.
삼성구현 문제에서 방향에 관한 문제가 많이나오는데 이문제를 통해 제대로 이해하자

코드 내에서 예를 들면
int ndir = (dir + 3 - i) % 4; // +3은 270도 회전 => 결국 왼쪽으로 90도 이동 , 또한 (-i)는 (dir*3)과 같은 수식결과라 할수있음(방향이 3씩 누적)

int ndir = (dir + 2) % 4; //기존 방향의 후진 방향

1.계속해서 회전하는경우 %n을통해 처리하면 된다.
2.각각의 주어진 방향의 인덱스를 보고 규칙을 찾는다.

DFS 이용한 코드

#include<iostream>
#include<vector>
using namespace std;
int N, M;
int map[51][51];

int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
int flag;
int cnt;
void dfs(int y, int x,int dir) {
	if (flag == 1) return;
	if (map[y][x] == 0) {
		map[y][x] = 2;//청소
		cnt++;
	}
	

	for (int i = 0; i < 4; i++) { //방향전환 반대로가기위해선 +2 왼쪽으로 가기위햇너 +3

		int ndir = (dir + 3 - i) % 4; // +3은 270도 회전  => 결국 왼쪽으로 90도 이동 , 또한 (-i)는 (dir*3)과 같은 수식결과라 할수있음
		int ny = y + dy[ndir];
		int nx = x + dx[ndir];

		if (ny < 0 || nx < 0 || nx >= M || ny >= N) continue; //벽넘을경우
		if (map[ny][nx] == 0) dfs(ny, nx, ndir);//2번 과정으로 이동

	}
	//네 방향 모두 청소가 이미 되어있거나 벽인 경우
	int ndir = (dir + 2) % 4; //기존 방향의 후진 방향
	int ny = y + dy[ndir];
	int nx = x + dx[ndir];
	if (map[ny][nx] == 1) { //후진시에도 막혀있다면 작동멈춤
		flag = 1;
		return;
	}
	
	dfs(ny, nx, dir); //바라보는방향 유지및 후진

}
//청소 완료:2 , 벽:1
int main() {
	cin >> N >> M;
	int r, c, d;
	cin >> r >> c >> d;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
		}
	}
	
	dfs(r,c,d);
	cout << cnt;
	return 0;
}