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

생각

문제 자체는 단순하다고 생각했습니다. 그런데 후진 조건을 잘못 생각해서 고생한 문제입니다ㅠㅠ 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 청소를 진행한다고 적혀있어서 정말 단순하게 '4방향 벽 and 4방향 청소이미한곳' 이라고 코드를 짰더니 계속 값이 적게 나왔습니다..

구글링을 통해 후진조건은 4방향을 청소기가 탐색했는데 더이상 청소불가 and 전진불가라는것을 알았습니다.

 

우선 문제의 전체적인 로직은 BFS탐색을 통해 청소기를 계속해서 이동시켰고 추가적으로 후진조건을 넣었습니다. 또한 이런 그래프 탐색 문제에 추가적인 조건이 있는 문제 같은 경우 BFS를 사용한 코드가 문제 해결에 적합할수있다는 것을 스터디원에게 배웠습니다!!

 

1. 청소기는 왼쪽방향부터 탐색하므로 dy,dx 값을 반시계방향(북->동->남->서)으로 초기화 시켜줍니다.  
2. BFS 로직을 이용합니다. 현재 노드에서 전진을 할수있는지 여부와 관계없이 방향은 무조건 왼쪽방향으로 돌아가야 합니다. 그렇기 때문에 dir변수를 다음 왼쪽 방향을 바라보게 업데이트 시켜줍니다 ( dir = (dir+3)%4 )
3. 그 다음 for문을 돌면서 사방탐색을 진행시킵니다. 왼쪽 방향으로 청소할수있으면 다음 좌표와 왼쪽 방향으로 바뀐 방향값을 큐에 넣어줍니다. 이때 map에 마스킹값을 줌으로써 visited와 같은 방문체크를 해주지 않아도 됩니다.
4. 왼쪽방향으로 전진할수없으면(청소를 못하거나, 벽일때) 탐색카운트를 증가시켜줍니다.
5. 사방탐색이 끝나고 청소기가 4 방향을 모두 돌아봤다면 이때 후진을 시켜줍니다.
   1. 후진하려는 y,x좌표를 계산합니다. 이때 후진은 반대 방향이므로 dy,dx 값에서 2씩 차이가 납니다. 그래서 (dir +2) % 4 연산을 통해 방향값을 재설정해줍니다.
   2. 후진하려는곳이 벽이 아니라면 청소기의 방향은 그대로 유지시켜줍니다. 다음으로 후진 y,x 값과 이전 방향과 동일한 방향값을 큐에 넣어주고 청소기 탐색 로직을 동일하게 진행합니다.
6. 모든 탐색이 끝난뒤 마스킹한값(청소한곳)을 카운트하여 출력합니다.

 

 

Java 코드

package com.java.algorithm;

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

class Pos{
	int y;
	int x;
	int dir;
	Pos(int y, int x, int dir){
		this.y = y;
		this.x = x;
		this.dir = dir;
	}
}

public class BAEKJOON_14503_로봇청소기 {
/**
 * 0 1 2 3 
 * 1. 현재위치 청소
 * 2. 현재위치에서 현재 방향 기준으로 왼쪽방향부터 차례대로 탐색!!! 사방탐색 여기서 진행해준다
 * 2-1. 왼쪽방향에 청소할수있는 공간 -> 그 방향으로 회전하고 한칸 전진하고 1번 부터 진행
 * 2-2. 왼쪽방향에 청소공간없음 -> 그 방향으로 회전하고 2번으로 돌아감.
 * 2-3. 네 방향 모두 청소됨 || 네 방향 모두 벽 (섞여 있어도 후진조건) -> 방향 유지하고 한칸 후진하고 2번으로 돌아감
 * 2-4. 네방향 모두 청소됨 && 네방향모두벽 && 뒤도벽이라 후진못함 -> end
 *  
 */
	//북 동 남 서
	static int dy[] = {-1, 0, 1, 0};
	static int dx[] = {0, 1, 0, -1};
	
	static int[][] map;

	//로봇청소기가 청소하는 칸의 개수
	public static void clean(int y, int x, int dir) {

		Queue<Pos> q = new LinkedList<Pos>();
		q.add(new Pos(y,x,dir));
		map[y][x] = 2;
		while(!q.isEmpty()) {
			Pos now = q.poll();
			
			int cleanCnt=0; // 탐색 카운트
			int nowY = now.y;//현재y
			int nowX = now.x;//현재x
			int nowDir = now.dir;//현재방향
			int ny,nx,nd;
			for (int k = 0; k < 4; k++) {
				nowDir = (nowDir + 3) % 4; //dir을 덮어씌워야 다음 탐색에 적용이된다.
				ny = nowY + dy[nowDir];
				nx = nowX + dx[nowDir];
				
				if(ny >= 0 && ny < map.length && nx >= 0 && nx < map[0].length) {
					//왼쪽 청소할수있음
					if(map[ny][nx] == 0) {
						//System.out.println("(" +ny+" , "+nx + ") dir : "+nowDir);
						//방향 회전하고 -> 한칸 전진 -> 바뀐 방향 다시 next에 넣어줌
						q.add(new Pos(ny, nx, nowDir));
						map[ny][nx] = 2;
						break;//처음부터 진행
					}else {
						cleanCnt++;
					}
				}
			}//사방탐색끝
			//네 방향 모두 탐색했으면
			if(cleanCnt == 4) {
				nd = (nowDir + 2) % 4;
				ny = nowY + dy[nd];
				nx = nowX + dx[nd];
				
				//후진한곳이 벽이 아니면 계속 진행
				//방향 유지하고 후진하고 2번으로 돌아감
				if(map[ny][nx] != 1) {
					q.add(new Pos(ny, nx, nowDir));
					map[ny][nx] = 2;
				}
			}
			
		}
		
	}
	
	//입력정복하기
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int ROW = Integer.parseInt(st.nextToken());
		int COL = Integer.parseInt(st.nextToken());
		
		String[] pos = br.readLine().split(" ");
		int startY = Integer.parseInt(pos[0]);
		int startX = Integer.parseInt(pos[1]);
		int startDir = Integer.parseInt(pos[2]);
		
		map = new int[ROW][COL];
		
		
		for (int i = 0; i < ROW; i++) {
			StringTokenizer s = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < COL; j++) {
				map[i][j] = Integer.parseInt(s.nextToken());
			}
		}
		
		//solve
		int answer=0;
		clean(startY, startX, startDir);
		for (int i = 0; i < ROW; i++) {
			for (int j = 0; j < COL; j++) {
				if(map[i][j] == 2) {
					answer++;
				}
			}
		}
		sb.append(answer);
		System.out.print(sb);
	}

}