[백준 14503]로봇 청소기/삼성 sw역량 테스트 기출(java)

문제 보러 가기

14503번: 로봇 청소기

이 문제는 그래프 탐색 + 구현 문제이다. 특별히 신경 써야 될 점은 2가지가 있다.

 

1. 방향 탐색 순서

2. 4방향 모두 벽 or 이미 청소 완료 일 때 -> 현재 방향으로 후진

 

 

 

 

 

문제풀이

- 문제에서 입력받은 청소기의 현재 위치 r, c 방향 d로부터 탐색.

- 현재 방향의 왼쪽 칸부터 탐색해야 하므로 반시계 방향 순서대로 탐색

ex) 현재 방향↑ 이면, ← ↓ → ↑방향 순서대로 탐색

 

- 여기서 주의점 , 문제에서는 처음 d를 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 나타내며 이는 시계방향 순으로 인덱스가 인덱스가 증가한다. 반시계 방향으로 탐색 배열을 정했다면 이 부분 수정 필요.

 

- 4방향을 순서대로 탐색하되 갈 수 있는 곳이 있으면 다음 방향을 탐색하지 않고 바로 이동

- 이동하면서 청소기의 위치인 r, c와 d를 업데이트, map [r][c]=2로 청소 표시,  청소 구역수 cnt++

 

- 만약 4방향이 모두 벽이거나 이미 청소했던 인덱스라면 flag를 이용해 if문에서 후진할 수 있게 한다.

- 후진은 마지막 탐색 방향을 유지하면서 반대방향으로 후진한다.

ex) ← ↓ → ↑방향으로 탐색을 하고 후진해야 한다면 ↑방향을 유지한 채로 ↓방향으로 한 칸 이동!

- 만약 후진하는 인덱스가 벽이라면 (map [r][c]==1) -> 탐색 종료

 

 

 

 

 

 

public class Ex_14503 {

	static int[][] map;
	static int cnt=1;
	static int n,m;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//삼성 sw 역량테스트 -로봇 청소기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		
		st = new StringTokenizer(br.readLine());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		
		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());
			}
		}
		map[r][c]=2;
		go(r,c,d);
		System.out.println(cnt);
	
	}
	static void go(int r, int c, int d) {
    	// 입력시 주어지는 시계방향 인덱스 수정
		d = d == 3 ? 1 : d == 1 ? 3 : d;
		int[] dx = {-1,0,1,0}; // 북 서  남 동
		int[] dy = {0,-1,0,1};
		
		while(true) {
        	//4방향 다 이동할 수 없을 때, 후진하기 위한 플래그변수
			boolean flag = true;
			for(int i=1;i<=4;i++) {
				int sx = r+dx[(d+i)%4];
				int sy = c+dy[(d+i)%4];
				if(sx < 0 || sy < 0 || sx >= n || sy >= m)
					continue;
				if(map[sx][sy]==1 || map[sx][sy]==2)
					continue;
				
                //이동할 수 있다면 변수들 업데이트
				r=sx;
				c=sy;
				d=(d+i)%4;
				flag = false;
				cnt++;
				map[r][c]=2;
				break;

			}
            //후진
			if(flag) {
				d =  (d+4)%4;
				r = r+dx[(d+2)%4];
				c = c+dy[(d+2)%4];
                //벽이면 인덱스 종료
				if(r < 0 || c < 0 || r >= n || c >= m)
					break;
				if(map[r][c]==1)
					break;
			}
			
		}
			
	}
}

 

* 지금 보니까 후진에서 d를 저렇게 안 해도 되겠네,,