[BOJ 14503] 로봇청소기

문제

• BOJ 14503
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

이 문제는 재귀로 해결했으며, 호출한 시점으로 다시 돌아오지 않으므로 함수 호출 후 다음 라인에 return을 꼭 해줘야한다.
해결해야 하는 순서대로 코드를 짜면 되므로 크게 어렵지 않은 문제다.

주의할점으로는 무조건 반시계방향으로 탐색하면 되는 줄 알았는데, 바뀐 방향을 기준으로 두고 다음 왼쪽방향이 무엇인지 조건을 걸어주어야 한다.
그래서, 쉽게 생각하기 위해 if문으로 하나씩 조건을 걸어서 현재 방향에 대한 왼쪽 방향을 구해줬다.(후진도 마찬가지)
다른 코드를 보니 (d+3)%4로 다음 왼쪽에 해당하는 방향을 간결하게 구해줄 수 있었다.

1. 재귀

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//로봇청소기
public class Main {
	static int N, M; //세로, 가로
	static int[] di = {-1, 0, 1, 0}; //북동남서
	static int[] dj = {0, 1, 0, -1};
	static int Ans; //청소영역개수
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M]; //전체 맵

		st = new StringTokenizer(br.readLine());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());


		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				map[i][j]= Integer.parseInt(st.nextToken());
			}
		}//input

		map[r][c] = -1;

		recur(r, c, d);


		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == -1) Ans++;
			}
		}

		System.out.println(Ans);
	}

	static void recur(int r, int c, int d) {
		int nd = 0; //다음 방향

		//2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
		for(int i=0; i<4; i++) {
			if(d == 0) nd=3;
			else if(d==1) nd=0;
			else if(d==2) nd=1;
			else nd=2;

			int nr = r + di[nd];
			int nc = c + dj[nd];

			//왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 처음 부터 진행한다.
			if(nr>=0 && nr<N && nc>=0 && nc<M && map[nr][nc]!=-1 && map[nr][nc] != 1) {
				map[nr][nc] = -1; //1. 현재 위치 청소
				recur(nr, nc, nd);
				return;
			}else{//왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
				d = nd;
			}
 		}

		//네 방향 모두 청소가 이미 되어있거나 벽인 경우에는,
		//바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
		int bd = 0; //후진방향
		if(d==0) bd=2;
		else if(d==1) bd=3;
		else if(d==2) bd=0;
		else bd=1;

		int nr = r + di[bd];
		int nc = c + dj[bd];

		if(nr>=0 && nr<N && nc>=0 && nc<M && map[nr][nc] != 1) {
			recur(nr, nc, d);
			return;
		}else return; // 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
	}
}

2. while문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, M; // height, width
	static int[][] map;
	static int d;
	static int nowX, nowY;
	static int[] di = { -1, 0, 1, 0 }; // north, east, south, west
	static int[] dj = { 0, 1, 0, -1 };
	static int Ans = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];

		st = new StringTokenizer(br.readLine());
		nowX = Integer.parseInt(st.nextToken());
		nowY = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		} // End input
		
		// 1:wall, -2:cleaned
		while (true) {
			// showMap();

			// 1. clean current position
			if (map[nowX][nowY] == 0) {
				map[nowX][nowY] = -2;
				Ans++;
			}
			
			// 2. 4 direction search
			int nx = 0, ny = 0, nd = 0;
			
			boolean endSearch = false;
			for (int i = 0; i < 4; i++) {
				
				nd = (d + 3) % 4; // next direction
				nx = nowX + di[nd];
				ny = nowY + dj[nd];

				// a
				if (nx >= 0 && nx < N && ny >= 0 && ny < M  && map[nx][ny] != -2 && map[nx][ny] != 1) {
					nowX = nx;
					nowY = ny;
					d = nd;
					break;
				} else d = nd;
				
				
				if(i == 3) endSearch = true;
			}//End 4search
			
			int rd = 0;
			//c
			if (endSearch) { 
				// go rear
				if(d==0) rd=2;
				else if(d==1) rd=3;
				else if(d==2) rd=0;
				else rd=1;

				int rx = nowX + di[rd];
				int ry = nowY + dj[rd];
				
				if (rx >= 0 && rx < N && ry >= 0 && ry < M && map[rx][ry] != 1) {
					nowX = rx;
					nowY = ry;
				} else break;
				
			}
		} // End clean
		System.out.println(Ans);
	}
}