[백준/Baekjoon] 14503 로봇 청소기 C++ :: DFS & Graph & Implementation

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

14503번: 로봇 청소기

---

1. Logic

우와 구현은 역시 까다롭다. 문제를 보자마자 최단거리 알고리즘을 사용해야 할 것같아서 BFS를 사용하려고 했지만 문제와 맞지 않아 DFS가 더 적절하다고 판단했다. 이유는 계속 탐색이 아니라 한번 시작해서 한번 실패하면 바로 종료되기 때문에? 그리고 방향을 유지해야하기 때문에!

 

로직은 문제에 있는 그대로 실수하지 않고 구현하면 된다.

 

까다로운점은 방향을 유지해야 한다는 점이다. 

방향을 유지시키는 코드는 아래 코드에서 주석이랑 함께 보면 이해갈것이다.

---

2. Code

#include <iostream>

using namespace std;

int n, m;

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

int input[51][51];
bool vis[51][51];

int ans = 1;

void dfs(int x, int y, int d) {
    for(int i = 0; i < 4; i++) {
    	//90도 회전시키기 위해
        int nd = (d + 3 - i) % 4;
        int nx = x + dx[nd];
        int ny = y + dy[nd];
        
        if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
        if(input[ny][nx] == 1) continue;
        if(vis[ny][nx]) continue;
        
        vis[ny][nx] = true;
        ans++;
        dfs(nx, ny, nd);
    }
    
    //방향을 유지시키면서 뒤로 움직이기 위해
    int nd = d > 1 ? d - 2 : d + 2;
    int nx = x + dx[nd];
    int ny = y + dy[nd];
    
    if(nx >= 0 && nx < m && ny >= 0 && ny < n) {
        if(input[ny][nx] == 0) {
            dfs(nx, ny, d);
        }
        else {
        	//뒤에가 벽이면 종료
            cout << ans;
            exit(0);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int ry, rx, rd;
    
    cin >> n >> m;
    cin >> ry >> rx >> rd;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> input[i][j];
            vis[i][j] = false;
        }
    }
    
    vis[ry][rx] = true;
    
    dfs(rx, ry, rd);
}

---

3. Feedback

구현은 역시 많이 풀어봐야하는 것 같다. 문제에 조건이 다 나와있어서 실수만 안하면 되지만 진짜 힘든 것 같다ㅋㅋㅋㅋ

열심히 풀어야지~

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90