[BaekJoon/백준] 13901번 로봇

 

DFS로 풀이했다.

 

 

처음 제출했을 땐 틀렸는데, 주의할 점은

'로봇은 벽이나 방문한 지역, 장애물을 만나기 전까진 계속 같은 방향으로 이동한다' 는 것이다.

 

주석을 상세히 달아놓았으니, 이해에 도움이 될 것 같다!!

#include <iostream>

using namespace std;

int R, C, K;

int START_X, START_Y;

int MAP[1000][1000]; // 0은 미 방문, 1은 방문, 2는 장애물

int DIR[4]; // 값 => 1 : 상, 2 : 하, 3 : 좌, 4 : 우

// 상 하 좌 우 인덱스 : 0 1 2 3
int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, -1 ,1};

void dfs(int x, int y, int dir) {
    
    MAP[x][y] = 1; // 방문
    
    int i;
    for(i = dir; i < dir + 4; i++) {
        
        int tx = x + mx[DIR[i % 4] - 1]; // => ex) DIR에서 가져온 값은 상 : 1 인데, mx에서 상은 0인덱스에 들어있으므로 -1을 해주어야 함.
        int ty = y + my[DIR[i % 4] - 1];
        
        if(tx < 0 || ty < 0 || tx >= R || ty >= C)
            continue;
        
        if(MAP[tx][ty] == 0) // 방문할 수 있음
            return dfs(tx, ty, i); // 가장 빠르게 찾은 한 쪽만 갈 것이므로, return으로 처리하면 됨.
            // 맨 처음엔 i + 1로 했다가 틀렸었다.
    }
    
    if(i == dir + 4) { // 네 방향 다 못감
        
        cout << x << " " << y << "\n";
    }
    
    
}

int main() {
    
    int Br, Bc;
    
    cin >> R >> C >> K;
    
    for(int i = 0; i < K; i++) {
        
        cin >> Br >> Bc;
        
        MAP[Br][Bc] = 2; // 장애물
    }
    
    cin >> START_X >> START_Y;
    
    for(int i = 0; i < 4; i++)
        cin >> DIR[i];
    
    dfs(START_X, START_Y, 0);
}

다른분들의 풀이도 찾아보았는데, 나와 비슷하다.

 

 

소요 시간 : 20분