[C++] 백준 14503번: 로봇 청소기

🔗 문제

14503번: 로봇 청소기

14503번: 로봇 청소기

 

🖍 풀이

 

이 문제는 2차원 배열을 동서남북으로 이동하되 이동 방향 규칙에 유의해야 한다.

 

꼬박 하루나 붙잡은 문제다.

처음엔 후진을 2칸간다고 생각했기 때문이다……………………………………

두번째엔 후진을 했을 때 방향을 유지하지 않고 왼쪽으로 돌려서 2번 예제도 나오지 않았었다.

 

🔄 방향 잡기

문제를 읽어보면 현재 방향(d)을 북동남서순으로 표현하고 있다.

그렇다면 왼쪽으로 d에 따라 좌회전을 하면 서북동남, 후진을 하면 남서북동이다.

이걸 d 기준으로  각 회전을 수식으로 표현할 수 있다.

// 문제의 d 방향으로 좌표 생성
// 북동남서
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

 

좌회전 : d = (d+3)%4

d = (d+3)%4;
int x = r + dx[d];
int y = c + dy[d];

 

후진: back = (d+2)%4

int back = (d+2)%4;
int x = r + dx[back];
int y = c + dy[back];

 

---

🐙 문제 정리

현재 위치를 r, c 로, 방향을 d을 뜻한다.

1. map[r][c]가 0이면 청소한다.
2. map[r][c]에서 반시계 방향으로 전진했을 때 위치, (x, y)를 구한다.
   • map[x][y]가 0이면 청소한다.
   • map[x][y]가 0이 아니면 과정 2를 반복한다.
   • 모든 방향에 청소가 불가능하면 다음 과정 3을 진행한다.
3. map[r][c]에서 후진했을 때 위치 (x, y)를 구한다.
   • map[x][y] == 1이면 후진할 수 없다. 프로그램 정지!
   • 후진할 수 있다면 위치만 후진하고 방향은 유지한 채 과정 1로 돌아간다.

 

 

🗺 예제 2번 이해를 위한 이동 경로

 

 

 

후진할 땐 후진 방향으로 회전하는게 아니라, 이전 방향을 유지해야한다는 점과 후진을 할 시에는 이미 청소한 구역에도 방문 가능하다. 만약 후진해야할 때 이미 청소한 구역으로 가지 못한다면 정답이 20에서 계속 맴돈다. (경험담)

 

💾  소스

#include <iostream>

const int MAX = 50 + 1;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int N, M, answer = 0;
int map[MAX][MAX];
int r, c, d;

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=M)
        return false;
    return true;
}

void solve()
{
    bool flag;
    
    while(1)
    {
        flag = false;
        
        if(map[r][c] == 0)
        {
            map[r][c] = -1;
            ++answer;
        }
        
        for(int i=0; i<4; ++i)
        {
            d = (d+3)%4;
            
            int x = r + dx[d];
            int y = c + dy[d];
            
            if(!isValid(x, y) || map[x][y] != 0)
                continue;
        
            r = x;
            c = y;
            
            flag = true;
        
            break;
        }
        
        if(flag == false) // 후진해야해..
        {
            int dir = (d+2)%4;
            int x = r + dx[dir];
            int y = c + dy[dir];
            
            if(!isValid(x, y) || map[x][y] == 1) // 후진할 수 없다..
                break;
            
            r = x;
            c = y;
        }
            
    }
    return;
}

int main()
{
    std::cin >> N >> M;
    std::cin >> r >> c >> d;
    
    for(int i=0; i<N; ++i)
        for(int j=0; j<M; ++j)
            std::cin >> map[i][j];
    
    solve();
    
    std::cout << answer;
    
    return 0;