백준[JAVA] 14503 로봇청소기 + 예제2번 20번이 나오는 이유 예측(자바)

 

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

----------------------------------------------------------------------------------------------------------------

주어진 행동양식 차례대로 탐색을 진행하기때문에 dfs로 풀었습니다.

저도 예제2가 출력값으로 20이 자꾸 나와서 고생했는데 예측할만한 이유가 있었습니다.

1. 셋째줄부터 주어지는 입력값 1을 빈칸이지만 청소를 하지않는 곳으로 착각

2. 둘째줄 방향에대한 입력값 1을 서쪽으로 착각한 경우(0:북쪽 1:동쪽 2:남쪽 3:서쪽 저는 북에서 회전하면 서쪽이므로 1을 서쪽으로 착각했습니다)

3. 후진을 할경우 북쪽인 경우만 생각해서 좌표(행+1,열)으로 시작하는 경우(후진을 할때도 방향에따라 후진했을때 좌표값이 다릅니다)

 

저는 1 2 3을 동시에 착각해서.. 예제 2번 출력값이  20으로 나왔었습니다 다들 유의하세요!

->풀이한 코드

 
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
    static int N;
    static int M;
    static int answer;
    static int[][] pan;//벽과 칸을 기록
    static boolean[][] isChecked;//청소했는지 안했는지 여부
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        answer = 1;
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        pan = new int[N][M];
        isChecked=new boolean[N][M];
        st = new StringTokenizer(br.readLine());
        int startX = Integer.parseInt(st.nextToken());
        int startY = Integer.parseInt(st.nextToken());
        int dir = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                pan[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        isChecked[startX][startY]=true;
        bfs(startX, startY, dir,0);
        System.out.println(answer);
 
 
    }
 
    public static void bfs(int x, int y, int dir, int temp) {
        if(temp==4){//다시 원점으로 왔을경우 후진할지 말지에 대한 판단
            if(dir==0){
                if(pan[x+1][y]==0){
                    if(!isChecked[x+1][y]){
                    isChecked[x+1][y] = true;
                    answer++;
 
                }
                    bfs(x+1,y,dir,0);//방향은 유지한채로 다시 시작
            }else {return;}//후진이 안되면 종료
            }
            else if(dir==1){
                if(pan[x][y-1]==0){
                        if(!isChecked[x][y-1]){
                            isChecked[x][y-1] = true;
                            answer++;
 
                        }
                    bfs(x,y-1,dir,0);
                    }else {return;}
            }
            else if(dir==2){
 
                if(pan[x-1][y]==0){
                    if(!isChecked[x-1][y]){
                        isChecked[x-1][y] = true;
                        answer++;
 
                    }
                    bfs(x-1,y,dir,0);
                }else {return;}
            }
            else{
                if(pan[x][y+1]==0){
                    if(!isChecked[x][y+1]){
                        isChecked[x][y+1] = true;
                        answer++;
 
                    }
                    bfs(x,y+1,dir,0);
                }else {return;}
 
            }
        }
        else{
 
        if (dir == 0) {
            if (isRange(x,y-1)&&!isChecked[x][y-1] && pan[x][y - 1] == 0) {// 빈칸이고 청소를안했으면 전진
                isChecked[x][y-1] = true;
                answer++;
                bfs(x, y - 1, 3, 0);//북쪽에서 왼쪽회전하므로 
            } else if (isChecked[x][y-1] || pan[x][y - 1] > 0) {
                bfs(x, y, 3, temp + 1);
            }
        } else if (dir == 1) {
 
            if (isRange(x-1,y)&&!isChecked[x-1][y] && pan[x-1][y ] == 0) {
                isChecked[x-1][y] = true;
                answer++;
                bfs(x-1, y , 0, 0);
            } else if (isChecked[x-1][y] || pan[x-1][y] > 0) {
                bfs(x, y, 0, temp + 1);
            }
 
        } else if (dir == 2) {
            if (isRange(x,y+1)&&!isChecked[x][y+1] && pan[x][y + 1] == 0) {
                isChecked[x][y+1] = true;
                answer++;
                bfs(x, y + 1, 1, 0);
            } else if (isChecked[x][y+1] || pan[x][y + 1] > 0) {
                bfs(x, y, 1, temp + 1);
            }
        }else {
            if (isRange(x+1,y)&&!isChecked[x+1][y] && pan[x+1][y] == 0) {
                isChecked[x+1][y] = true;
                answer++;
                bfs(x+1, y , 2, 0);
            } else if (isChecked[x+1][y] || pan[x+1][y] > 0) {
                bfs(x, y, 2, temp + 1);
            }
        }}
    }
 
    public static boolean isRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}