[백준] G5 14503 로봇 청소기 (java)

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

14503번: 로봇 청소기

 

풀이

 

1) 로봇 청소기의 위치와 방향을 저장할 클래스 Node 를 생성. 청소의 유무를 저장할 boolean형 배열 isCleaned[][] 선언, 입력된 영역을 표시할 map[][] 배열 선언.

2) BFS 방식으로 이동할 영역을 탐색한다.

2-1) 현재 위치한 좌표가 청소 되지 않은 경우 isCleaned 를 true 로 바꾸고 횟수 1 추가.

2-2) 방향 전환 규칙을 찾고 공식을 만들고 다음 좌표를 계산한다.

2-3) 다음 좌표가 범위를 벗어나지 않으며 청소를 하지 않은 구역이며 벽이 아닐경우 새로운 좌표 + 방향을 queue에 넣는다.

2-4) 4방향을 다 탐색해도 갈곳이 없을 경우 뒤로 이동한다.

3) 2) 를 반복한다.

4) 청소된 횟수를 출력한다.

 

주의사항

 

1) 딱히 없다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G5_14503_로봇청소기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,map[][];
	static boolean isCleaned[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		map = new int[N][M];
		isCleaned = new boolean[N][M];
		tokens = new StringTokenizer(input.readLine());
		int startR = Integer.parseInt(tokens.nextToken());
		int startC = Integer.parseInt(tokens.nextToken());
		int startD = Integer.parseInt(tokens.nextToken());
		
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<M; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}
		}
		cleaning(startR,startC,startD);
	}
	private static void cleaning(int startR, int startC, int startD) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(startR, startC, startD));
		int cnt = 0;
		outer : while(!queue.isEmpty()) {
			Node front = queue.poll();
//			System.out.println(front);
			if(!isCleaned[front.r][front.c]) {
				isCleaned[front.r][front.c] = true;
				cnt++;
			}
			int nd = front.d;
			for(int d=0; d<4; d++) {
				nd = (nd+3)%4; // 방향 바꾸기~
	
				int nr = front.r + dr[nd]; // 방향 공식 발견함
				int nc = front.c + dc[nd];
				if(isIn(nr, nc) && !isCleaned[nr][nc] && map[nr][nc] == 0) {
					queue.offer(new Node(nr, nc, nd));
					continue outer;
				}
			}
			int reverseD = (nd+2)%4;
			int nr = front.r + dr[reverseD];
			int nc = front.c + dc[reverseD];
			if(isIn(nr, nc) && map[nr][nc] == 0) {
				queue.offer(new Node(nr, nc, nd));
			}
		}
		System.out.println(cnt);
	}
	static class Node{
		int r;
		int c;
		int d;
		public Node(int r, int c, int d) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
		}
		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + ", d=" + d + "]";
		}
	}
	static int dr[] = {-1,0,1,0}; // 북, 동, 남, 서
	static int dc[] = {0,1,0,-1};
	static boolean isIn(int r, int c) {
		return(r>=0 && c>=0 && r<N && c<M);
	}
	static String src =
			"11 10\r\n"
			+ "7 4 0\r\n"
			+ "1 1 1 1 1 1 1 1 1 1\r\n"
			+ "1 0 0 0 0 0 0 0 0 1\r\n"
			+ "1 0 0 0 1 1 1 1 0 1\r\n"
			+ "1 0 0 1 1 0 0 0 0 1\r\n"
			+ "1 0 1 1 0 0 0 0 0 1\r\n"
			+ "1 0 0 0 0 0 0 0 0 1\r\n"
			+ "1 0 0 0 0 0 0 1 0 1\r\n"
			+ "1 0 0 0 0 0 1 1 0 1\r\n"
			+ "1 0 0 0 0 0 1 1 0 1\r\n"
			+ "1 0 0 0 0 0 0 0 0 1\r\n"
			+ "1 1 1 1 1 1 1 1 1 1";
}

 

후기

 

 뒤로 이동하는 부분이 틀려서 조금 애먹었는데 문제이해를 잘 못했었다. 예제 3번의 이동경로를 구글링을 통해 확인한 후에 이해할 수 있었다.