글 읽기 - 로봇청소기 테케 2번 청소를 다해버립니다..

apicad0307 2년 전 0

후... 12시간째 뭐가 틀린지 보고 있는데 어디서 틀렸는지를 못찾겠네요

정답은 58, 59번째를 청소안하는데 제 풀이에서는 58번째 59번째도 청소를 해버리네요...ㅠㅠㅠ

재귀로 구성하였는데 return;을 만나도 함수가 안끝나는 것 같아서요...

고수님들 도와주세요...ㅠㅠㅠ

벽은 숫자 2로 만들었습니다.

(문제의 정답.) 
0  0  0  0  0  0  0  0  0  0
 0 56 57 46 45 44 43 42 41  0
 0 55 48 47  0  0  0  0 40  0
 0 50 49  0  0 36 37 38 39  0
 0 51  0  0 35 34 31 30  0  0
 0 52 53 12 11 33 32 29 28  0
 0 54 14 13 10  9  0  0 27  0
 0 16 15  2  1  8  0  0 26  0
 0 17 18  3  4  7  0  0 25  0
 0 21 19 20  5  6 22 23 24  0
 0  0  0  0  0  0  0  0  0  0
    
(제 풀이의 답)
2  2  2  2  2  2  2  2  2 2
2 56 57 46 45 44 43 42 41 2 
2 55 48 47  2  2  2  2 40 2     
2 50 49  2  2 36 37 38 39 2   
2 51  2  2 35 34 31 30 58 2   
2 52 53 12 11 33 32 29 28 2 
2 54 14 13 10  9 59  2 27 2   
2 16 15  2  1  8  2  2 26 2      
2 17 18  3  4  7  2  2 25 2
2 21 19 20  5  6 22 23 24 2
2  2  2  2  2  2  2  2  2 2
    
    

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second
int n, m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int board1[51][51];
int board2[51][51];
bool vis[51][51];
int cnt = 0;

void robot(int x, int y, int d){
  if(!vis[x][y]){
    board2[x][y] = ++cnt;
    vis[x][y] = true;
  }
  for(int i=0; i<4; i++){
    int nd = (d-i+3)%4;
    int nx= x + dx[nd];
    int ny= y + dy[nd];
    if(board2[nx][ny]!=0 || vis[nx][ny]) continue;
    robot(nx, ny, nd);
  }
  int px = x + dx[(d+2)%4];
  int py = y + dy[(d+2)%4];
  if(board2[px][py] == 2) return;
  robot(px, py, d);
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  int r, c, d;
  cin>>r>>c>>d;
  int cnt1 = 0;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin>>board1[i][j];
      if(board1[i][j] == 0) cnt1++;
      board2[i][j] = board1[i][j];
      if(board1[i][j]==1) board2[i][j]=2;
    }
  }
  int cnt2 = 0;
  robot(r, c, d);
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      // if(board2[i][j]==0) cnt2++;
      cout<<board2[i][j]<<' ';
    }
    cout<<'\n';
  }
  return 0;
  // cout<< cnt1 - cnt2;
}

sjin0704 2년 전 2

코드를 올리고 질문하실 땐 남들이 보기 편하게 코드를 짜거나 주석을 달아주세요.

다른 부분은 문제가 없는 것 같지만 robot함수에 문제가 있어 보입니다.

1. 로봇은 왼쪽을 탐색하다 공간이 있으면 그 방향으로 이동합니다.

하지만 위 코드의 for문에서는 로봇이 이동한 후에도 계속 루프가 돌기 때문에 로봇의 경로가 여러 개가 존재하게 될 가능성이 있습니다.

로봇이 공간을 탐색했다면 루프가 종료되어야 합니다.

2. 로봇이 이동하는 것에 성공을 했다면 뒤로 이동하지 않습니다.

하지만 위 흐름에서는 로봇의 이동 여부와 관계없이 for문이 종료되면 로봇을 뒤로 후진시키는 코드가 실행됩니다.

로봇의 사방이 막혀있든 막혀있지 않던 뒤가 벽이 아니기만 한다면 후진이 되고 있다는 겁니다.

로봇이 이동에 성공했다면 사방이 막혀있지 않다는 의미이므로 함수가 종료되어야 합니다.

댓글을 작성하려면 로그인해야 합니다.