로봇 청소기

문제: 로봇 청소기 (백준 14503번)

구조 분석

해당 문제는 로봇 청소기의 움직임을 구현하는 문제로 후진을 하는 움직임을 back tracking으로 구현해야 하는 dfs문제이다. 이런 구조의 문제는 dfs를 재귀함수로 구현하는 것이 더 쉽고 간단하다.

풀이 방법

우선 회전을 위해서 다음의 전역변수를 설정하고 왼쪽 방향, 뒷쪽 방향을 아래와 같이 구현한다.

// 위, 오른쪽, 아래, 왼쪽
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
// 왼쪽 방향  
int nd = (d + 3 - i) % 4;
// 뒷쪽 방향  
int back = d+2<4 ? d+2 : d-2;

다음으로 조건 중에 뒤로 갈 수 없는 상황이 생기면 종료한다. 이 부분을 놓쳐서 계속 삽질을 했다. 이는 재귀함수에서 단지 return 하는 것이 아니라 아예 종료를 시켜야 하므로 함수 내 해당 조건을 충족한다면 바로 답을 출력하고 종료하도록 한다.

if (map[bx][by] == 1) {
    cout << ans << "\n";
    exit(0);
}
else dfs({bx,by,d});

코드

#include <stdio.h>
#include <iostream>
#include <stack>
using namespace std;

int n, m;
int map[50][50] = {0,};
int visited[50][50] = {0,};
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int ans = 0;
typedef struct Robot {
    int x;
    int y;
    int d;
} Robot;

void dfs(Robot R) {
    int x = R.x;
    int y = R.y;
    int d = R.d;
    for (int i=0; i<4; i++) {
        int nd = (d + 3 - i) % 4;
        int nx = x + dx[nd];
        int ny = y + dy[nd];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m || map[nx][ny] == 1) continue;
        if (map[nx][ny] == 0 && visited[nx][ny] == 0) {
            ans++;
            visited[nx][ny] = 1;
            dfs({nx,ny,nd});
        }
    }
    int back = d+2<4?d+2:d-2;
    int bx = x + dx[back];
    int by = y + dy[back];
    if (bx >= 0 && bx <= n && by >= 0 && by <= m) {
        if (map[bx][by] == 1) {
            cout << ans << "\n";
            exit(0);
        }
        else dfs({bx,by,d});
    }
    
}

int main() {
    cin >> n >> m;
    int r, c, d;
    cin >> r >> c >> d;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> map[i][j];
        }
    }
    ans++;
    visited[r][c] = 1;
    dfs({r,c,d});

    return 0;
}  

정리

재귀함수를 이용하여 dfs를 구현하는 문제로 back tracking도 고려하여 푸는 문제였다. 다만 조건을 잘 읽고 종료하는 부분만 신경써주면 된다.