[BOJ] 13901. 로봇

로봇

클릭시 이동합니다.

어떻게 풀까?

우선, 처음에 방향이 4개가 주어집니다.

그리고 4개의 방향에서 나아가지 못하면, 현재의 위치를 출력해야하죠!

따라서, 저는 4개의 방향을 살펴보면서 4개의 방향으로 가지 못하면 cont라는 bool 변수를 false로 만들어서 while문을 빠져나오게 했습니다!

한 번이라도 움직이면, 해당 방향으로 움직이기 때문에 계속 루프를 돌겠죠.

그리고, 움직인 방향에는 벽을 설치해서 다시 돌아올수 없게 했습니다.

또 중요하게 생각해볼 점은 

1. '만약 움직이면 계속 같은 방향으로 움직인다.' 라는 점과

2. '만약, 사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아간다.' 라는 점이겠죠.

1번 같은 경우는, 자신의 현재 방향을 변수로 가지고 있으면 쉽게 해결됩니다!

2번의 경우는 모듈라 연산을 이용하여 해결할 수 있습니다!

과정으로 나타내면 이런 과정이죠!

현재 방향이 왼쪽인데, 왼쪽을 보니 막혀있습니다. 다음에 설정된 방향을 봅니다.

(현재방향 = 현재방향 + 1)

오른쪽을 보니 오른쪽도 막혀있습니다! 처음으로 돌아가야합니다!

하지만, 현재 방향에 +1을 한다면.. 인덱스 초과 오류가 뜨겠죠. 이럴때 쓰는것이 모듈라 연산입니다!

현재 인덱스가 3이라고 하면, 

현재인덱스에 1을 더하면 4가 되죠!

그리고 배열이 총 4개이기 때문에, 4로 모듈라 연산을 해주면, 0이 됩니다!

따라서, 현재 방향 = (현재 방향 + 1) % 4를 해주는 것이죠.

이렇게 하면, 알아서 뺑뺑 잘 돕니다!

이제 위가 뚫렸기 때문에 위로 이동합니다.

사방이 막힌 경우에는 로봇이 나아가지 못하고 해당 배열을 뺑뺑 돌기만 할 것입니다.

따라서, for문을 이용하여 딱 4번만 돌게 하고, 그래도 이동을 못했으면 종료한다는 조건을 추가합시다.

코드

//https://www.acmicpc.net/problem/13901
//로봇
#pragma once
#include<cstdio>
 
bool map[1002][1002];
int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,-1,1 };
 
int main() {
    int r, c, k;
    scanf("%d %d\n", &r, &c);
    scanf("%d \n", &k);
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            map[i][j] = true;
        }
    }
        
    while (k--) {
        int tr, tc;
        scanf("%d %d\n", &tr, &tc);
        map[++tr][++tc] = false;
    }
    
    int sr, sc;
    scanf("%d %d\n", &sr, &sc);
 
    int d[4], cnt = 0;
    scanf("%d %d %d %d\n", &d[0], &d[1], &d[2], &d[3]);
 
    sr++; sc++;
 
    bool cont = true;
    while (cont) {
        int nnr, nnc;
        
        cont = false;
 
        for (int i = 0; i < 4; i++) {
            nnr = sr + dr[d[(cnt+i)%4]]; nnc = sc + dc[d[(cnt+ i)%4]];
 
            if (map[nnr][nnc]) {
                cnt = (cnt + i) % 4;
                map[sr][sc] = false;
                sr = nnr; sc = nnc;
                cont = true;
                break;
            }
        }
    }
 
    printf("%d %d\n", --sr, --sc);
    return 0;
}

여담

시간 복잡도는, 맵의 크기 O(MN) 이겠군요!