[백준] 로봇 청소기 14503 - JAVA

문제

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

14503번: 로봇 청소기

 

풀이

BFS 처럼 풀었지만 BFS문제는 아니고 BFS문제 같은 구현 문제다. 문제에서 나타나는 그대로 구현하면 된다.

 

주의해야 할 것은 다음 두가지다.

1. 후진

2. 반시계 방향으로 돌기

 

1. 후진을 수식으로 나타낸다면 다음과 같이 나타낼 수 있다.

(현재 방향 + 2 ) % 4

후진을 한다는 것은 현재방향과 반대이기 때문에 2를 더한후 4의 나머지를 구하면 된다.

 

2. 반시계 방향으로 도는건 조금 복잡하다.

4방향에 대해 반시계 방향으로 돌면서 청소안한 빈칸이 있는지 살펴봐야한다.

예를 들어, 현재 방향이 북(0)이면 3(서), 2(남), 1(동) 순으로 살펴봐야 된다. 

0, 3, 2, 1 과 같이 줄어들어야 하기때문에 수식은 다음과 같이 나타낼 수 있다. 이때 i는 0~3까지 증가한다.

(현재 방향 + 3 - i) % 4

 

코드

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

public class Main {

	static class Point{
		int x;
		int y;
		
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
	}
	
	static int n, m;
	static int board[][];
	static int result = 0;
	
	public static void main (String[] args) throws java.lang.Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		board = 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++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		bfs(r,c,d);
		
		System.out.print(result);
	}		
	
	static void bfs(int r, int c, int d) {
		// 0 북 1 동 2 남 3 서
		int dx [] = {-1, 0, 1, 0};
		int dy [] = {0, 1, 0, -1};
		
		Queue<Point> que = new LinkedList<>();
		boolean check [][] = new boolean[n][m];
		
		que.add(new Point(r, c));
		check[r][c] = true;
		result++;
		
		while(!que.isEmpty()) {
			Point cur = que.poll();
			
			boolean isEmpty = false;
			
			for(int i=0;i<4;i++) {
				int dir = (3+d -i) % 4; 
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				
				if(check[nx][ny] || board[nx][ny] == 1) continue; 
				
				que.add(new Point(nx, ny));
				check[nx][ny] = true;
				result++;
				d = dir;
				isEmpty = true;
				break;
			}
			
			if(!isEmpty) {
				int nx = cur.x + dx[(d+2)%4];
				int ny = cur.y + dy[(d+2)%4];
				
				if(board[nx][ny] == 1)
					return;
				
				que.add(new Point(nx, ny));
			}
			
		}
		
	}
}