백준 14503번: 로봇 청소기, c++

 

 

처음 작성한 코드는 다음과 같다.

#include <iostream>
using namespace std;


int count = 0;
int N, M, r, c, d;
int v[51][51] = {-1,};


int clean(int r, int c) {   
    if( v[r][c]== 0) {//현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
        v[r][c] = 2; //청소 완료는 2, 벽 1, 청소 x는 0으로 표시
        count++;
    } 
    return count;
}


int main() {
    cin >> N >> M;
    cin >> r >> c >> d;  
    
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> v[i][j];
        }
    }  
    
    while(true) {
        clean(r, c);   
        
        //현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
        if( (v[r-1][c]!=0) && (v[r+1][c]!=0) && (v[r][c-1]!=0) && (v[r][c+1]!=0)) { 
            if(d==0) {
                if(v[r+1][c]==0 && r+1<N){
                    r += 1;
                    clean(r,c);
                }
                else
                    break;
            }
            else if (d==1){
                if(v[r][c-1]==0 && c-1>=0){
                    c -= 1;
                    clean(r,c);
                }
                else
                    break;            
            }
            else if (d==2){
                if(v[r-1][c]==0 && r-1>=0){
                    r -= 1;
                    clean(r,c);
                }
                else
                    break;            
            }
            else if (d==3){
                if(v[r][c+1]== 0 && c+1<M){
                    c += 1;
                    clean(r,c);
                }
                else
                    break;            
            }        
        }
        else { //현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
            if(d==0)
                d = 3;
            else
                d -= 1;
            
            if(d==0) {
                if(v[r-1][c]==0 && r-1>=0)
                    r -= 1;
            }
            else if(d==1) {
                if(v[r][c+1]==0 && c+1<M)
                    c += 1;
            } 
            else if(d==2) {
                if(v[r+1][c]==0 && r+1<N)
                    r += 1;
            }
            else if(d==3) {
                if(v[r][c-1]==0 && c-1>=0)
                    c -= 1;
            }
      
            clean(r, c);
        }        
    }
    
    cout << count;
    return 0;
}

 

 

 

결과로 "틀렸습니다"가 나왔다.

벽이 중간에 없는 간단한 맵은 잘 해결하는데, 중간에 벽이 있는 복잡한 맵은 잘 해결하지 못했다.

while문 안에 청소기 이동하는 코드에 뭔가 오류가 있는 듯 했다.

나는 하나하나 조건을 넣어 구현했는데, 구글링을 해보니 다들 큐와 bfs를 사용해 해결했다.

이런 탐색 문제(특히 로봇청소기 문제)는 역시 bfs를 사용하는게 빠르고 쉬운 것 같다.