[백준] code.plus(시뮬레이션과 구현,JAVA)14503번, 로봇 청소기

문제 링크

14503번: 로봇 청소기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 로봇 청소기는 현재 위치를 청소한 뒤 바라보는 방향을 왼쪽으로 변경합니다.

2. 변경한 방향에 앞이 청소할 수 있으면 전진, 벽이거나 청소를 했다면 다시 왼쪽으로 회전합니다.

3. 왼쪽으로 회전 4번을 했을 시 후진을 하며 만약 후진할 때 벽이 있으면 로봇 청소기는 종료됩니다.

 

이 문제에서 로봇 청소기가 왼쪽으로 회전하여 탐색할 때 처리하는 것을 해결하는 것이 핵심입니다.

 

로봇 청소기가 왼쪽으로 회전하는 것을 재귀를 통해 해결하였습니다.

 

회전을 4번하였다면 원래 방향으로 돌아왔기 때문에 후진을 하도록 구현하였습니다.

 

지도의 각 구역을 청소했는지 확인을 위해 Boolean 형 배열을 이용하여 확인하였습니다.

 

각 구역을 청소할 때마다 result에 +1을 진행합니다.

 

청소기가 멈추었을 때 result값은 청소기가 청소한 구역의 개수이므로 결과로 출력합니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값들을 저장합니다.

2. 로봇 청소기가 회전 횟수에 따른 재귀를 통해서 탐색을 진행합니다.

3. 로봇 청소기가 멈춘 뒤에는 result를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 지도의 정보와 로봇 청소기 위치 및 방향을 저장하였습니다.
• 로봇 청소기가 재귀를 통해 탐색하는 cal함수 실행하였습니다.
• 로봇 청소기가 청소한 구역의 개수가 저장된 result를  BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 회전 횟수에 따른 재귀를 진행하였습니다.
• cal함수는 회전 후 해당 방향이 청소하지 않은 구역이면 전진하고 벽이나 청소한 구역이면 다시 회전합니다.
• cal함수는 4번의 회전을 했다면 후진을 진행하며 후진 시 벽이면 작동을 중지합니다.
• cal함수는 지도의 구역을 청소하였다면 result + 1을 진행합니다.

import java.util.*;
import java.io.*;
public class Main{
	static int N,M,r,c,d;
	static int[][] space;
	static int[] dx = {-1, 0, 1, 0};	//북동남서 x값 변경
	static int[] dy = {0, 1, 0, -1};	//북동남서 y값 변경
	static boolean[][] visited;		//지도 구역 방문 확인 배열
	static int result=1;		//청소한 구역 개수 저장 변수
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	N =Integer.parseInt(st.nextToken());
    	M =Integer.parseInt(st.nextToken());
    	space = new int[N][M];
    	visited = new boolean[N][M];
        //청소기 초기 위치 및 방향 저장
    	st = new StringTokenizer(br.readLine()," ");
    	r = Integer.parseInt(st.nextToken());
    	c = Integer.parseInt(st.nextToken());
    	d = Integer.parseInt(st.nextToken());
        //지도 관련 정보 배열에 저장
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		for(int j=0;j<M;j++)
    			space[i][j] = Integer.parseInt(st.nextToken());
    	}
    	visited[r][c] = true;		//초기 위치 청소 완료 확인
    	cal(r,c,d,0);		//로봇 청소기 탐색함수 실행
    	bw.write(result + "\n");	//로봇 청소기 청소한 구역 개수 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //로봇 청소기 작동하여 탐색하는 재귀 함수
    static void cal(int r, int c,int direction, int check){
    	if(check==4){		//왼쪽 방향으로 4번 회전시
    		int tempDirection = (direction+2)%4;	//후진 방향
    		int tempR = r + dx[tempDirection];
    		int tempC = c + dy[tempDirection];
    		if(space[tempR][tempC]==1)	//후진 시 벽이면 작동 종료
    			return;
    		else		//벽이 아니면 후진 진행
    			cal(tempR,tempC,direction,0);
    	}else {
        	//왼쪽 방향 이동
        	int tempDirection = direction-1<0?3:direction-1;
        	int tempR = r + dx[tempDirection];
        	int tempC = c + dy[tempDirection];
            	//청소하지 않은 구역일 때
        	if(space[tempR][tempC]==0 && !visited[tempR][tempC]) {
            	visited[tempR][tempC] = true;
        		result++;
        		cal(tempR,tempC, tempDirection, 0);		//전진
        	}else {		//벽이거나 청소한 구역일 때
        		cal(r,c,tempDirection, check+1);	//방향 전환
        	}
        	return;
    	}
    }
}