[JAVA/BFS] 백준 14503 로봇청소기

1. 문제

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

14503번: 로봇 청소기

 

2. 풀이

• BFS를 이용해 풀이한다. 별도로 방문 배열을 사용하지 않고 방문한 부분을 2로 값을 변경했다.
• 이 문제에서 중요한 것은 방향을 정하는 것이다.
  • d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽 인데, 표에 해당하는 방향을 미리 배열로 지정해 놓고 왼쪽으로 이동할 때 (기존 방향 + 3) % 4로 다음 방향을 설정해준다.
• 청소를 하지 못한 경우 후진 처리를 해줘야 하는데,
  • 후진 처리 시 원래의 방향에서 후진 처리를 해줘야 한다.
  • 기존에 청소를 한 부분도 후진이 가능하므로, 벽이 아닌 경우(map[backX][backY] != 1) 후진 처리를 한다.

 

3. 코드

import java.util.*;
import java.io.*;

class Main{
	
	private static class Point{
		int x, y, d; // x, y 좌표와 방향
		
		public Point(int x, int y, int d) {
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
	
	private static int bfs(int N, int M, int x, int y, int d, int[][] map) {
		int areaCnt = 0;
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x, y, d));
		int[][] dir = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 북, 동, 남, 서
		
		while(!q.isEmpty()) {
			Point now = q.poll();
			if(map[now.x][now.y] == 0) {
				map[now.x][now.y] = 2; // 방문처리
				areaCnt++; // 청소한 구역 추가
			}
			
			boolean isCleaned = false; // 해당 좌표에서 청소 했는지
			int originD = now.d;
			for(int i = 0; i < 4; i++) {
				int newD = (now.d + 3) % 4;
				int nextX = now.x + dir[newD][0];
				int nextY = now.y + dir[newD][1];
				now.d = (now.d + 3) % 4;
				
				// 범위에서 벗어나면 청소하지 x
				if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
				
				if(map[nextX][nextY] == 0) {
					q.add(new Point(nextX, nextY, newD));
					isCleaned = true;
					break;
				}
			}
			
			if(isCleaned == false) {  // 네 방향 모두 청소되있거나 벽인 경우
				int backD = (originD + 2) % 4; // 원래의 방향에서 후진
				int backX = now.x + dir[backD][0];
				int backY = now.y + dir[backD][1];
				
				if(backX < 0 || backX >= N || backY < 0 || backY >= M) continue;
				if(map[backX][backY] != 1)  // 후진
					q.add(new Point(backX, backY, now.d));
				
			}
		}
		
		return areaCnt;
	}
	
	public static void main (String[] args) throws java.lang.Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] map = new int[N][N];
		
		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());
			}
		}
		
		int answer = bfs(N, M, r, c, d, map);
		
		System.out.println(answer);
	}
}