[자바] 백준 14503 - 로봇 청소기 (java)

목차

문제 : boj14503

 

 

필요 알고리즘

• 구현, 시뮬레이션, 탐색 (bfs, dfs 등)
  
  • 그냥 문제에 제시된 대로 구현하는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  딱히 풀이라 할 부분은 없을 것 같다. 문제에 제시된대로 구현하면 된다. 따라서 내 코드를 기준으로 어떤식으로 구현했는지만 얘기해보겠다.

 

  우선 '방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다.' 라는 부분은 그냥 미리 맵의 크기를 상하좌우로 +1씩 늘려놓고, 전부 벽이라고 체크해두면 별도로 맵을 벗어났음을 판단하기 위해 조건문이 들어가지 않아도 되서 편하다.

v = new int[r + 2][c + 2];	// 상하좌우 +1 칸씩 늘림
for (int[] row : v) Arrays.fill(row, BLOCKED);	// 일단은 맵 전부 벽이라고 체크

for (int i = 1; i <= r; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 1; j <= c; j++) {
        if (st.nextToken().charAt(0) == '0')	// 입력받으면 빈칸인곳만 빈칸으로 변경
            v[i][j] = BLANK;
    }
}

 

 

  이후로는 bfs 혹은 dfs 등 아무꺼나 써서 탐색을 진행하면 된다. 내 경우엔 dfs를 썼다.

simulation(sr+1, sc+1, d);	//sr+1, sc+1인 이유는 상하좌우 +1칸씩 늘려놨기 때문임.

 

 

  이하 문제에 제시된 조건대로 짰다. 주석을 참고해보자.

주의할점

1. 상태는 총 3가지가 필요하다. 빈칸(BLANK), 벽(BLOCKED), 청소완료된 곳(CLEAN). 예를들어 후진했더니 이미 청소완료된 곳이라고 거기서 종료하면 안된다. 최초 입력이 벽인 곳에서 종료해야 한다.

2. 4방향 모두 빈칸이 없을 경우 '후진' 한다고 되어 있다. 즉, 바라보고 있는 방향은 그대로 둔 채 뒤로 이동해야 한다는 점에 주의해야 한다.

3. 코드에서 d = (d+3)%4 가 반시계 방향으로 도는 코드인 이유는, d-1이 반시계방향으로 도는건데 이러면 d가 -1일 때 d를 3으로 바꾸는 조건문이 들어가야 되는데 조건문 넣기 귀찮으므로 d-1+4를 해준거다. 여기서 4는 4%4 == 0 이므로, 나머지 연산의 이하 성질로 인해 더해도 상관없는 숫자이다.

private void simulation(int cr, int cc, int d) {
    if (v[cr][cc] == BLOCKED) return;   // 후진한 곳이 벽이라면 종료

    if (v[cr][cc] == BLANK) {   // 현재칸이 빈칸이면
        answer++;	// 답을 카운팅하고
        v[cr][cc] = CLEAN;	// 청소 ㄱㄱ
    }

    for (int i = 0; i < 4; i++) {
    	d+=3;   // 반시계 방향으로 돈다.
    	d%=4;
    	if (v[cr+DR[d]][cc+DC[d]] == BLANK) { // 돈 방향으로 한칸 가보니 빈칸이라면
        	simulation(cr+DR[d], cc+DC[d], d);    // 해당 빈칸으로 진행하고
        	return;	// 더이상 진행할 필요가 없다.
    	}
    }
    
    // 이하 4방향 중 빈칸이 없던 경우이므로, 뒤로 한칸 가면 된다.
    // 주의할점은 '후진'이므로 보고 있던 방향이 바뀌면 안된다.
    simulation(cr+DR[(d+2)%4], cc+DC[(d+2)%4], d);
}

 

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private static final int[] DR = {-1, 0, 1, 0};
    private static final int[] DC = {0, 1, 0, -1};
    
    private static final int BLOCKED = -1;
    private static final int BLANK = 0;
    private static final int CLEAN = 1;

    private int answer = 0;
    private int[][] v;

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int sr = Integer.parseInt(st.nextToken());
        int sc = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        v = new int[r + 2][c + 2];
        for (int[] row : v) Arrays.fill(row, BLOCKED);

        for (int i = 1; i <= r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= c; j++) {
                if (st.nextToken().charAt(0) == '0')
                    v[i][j] = BLANK;
            }
        }

        simulation(sr+1, sc+1, d);

        System.out.println(answer);
    }

    private void simulation(int cr, int cc, int d) {
        if (v[cr][cc] == BLOCKED) return;   //2.2

        if (v[cr][cc] == BLANK) {   //1
            answer++;
            v[cr][cc] = CLEAN;
        }

        for (int i = 0; i < 4; i++) {
            d+=3;   //3.1
            d%=4;
            if (v[cr+DR[d]][cc+DC[d]] == BLANK) {
                simulation(cr+DR[d], cc+DC[d], d);    //3.2, 3.3
                return;
            }
        }

        simulation(cr+DR[(d+2)%4], cc+DC[(d+2)%4], d);    // 2.1, 2.2
    }
}