baekjoon 31404:아리스, 청소합니다! (Easy)

baekjoon 31404 아리스, 청소합니다! (Easy)

31404번 아리스, 청소합니다! (Easy)

접근

규칙에 맞게 움직이기만 하면 되지만 나머지는 다 쉬워도 더이상 움직이는게 무의미 해지는 순간을 찾는 것이 조금 어려웠다.
처음에는 전체 칸 수 만큼 움직여도 제거할 수 있는 먼지가 없으면 그렇게 판단 하도록 했더니 틀렸었다.
생각해보니 실질적으로 중요한 것은 하나도 지운 먼지가 없는 사이클이 발생하면 되는 것이였는데 그 사이클이 같은 점을
여러번 지날 수 있기 때문에 처음 방식대로 하면 안되는 것이였다.
그래서 진짜 사이클을 찾기 위해 3차원 벡터를 생성하여 각 칸마다 어떠한 모양으로 지나갔었는지를 기록했다.

코드

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
void updateCor(array<int, 3>& p, vector<vector<int>>& map);
int main(){
  int h, w;
  cin >> h >> w;
  int r, c, d; cin >> r >> c >> d;
  vector<vector<int>> a(h, vector<int>(w));
  vector<vector<int>> b(h, vector<int>(w));
  vector<vector<bool>> dust(h, vector<bool>(w));
  vector<vector<vector<int>>> stack(h, vector<vector<int>>(w)); //사이클 기록
  for(int i = 0; i < h; i++){
    string s; cin >> s;
    for(int j = 0; j < w; j++){
      a[i][j] = s[j] - '0';
    }
  }
  for(int i = 0; i < h; i++){
    string s; cin >> s;
    for(int j = 0; j < w; j++){
      b[i][j] = s[j] - '0';
    }
  }
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      dust[i][j] = true;
    }
  }
  array<int, 3> p = {r, c, d};
  int move = 0;
  int endMove = 0;
  int clean = 0;
  while(true){
    if(dust[p[0]][p[1]]){
      dust[p[0]][p[1]] = false;
      clean++;
      updateCor(p, a);
      move++;
      endMove = move;
      stack = vector<vector<vector<int>>>(h, vector<vector<int>>(w)); //먼지 제거 한번 하는 순간 사이클 초기화
      if(p[0] < 0 || p[0] >= h || p[1] < 0 || p[1] >= w) break;
    }
    else{
      if(find(stack[p[0]][p[1]].begin(), stack[p[0]][p[1]].end(), p[2]) != stack[p[0]][p[1]].end()){
        break;  //있으면 사이클 발생 (먼지 제거 한번이라도 했으면 없었을 거임)
      }
      stack[p[0]][p[1]].push_back(p[2]);
      updateCor(p, b);
      move++;
      if(p[0] < 0 || p[0] >= h || p[1] < 0 || p[1] >= w) break;
    }
    
    
    
  }
  cout << endMove;

  return 0;
}
void updateCor(array<int, 3>& p, vector<vector<int>>& map){
  p[2] = (p[2] + map[p[0]][p[1]]) % 4;
  if(p[2] == 0){
    p[0]--;
  }
  else if(p[2] == 1){
    p[1]++;
  }
  else if(p[2] == 2){
    p[0]++;
  }
  else if(p[2] == 3){
    p[1]--;
  }
}

배운 점

슬슬 골3은 풀만해지는 것 같기도…?