[백준] 14503번 로봇 청소기 자바

문제

 

14503번: 로봇 청소기

 

 

문제 풀이

 

문제 자체를 이해하기 어려워서 구글링을 했다.

왼쪽 방향으로 돌면서 빈칸일 경우 해당 칸으로 이동하고 그 칸에서 다시 인접칸을 확인한다.

모두 청소했거나 벽이여서 갈 수 없을 경우는 현재 방향 기준 뒤를 확인해서 후진할 수 있는 경우에 후진하고, 벽이 있다면 그대로 작동을 멈춘다. dfs로 해당 문제에 나온 알고리즘 그대로 코드를 짰다. 

 

일단 나는 현재 방향에서 왼쪽으로 이동하고 바라보는 방향도 바꾸는 코드는 다음과 같은 2차원 배열을 이용해서 일일이 방향을 맞춰주었다. 각각의 열은 현재 방향일 때 왼쪽으로 이동할 행렬 값을 담고 있다.

	0	1	2	3
dr	0	-1	0	1
dc	-1	0	1	0

 

근데 원래 현재 방향에서 왼쪽 방향을 설정할 때 다음과 같이 하는 게 맞는 것 같다. 다른 사람들이 다 일케 했음.

direction = (direction + 3) % 4; 

0~3의 방향이 계속 반복되므로 3을 더해서 4로 나누어야 0에서 다시 3으로 돌아올 수 있어서 그런듯

→참고링크

 

 

소스 코드

 

public class s2_14503 {

	static int N, M, ans = 0;
	static int[][] map;
	static int[][] move = {{0, -1, 0, 1}, {-1, 0, 1, 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());
		int r = Integer.parseInt(st.nextToken());	//현재 좌표
		int c = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());	//현재 바라보고 있는 방향
		
		//input
		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());
		}
		
		//청소하는 칸의개수 출력
		dfs(r, c, d);
		System.out.println(ans + 1);
	}
			
	public static void dfs(int r, int c, int d) {
		map[r][c] = -1;	//현재 위치 청소
		//ans++;
		
		//현재 방향기준으로 왼쪽방향으로 탐색 진행
		int i = 0;
		for(i = 0; i < 4; i++) {
			int nr = r + move[0][d];
			int nc = c + move[1][d];
			if(d == 0)
				d = 3;
			else
				d -= 1;
			
			if(nr >= 0 && nr < N && nc >= 0 && nc < M) {	//격자 내이고
				if(map[nr][nc] == 0) {	//청소되지 않은 빈칸으로 이동해서 다시 dfs실행
					ans++;
					dfs(nr, nc, d);
					return;
				}
			}
		}
		
		//네 방향 모두 청소가 되어있거나 뒤쪽 방향 외에 모두 벽인 경우 
		//현재 방향 그대로 한 칸 후진
		int idx;
		if(d == 0)
			idx = 3;
		else
			idx = d-1;
		int nr = r + move[0][idx];
		int nc = c + move[1][idx];
			
		if(nr >= 0 && nr < N && nc >= 0 && nc < M)
			if(map[nr][nc] != 1)	//벽만 아니라면 후진이 가능함
				dfs(nr, nc, d);
	}

}