[Java] 백준 14503번 로봇 청소기

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

14503번: 로봇 청소기

이번 문제는 dfs를 이용하여 풀었습니다.

처음에는 아 그냥 방향만 잘 설정해서 청소하고 visit배열만 체크 잘해주면 쉽게 풀린다고 생각하여 문제도 제대로 안읽고 풀었다가 시간을 좀 쓴 문제였습니다.

후진과 벽이 있을 경우 작동이 멈춘다니.....;;

문제를 제대로 읽어야합니다!!!

 

다 풀고 나서 보니 좀더 쉽게 풀 수 있는 문제였습니다.

좀 생각을 안하고 풀었는데 저는 방향별 노가다로 청소구역을 일일이 다 설정했는데

이렇게 푸는 것 보다 dx와 dy배열을 사용하여 이동 경로를 미리 설정해두고 (방향 + 3)%4를 해주면 쉽게 풀 수 있었을 것이라고 생각이 듭니다.

 

저는 이미 풀어서 귀찮아서 좀 노가다 한 것으로 올리겠습니다.

 

package BJ;

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

public class BJ_로봇청소기 {
	static int N, M;
	static int r, c, d;
	static int[][] map;
	static boolean[][] visit;
	static int cnt = 1;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		visit = new boolean[N][M];
		
		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());
			}
		}
		visit[r][c] = true;
		dfs(r, c, d);
		System.out.println(cnt);
	}

	private static void dfs(int y, int x, int d) {
		int nx = 0;
		int ny = 0;
		boolean check = false;
		for (int i = 0; i < 4; i++) {
			if(d == 0) {
				nx = x - 1;
				ny = y;
				d = 3;
			}else if(d == 1) {
				nx = x;
				ny = y - 1;
				d = 0;
			}else if(d == 2) {
				nx = x + 1;
				ny = y;
				d = 1;
			}else if(d == 3) {
				nx = x;
				ny = y + 1;
				d = 2;
			}
			
			if(nx >= 0 && ny >= 0 && nx < M && ny < N && !visit[ny][nx] && map[ny][nx] == 0) {
				cnt++;
				visit[ny][nx] = true;
				dfs(ny, nx, d);
				check = true;
				break;
			}
		}
		
		if(!check) {
			if(d == 0) {
				nx = x;
				ny = y + 1;
			}else if(d == 1) {
				nx = x - 1;
				ny = y;
			}else if(d == 2) {
				nx = x;
				ny = y - 1;
			}else if(d == 3) {
				nx = x + 1;
				ny = y;
			}
			
			if(map[ny][nx] != 1) {
				dfs(ny, nx, d);
			}
		}
		
		
	}

}

 

Ysik Github : https://github.com/Y1sik/Algorithm/blob/main/BJ/BJ_%EB%A1%9C%EB%B4%87%EC%B2%AD%EC%86%8C%EA%B8%B0.java