백준 알고리즘 14503_로봇 청소기 C

문제

(링크)14503번: 로봇 청소기 (acmicpc.net)

 

사고과정

처음 문제를 봤을 때 전형적인 DFS문제라고 생각했다. 현재 위치를 기준으로 4방향을 탐색한 뒤 새 위치를 업데이트하기 때문이다. 하지만 결과적으로 DFS문제는 아니고 비슷한 방법을 사용해서 풀이할 수 있는 문제이다.

문제를 해결하기 위해 난 문제 흐름대로 방법을 생각했다. 현재 위치(r,c)와 dir가 주어진 상태에서 반시계방향으로 4번, 다시 현재 방향을 바라볼 때까지 반복하는데, 만약 청소를 할 수 있는 칸이 있다면 탐색을 멈추고 해당 칸으로 이동한다. 이후 탐색을 반복한다. 이 때, 4방향 모두 방문(청소)했거나 벽이면 주어진 dir의 바라보는 상태로 후진을 하고 탐색을 시작한다. 후진도 불가능하면 코드를 끝낸다.

DFS와 다른점은 스택을 쌓지않고 "현재 시작점"을 갱신한다는 점 밖에 없다.  

 

내코드

#include <stdio.h>
#include <stdlib.h>


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


int adjustDir(int dir) {
	if (dir <0)dir += 4;
	return dir;
}

int main() {
	int height, width,i,j;
	scanf("%d %d", &height, &width);
	int start_x, start_y, direction;
	scanf("%d %d %d", &start_y, &start_x, &direction);

	int** map = (int**)malloc(height * sizeof(int*));
	int** visit = (int**)calloc(height, sizeof(int*));
	for (i = 0; i < height; i++) {
		map[i] = (int*)malloc(width * sizeof(int));
		visit[i] = (int*)calloc(width, sizeof(int));
	}
	for (i = 0; i < height; i++) {
		for (j = 0; j < width; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	
	visit[start_y][start_x] = 1;
	int clean = 1;
	int end_flag = 0;

	while (!end_flag) {
		int return_flag = 0;
		for (i = 0; i < 4; i++) {
			int NewDirection = adjustDir(direction - i - 1);
			int Y = start_y + dy[NewDirection];
			int X = start_x + dx[NewDirection];

			if (Y >= 0 && Y < height && X >= 0 && X < width) {
				if (visit[Y][X] == 0 && map[Y][X] == 0) {
					start_x = X;
					start_y = Y;
					visit[Y][X] = 1;
					clean++;
					direction = NewDirection;
					break;
				}
				else if (visit[Y][X] == 1 || map[Y][X] == 1) {
					return_flag++;
					continue;
				}
			}
		}
		if (return_flag == 4) {
			int Y = start_y - dy[direction];
			int X = start_x - dx[direction];

			if(map[Y][X]==1){
				end_flag = 1;
			}
			else {
				start_y = Y;
				start_x = X;
			}
		}
	}
	printf("%d", clean);





	for (i = 0; i < height; i++) {
		free(map[i]);
		free(visit[i]);
	}
	free(map);
	free(visit);
	return 0;
}

변수 start_x와 start_y에 현재 위치를 입력 받고 dir에 현재 방향을 입력 받는다. map에 방의 구조를 입력 받고 visit배열을 0으로 초기화 시킨다. (malloc와 calloc을 사용하려면 <stdlib.h>를 include해야한다) 이후 visit[start_y][srats_x]를 1로 바꿔주고 clean(몇번 청소를 했느가)을 1로 초기화한다. 이후 탐색을 시작한다.

 

먼저 while문의 종료조건을 end_flag를 이용해 설정한다. 이 end_flag는 문제에서 설명하는대로 "4면 모두 진행이 불가한데, 현재 방향을 바라보고 후진이 불가능할 때" 1이 된다. end_flag를 갱신하기 위해선 후진을 해야하는 상황인지를 알아내야 하기 때문에 return_flag를 각 지점에서 0으로 초기화한다. 

 

NewDirection은 현재 방향 direction에서 파생된 것인데, 문제에서 북0, 동1, 남2, 서3이라고 설정해 놓았으므로, 각 방향에서 왼쪽방향은 1을 빼준 방향이고 이를 adjustDir함수를 이용해 0~3범위로 만들어준다. 이후 구한 새로운 지점  map[Y][X]== 0 && visit[Y][X]== 0 (청소한적 없고 벽이 아니다)이면 시작하는 위치start_y,start_x를 Y와 X로 갱신하고 clean을 추가한다. 또한 현재 바라보는 방향인 direction을 NewDirection으로 바꿔주고 청소를 한 곳이라고 visit[Y][X]를 갱신한다. 만약 map[Y][X]==1 || visit[Y][X]==1(벽이거나 청소한적이 있으면) return_flag를 증가시키고 계속한다.

 

2번째 반복문이 끝나고 return_flag가 0이면, 후진을 해야한다. 이 때, 후진한 지점 map{Y][X]==1 (벽)이면 end_flag를 증가시키고 아니면 start_x와 start_y를 갱신한다.

 

피드백

그리 어려운 문제는 아니었다. 맞은 사람들 보면 메모리가 1112KB던데 어떻게 하면 4KB를 줄일 수 있을지 생각해볼것