[baekjoon] 백준 14503번 로봇 청소기 (골드5, java)

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

14503번: 로봇 청소기

---

이 문제는 구현하는 방법보다 문제 표현을 정확하게 이해하는 게 더 어려운 문제인 것 같다

재귀를 사용해서 갈 수 있는 방향이면 다시 함수를 호출할 수 있도록 하였고,

cnt 변수를 통해 네 방향을 모두 확인하고 나면 다시 후진할 수 있는지를 확인하여 할 수 있으면 함수를 호출하고,

할 수 없다면 함수를 종료하도록 구현하였다

 

네 방향을 확인할 때는 벽인지, 이미 청소를 하였는지를 확인해야 하고,

후진을 할 때는 벽인지만 확인해야 한다

 

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

public class Main {

	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	static int answer = 1;
	static int n;
	static int m;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine()," ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int[][] map = new int[n][m];
		
		st = new StringTokenizer(bf.readLine()," ");
		int curX = Integer.parseInt(st.nextToken());
		int curY = Integer.parseInt(st.nextToken());
		int dir = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(bf.readLine()," ");
			for(int j=0; j<m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		map[curX][curY] = 2; //청소 표시
		dfs(curX,curY,dir,map);
		System.out.println(answer);
	}
	
	public static void dfs(int x, int y, int dir, int[][]map) {
	
		int cnt = 0;
		int nx = x;
		int ny = y;

		while(cnt < 4) {
			dir = (dir-1)<0 ? 3: dir-1; //방향 전환
			cnt++;
			nx += dx[dir];
			ny += dy[dir];
			//해당 방향으로 갔을 때 범위를 벗어나거나, 벽이거나, 청소를 이미 한 곳이라면 다시 2번으로 돌아감
			if(!check(nx,ny) || map[nx][ny] == 1 || map[nx][ny] == 2) {
				nx -= dx[dir];
				ny -= dy[dir];
				continue;
			}
			answer++;
			map[nx][ny] = 2; // 청소 표시
			dfs(nx, ny,dir, map);
			return;	
		}
		//후진
		nx -= dx[dir]; 
		ny -= dy[dir]; 
		
		if(!check(nx,ny) || map[nx][ny] == 1) return; //후진하려는 곳이 벽인 경우
		dfs(nx,ny,dir,map);		
	}
	public static boolean check(int x, int y) { //범위 벗어난 경우 확인
		
		if(x < 0 || x > n-1 || y < 0 || y > m-1) return false;
		return true;
	}
}