백준_14503 로봇 청소기(자바) / 구현 + 재귀

시간 & 메모리 제한

문제

입력 & 출력

예제

구현을 통한 문제풀이

package com.Back;

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

public class Back_14503 {
	static int R,C,x,y,dir;
	static int [][] map;
	static boolean [][] visited;
	static int ans =0; 
	//북 동 남 서
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,1,0,-1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];
		visited = new boolean[R][C];
		
		st = new StringTokenizer(br.readLine());
		
		x = Integer.parseInt(st.nextToken());
		y = Integer.parseInt(st.nextToken());
		
		dir = Integer.parseInt(st.nextToken());
		
		// 맵 입력
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		clean(x,y,dir);
		System.out.println(ans);
	}
	private static void clean(int x,int y,int dir) {
		boolean sign = false;
		
		if(!visited[x][y]) {
			ans++;
			visited[x][y]=true;
		}
		
		for (int k = 0; k < 4; k++) {
			int xx = x + dx[(dir+3)%4];
			int yy = y + dy[(dir+3)%4];
			
			if(map[xx][yy]==0 && !visited[xx][yy]) {
				clean(xx,yy,(dir+3)%4);
				sign=true;
				break;
			}
			dir = (dir+3)%4;
		}
		
		if(sign==false) {
			int xx = x+dx[(dir+2)%4];
			int yy = y+dy[(dir+2)%4];
			
			if(map[xx][yy]==0) {
				clean(xx,yy,dir);
			}
		}
	}

}

- 이 문제의 경우 방향에 대한 이해를 하면 구현할 수 있는 문제라고 생각합니다.

 

- 각 위치에서 왼쪽으로 바라보고 안되면 반시계 방향으로 돌려보는 과정을 반복하고 있습니다.

 

- 또한 만약에 갈수가 없다면 다시 뒤로 가는 것도 고려를 해야하는 부분입니다.

 

- 두 번째 예시의 경우 이동에 대한 부분을 그린 그림입니다.