[Baekjoon]14503.로봇청소기

14503.로봇청소기

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

14503번: 로봇 청소기

---

요즘 시뮬레이션 문제를 연습하고 있다. 특별한 알고리즘이 필요없이 문제에 나와있는 조건대로 구현만 하면 된다고 하는데 그게 더 어려운 것 같다. 조건 하나 하나 꼼꼼히 생각해서 구현하는 것이 어려운 것 같다. 아무튼 이문제도 시뮬레이션 문제라고 생각하고 풀었다. 다른 사람들은 탐색 문제로 접근한 풀이도 많이 있는것 같다. 

 

재귀함수를 이용해서 풀었다.

먼저 map에서 청소한 곳과 안한 곳을 구분하기 위해  다음과 같이 정의한다.

0: 청소안한곳,     1: 벽,     2: 청소한 곳

청소를 하면 map에 저장된 값을 2로 갱신한다. 

 

그리고 방향전환 횟수를 저장하기 위해 turn변수를 사용한다. 청소할 곳을 탐색할 때 할 곳이 없으면 turn++ 해준다. 나중에 turn이 4가 되면 모든 방향에서 청소할 곳을 찾지 못한 것이므로 후진한다.

 

그리고 map의 테두리가 모두 벽이기 때문에 따로 map범위를 체크할 필요가 없다. 탐색 시 벽이 있으면  return하도록 한다. 

 

방향에 신경을 써야한다. 현재 로봇의 방향의 왼쪽 방향을 탐색해야 하므로 로봇이 회전할 때마다 탐색해야 할 방향이 바뀐다. 즉 현재 로봇이 북쪽을 보고 있으면 왼쪽은 서쪽이고 현재 동쪽을 보고있으면 왼쪽은 북쪽이다. 재귀함수의 parameter를 dir로 설정했으면  dir을 갱신할 때 다른 변수명으로 하면 안된다. 처음에  nextdir = dir+[] 이런 식으로 했다가 한참 헤맸다. 

 

 

private static void operate(int curX, int curY, int dir) {

		if (map[curY][curX] == 1) {	// 벽이면 종료 
			return;
		}
		if (map[curY][curX] == 0) { 
			map[curY][curX] = 2;
			cnt++;
		}

		int turn = 0;

		for (int i = 0; i < 4; i++) {
			dir = (dir + 3) % 4;	// 현재방향의 왼쪽 
			int nextX = curX + dx[dir];
			int nextY = curY + dy[dir];

			if (map[nextY][nextX] == 0) {	
				operate(nextX, nextY, dir);
				return;		// 청소하면 다른 방향 탐색하지 않음 
			} else { // 청소할 곳이 없으면 방향전환 
				turn++;	
			}
		}

		if (turn == 4) { // 네방향 모두 청소할 곳이 없으면 
			int back = (dir + 2) % 4; // 후진 
			int backX = curX + dx[back];
			int backY = curY + dy[back];

			if (map[backY][backX] == 1) { // 벽이면 종료 
				return;
			}
			operate(backX, backY, dir);
		}

	}

<전체코드>