로봇 청소기 - 백준 14503 (Java)

https://www.acmicpc.net/problem/14503

 

풀이

1. 현재 위치에서 왼쪽으로 90도씩 회전하면서 해당 방향으로 이동할 수 있다면 이동한다.

2. 이동한 위치에서 또 왼쪽으로 90도씩 회전하면서 해당 방향으로 이동할 수 있다면 이동한다.

3. 만일 모든 방향으로 이동할 수 없을 경우, 현재 위치에서 1칸 뒤 (현재 방향에서 반대 방향)가 빈 칸이면 (청소를 이미 했더라도) 현재 방향을 유지한 채 이동하고, 1칸 뒤가 벽이라면 작동을 멈춘다.

 

현재 위치에서 조건 따지고, 이동하고서도 똑같이 조건 따지고... 하는 과정이 계속 진행되는 형태라 재귀로 접근했다.

 

입력을 받고 여러 변수를 초기화하고 재귀 메서드를 처음 호출하는 main()

static boolean[][] isVisited;
static int[][] board;
static int row, col;
//청소하는 칸의 개수
static int cnt;

//북 동 남 서 순서
static final int[] DIRECTIONS_ROW = {-1, 0, 1, 0};
static final int[] DIRECTIONS_COL = {0, 1, 0, -1};

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(bf.readLine() , " ");

    row = Integer.parseInt(st.nextToken());
    col = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(bf.readLine() , " ");

    int startRow = Integer.parseInt(st.nextToken());
    int startCol = Integer.parseInt(st.nextToken());
    int startDirection = Integer.parseInt(st.nextToken());

    board = new int[row][col];
    isVisited = new boolean[row][col];

    for (int i = 0; i < row; i++) {
        st = new StringTokenizer(bf.readLine() , " ");
        for (int j = 0; j < col; j++) {
            board[i][j] = Integer.parseInt(st.nextToken());
        }//for end
    }//for end

    //출발 장소 count
    cnt++;
    isVisited[startRow][startCol] = true;
    //재귀함수 호출
    dfs(startRow, startCol, startDirection);

    //청소하는 칸의 개수 출력
    System.out.println(cnt);
}

 

 

재귀 dfs()

현재 row, col, direction을 파라미터로 하는 재귀 메소드

 

90도씩 회전하면서 그 방향으로 이동 가능한지 확인

- 이동 가능하면 그 위치로 이동한 후 재귀 호출

- 이동 가능하지 않은 경우, 반대 방향 칸이 빈 칸이면 현재 방향을 유지한 채 반대 방향 칸으로 이동하고, 반대 방향 칸이 벽이면 중단

 

public static void dfs(int nowRow, int nowCol, int nowDirection) {
    //빈 칸 0, 벽 1

    //왼쪽으로 회전
    int i = 1;
    for (; i <= 4; i++) {
        //새로운 방향
        int newDirection = (nowDirection-i<0)? nowDirection-i+4 : nowDirection-i;
        //새로운 방향으로 한 칸 이동
        int newRow = nowRow + DIRECTIONS_ROW[newDirection];
        int newCol = nowCol + DIRECTIONS_COL[newDirection];

        //만일 새로 이동한 칸으로 진행할 수 있다면 이동!
        //(방문 여부 true, 개수+1, 새로 이동한 칸에서 재귀 호출)
        if ((newRow>0 && newRow<row-1)
                && (newCol>0 && newCol<col-1)
                && board[newRow][newCol] == 0
                && !isVisited[newRow][newCol]) {
            cnt++;
            isVisited[newRow][newCol] = true;
            dfs(newRow, newCol, newDirection);
            //현재 위치에서 어느 한 방향으로 이동했다면 
            //더 이상 현재 위치에서는 진행하지 않으므로 break
            break;
        }
    }//for end

    //모든 방향으로 더 이상 나갈 수 없을 때
    if (i==5) {
        //현재 방향의 반대 방향
        int oppoDirection = (nowDirection+2>3)? nowDirection-2 : nowDirection+2;
        //반대 방향으로 한 칸 이동
        int newRow = nowRow + DIRECTIONS_ROW[oppoDirection];
        int newCol = nowCol + DIRECTIONS_COL[oppoDirection];

        //반대 방향으로 한 칸이 빈 칸이라면 이동!
        if ((newRow>0 && newRow<row-1)
                && (newCol>0 && newCol<col-1)
                && board[newRow][newCol] == 0) {
            dfs(newRow, newCol, nowDirection);
        }//if end
    }//if end

}//dfs() end