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

1. 소요시간 : 55분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 5
4. 문제 유형 : 구현, 시뮬레이션
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/14503
8. 푼 날짜 : 2023.04.07

1. 사용한 자료구조 & 알고리즘

구현 !

2. 사고과정

문제에 있는 그대로를 구현했는데, 그러자 시간 초과가 났다.
어떻게 하면 시간초과가 안 나게 할 수 있을까를 꽤 오래 고민한 것 같다.
10분 정도 고민하다가
현재 칸의 주변

현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

에서 계속해서 같은 장소를 queue 가 중복 탐색을 하고 있다는 것을 알게 되었다. 따라서 필요한 경우에는 중복탐색하지 않고 즉시 return 해주는 작업을 추가해주니 풀 수 있었다.

3. 풀이과정

1. 청소되지 않은 구역을 0, 벽을 1, 청소 한 구역을 2로 생각
2. 문제에 있는 그대로를 구현. 이 과정에서 queue를 사용.
3. 주석에 해석을 담았음.

4. 소스코드

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

public class Main{

	static int dy[]= {-1,0,1,0};
	static int dx[]= {0,-1,0,1};
	static int Y,X,straight;
	static char map[][];
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		map=new char[N][M];
		
		st=new StringTokenizer(br.readLine());
		Y=Integer.parseInt(st.nextToken());
		X=Integer.parseInt(st.nextToken());
		straight=Integer.parseInt(st.nextToken());
		for(int i=0;i<map.length;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<map[0].length;j++) {
				map[i][j]=st.nextToken().charAt(0);
		
			}
		}
		
		int result = cleanArea();
		System.out.println(result);

	}
	public static int cleanArea() {
		Queue<Integer[]> queue=new LinkedList<>();
		queue.add(new Integer[] {Y,X,straight});
		int count = 0;
		
	
		while(!queue.isEmpty()) {
			Integer temp[]= queue.poll();
			int nowY=temp[0];
			int nowX=temp[1];
			int dir=temp[2];
			
			
			//현재 구역 청소 안됐으면 청소함.
			if(map[nowY][nowX]=='0') {
				map[nowY][nowX]='2';
				count++;
			}
			
			
			//청소 해야하는가? true 면 해야함. false 면 할필요 없음.
			boolean shouldClean = check(nowY,nowX);
			
			if(!shouldClean) {
				//4칸다 청소가 돼있으면
				
				switch(dir) {
				case 0: nowY++; break;
				case 1: nowX--; break;
				case 2: nowY--; break;
				case 3: nowX++; break;
				}
				//이동 불가하면 count를 리턴.
				if(nowY<0||nowX<0||nowY>=map.length||nowX>=map[0].length)
					return count;
				//이동 했는데 벽이면 count를 리턴
				else if(map[nowY][nowX]=='1')
					 return count;
				//이동 가능하면 이동한 좌표를 넣음
				else
					queue.add(new Integer[] {nowY,nowX,dir});
					
					
			}
			else {
            //방향 전환
				dir --;
				if(dir== -1) dir = 3;
				int prevY=nowY;
				int prevX=nowX;
				switch(dir) {
				case 0: nowY--; break;
				case 1: nowX++; break;
				case 2: nowY++; break;
				case 3: nowX--; break;
				}
				//좌표를 벗어났다면, 이전 좌표를 넣음.
				if(nowY<0||nowX<0||nowY>=map.length||nowX>=map[0].length) 
					queue.add(new Integer[] {prevY,prevX,dir});
				//벽이거나, 청소 했다면 이전 좌표 넣음
				else if(map[nowY][nowX]=='1'||map[nowY][nowX]=='2')
					queue.add(new Integer[] {prevY,prevX,dir});
				//청소 안한 구역이면 한 칸 전진.
				else
					queue.add(new Integer[] {nowY,nowX,dir});
				
			}
			
			
			
		}
		
		
		return 0;
	}
	public static boolean check(int nowY,int nowX) {
		for(int i=0;i<4;i++) {
			int nextY=nowY+dy[i];
			int nextX=nowX+dx[i];
			if(nextY<0||nextX<0||nextY>=map.length||nextX>=map[0].length)
				continue;
			if(map[nextY][nextX]=='1'||map[nextY][nextX]=='2')
				continue;
			
			return true;
			//청소 해야하는 칸이 남아있음
			
		}
		
		//청소 할 필요 없음
		return false;
	}
	
}

5. 결과

6. 회고

이번 문제는 스스로 이해하고 다른 해석 지문을 보지 않고 풀었다 !
사실 다른 사람의 코드를 본다는게 이 사람이 어떻게 풀었나 볼 때도 있지만 문제가 무슨 소리인지 이해하기 위해 보는 경향이 많은 것 같다 ㅜ.ㅜ
문제 해석 실력을 키우자 !

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212