BOJ 14503번: 로봇 청소기

문제

문제 바로가기> BOJ 14503번: 로봇 청소기

14503번: 로봇 청소기

 

풀이

문제에서 설명한 조건에 따라 구현해주면 된다!

문제의 2-1, 2-2 조건은 현재 위치에서 반 시계 방향으로 돌면서 청소 가능한 위치를 찾는 것을 의미한다!

[북 동 남 서] 순서의 배열이기 때문에, 반시계 방향은 -1을 해주면 된다.

이때, "북(0)-1 = -1" 이므로, 이를 방지하기 위해 "(d-1+4)%4 = (d+3)%4" 를 해준 것이다.

 

C++

#include<iostream>
#include<queue>
#define WALL 1
#define MAX 51
using namespace std;

struct DATA { int y, x, dir; };

int N, M;
int r, c, d;
int map[MAX][MAX];
bool visited[MAX][MAX];
int dy[] = {-1, 0, 1, 0}; // 북 동 남 서
int dx[] = {0, 1, 0, -1};

void input(){
    cin >> N >> M;
    cin >> r >> c >> d;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++) cin >> map[i][j];
    }
}

void solution(){

    queue<DATA> q;
    q.push({r, c, d});
    visited[r][c] = true;

    int ans = 1;
    while(!q.empty()){
        int y = q.front().y;
        int x = q.front().x;
        int dir = q.front().dir;
        q.pop();

        bool flag = true;
        int left = dir;
        for(int i=0; i<4; i++){
            left = (left+3)%4; // 반시계 방향 탐색 (2-1, 2-2)
            int ny = y+dy[left];
            int nx = x+dx[left];

            if(ny<0 || ny>=N || nx<0 || nx>=M) continue; // 범위를 벗어나는 경우
            if(visited[ny][nx] || map[ny][nx]==WALL) continue; // 이미 청소한 경우, 벽인 경우
            visited[ny][nx] = true; // 청소
            q.push({ny, nx, left});
            flag = false; ans++;
            break;
        }

        if(flag){ // 네 방향 모두 청소가 이미 되어있거나 벽인 경우
            int back = (dir+2)%4; // 뒤쪽
            int ny = y+dy[back];
            int nx = x+dx[back];

            if(ny<0 || ny>=N || nx<0 || nx>=M || map[ny][nx]==WALL) break; // 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽이 벽이라 후진도 할 수 없는 경우
            q.push({ny, nx, dir}); // 후진 가능한 경우
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}

 

Java

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

public class Main {
	
	static final int WALL =1 ;
	static final int MAX =51 ;	
	
	static class DATA{
		int r, c, d;

		public DATA(int r, int c, int d) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
		}
		
	}
	
	static int N, M, ans=0;
	static int r, c, d;
	static int map[][];
	static boolean visited[][];
	static int dy[] = {-1, 0, 1, 0}; // 북 동 남 서
	static int dx[] = {0, 1, 0, -1};

	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		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];
		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++) {
	        	map[i][j] = Integer.parseInt(st.nextToken());
	        }
	    }
		solution();
	}

	private static void solution() {
		Deque<DATA> q =  new ArrayDeque<>();
	    q.addLast(new DATA(r, c, d));
	    visited[r][c] = true;

	    int ans = 1;
	    while(!q.isEmpty()){
	        int y = q.peek().r;
	        int x = q.peek().c;
	        int dir = q.peek().d;
	        q.poll();

	        boolean flag = true;
	        int left = dir;
	        for(int i=0; i<4; i++){
	            left = (left+3)%4; // 반시계 방향 탐색 (2-1, 2-2)
	            int ny = y+dy[left];
	            int nx = x+dx[left];

	            if(ny<0 || ny>=N || nx<0 || nx>=M) continue; // 범위를 벗어나는 경우
	            if(visited[ny][nx] || map[ny][nx]==WALL) continue; // 이미 청소한 경우, 벽인 경우
	            visited[ny][nx] = true; // 청소
	            q.addLast(new DATA(ny, nx, left));
	            flag = false; ans++;
	            break;
	        }

	        if(flag){ // 네 방향 모두 청소가 이미 되어있거나 벽인 경우
	            int back = (dir+2)%4; // 뒤쪽
	            int ny = y+dy[back];
	            int nx = x+dx[back];

	            if(ny<0 || ny>=N || nx<0 || nx>=M || map[ny][nx]==WALL) break; // 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽이 벽이라 후진도 할 수 없는 경우
	            q.addLast(new DATA(ny, nx, dir)); // 후진 가능한 경우
	        }
	    }
	    System.out.println(ans);
	}
}