[C++] 14503 : 로봇 청소기

#include <iostream>
#include <utility> //pair
using namespace std;

int N, M; // 세로, 가로
int r, c, d; // 좌표, 방향 : 북0 동1 남2 서3
int map[51][51]; // 빈칸 : 0, 벽 1, 청소됨 2

int dx[4] = {-1, 0, 1, 0}; // 왼쪽 방향으로 회전
int dy[4] = {0, 1, 0, -1};

int cnt = 0; // 청소한 칸 수
bool back; // 뒤로 갔는지 여부 - false면 이동 불가, true면 이동

int main(int argc, char** argv){
  scanf("%d %d", &N, &M);
  scanf("%d %d %d", &r, &c, &d);

  for(int i=0; i<N; i++){
    for(int j=0; j<M; j++){
      scanf("%d", &map[i][j]); // map 입력받기
    }
  }

  while(1){
    if(map[r][c] == 0){ // 빈칸인 경우
      map[r][c] = 2; // 청소
      cnt++;
    }

    back = false; // 돌아가기 초기화

    for(int i=0; i<4; i++){ // 4방향 탐색
      d = (d+3) % 4; // 방향 전환
      int nx = r + dx[d];
      int ny = c + dy[d]; // 주변 좌표값 보기 위해 이동

      if(map[nx][ny] == 0){ // 청소하지 않은 공간 있을 때
        back = true; // 뒤로 돌아가기 성공
        r = nx;
        c = ny; // 이동
        break;
      }
    }

    if(!back){ // 네 방향 모두 청소 x
      int nd = (d+2) % 4;
      int nx = r + dx[nd];
      int ny = c + dy[nd]; // 방향 유지한 후 반대로 이동
      if(map[nx][ny] == 1){ // 뒤에 벽이 있을 경우
        break; // 종료
      }
      // 벽이 아닌 경우
      r = nx;
      c = ny; // 뒤로 이동
    }
  }

  printf("%d", cnt);

  return 0;
}

시뮬레이션 연습용 문제. 대략 4시간 쯤 걸렸다. 아직 익숙치 못한 슬픈 나...
인터넷도 많이 찾아보고 이런 문제를 접했을 때 어떤식으로의 접근법이 효율적인지를 공부하는 중이다.

• 방향은 함수를 통해서 구해도 되지만 나머지를 이용해 구하는 것이 훨씬 숫자를 이용하기 편하며 코드가 짧아 진다. ex) d = (d+3) % 4

• 굳이 check 배열을 만들지 않아도 된다. map에 2를 할당하는 것이 청소로 표시하면 훨씬 직관적이며 코드가 간단해진다.

• 모든 경우를 탐색하고 아닌 경우에 예외를 주려면 bool 변수를 사용하자. 모든 경우를 체크하는 것이 힘들고 만약 해당이 되는 경우 변수를 변화시켜 해당 경우에 해당하는 것이 아님을 확인하자.

• 좌표 변화시에는 nx, ny, nd와 같은 변수명을 사용한다.

이렇게 보면 코드도 참 간단하고 풀만한 것 같은데 아직 너무 문제를 보면 쫄아버린다. 자주 풀기~ 내일도 엄청 미뤄두었던 Dummy 문제를 풀어볼 생각이다. 시뮬레이션과 BFS/DFS 마스터가 되는 그 날까지.