solved.ac Grand Arena div 2 (C번)

• 링크

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

• 내가 푼 방법

이 문제는 실제 대회 시간 내에 풀지 못한 문제이다.

진짜 엄청나게 맞왜틀을 한 문제인데, 초기에 한 가정은 이렇다.

일단, 지점에 방문하자말자, 먼지를 청소하고 그에 따라 시계 방향으로 얼마나 회전할지 결정되기 때문에, 해당 지점에 방문했을 때, 먼지를 청소하는 경우와 그렇지 않은 경우를 생각해야 했다.

또한, 들어오는 방향에 따라 방향이 달라져, 이도 적용하기 위해서 4차원 vector 를 만들었다.

마지막으로 먼지를 청소하기 위해 최소한으로 움직여야 하니까, 얼마나 오랫동안 먼지를 청소하지 못했는지도 zeroTime 으로 기록해주고, moveTime - zeroTime 을 통해 최소 움직임 횟수를 구했다.

하지만, 맞지 않았다. 왜 아니지... 라고 맞왜틀 하였다.

대회가 끝나고 질문 게시판을 보니 다음과 같은 반례가 존재했다.

1 5
0 2 1
22222
00000

answer : 11

머리를 얻어맞은 것 같았다. 동일한 방향으로 들어오더라도, 여러번 방문할 수 있다. 꼭 해당 방향으로 방문해야지 다음 먼지가 쌓인 지점으로 가기 위해서는 말이다.

아마, 출제자 분은 테케 짜느라 엄청 애먹으셨을 것이다.

쨌든, 그래서 방문 배열의 값을 bool 값이 아닌 int 값으로 하고, 해당 지점을 최대 h * w (전체 그리드 개수) 번 방문하게끔 바꿔주었더니 바로 맞았다.

• 시간복잡도

O(h ^ 2 * w ^ 2 * 2 * 4)

최대 경우 1억 3천만 번의 연산을 진행해야한다.

시간 복잡도가 상당히 높다. 하지만, naive 하게 계산한 시간 복잡도이므로, 아마 실제로 프로그램이 돌아가면서 한 지점을 모두 h * w 만큼 방문하는 경우는 존재하지 않는 것 같다.

그래서 이론상(?) 최대 시간 복잡도가 저럼에도 불구하고 통과할 수 있었다.

• Code

#include <algorithm>
#include <sstream>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <string.h>
#include <cstdio>
#include <cmath> 
#include <set>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<vector<int> > vii;
typedef vector<vector<ll> > vll;
typedef vector<vector<vector<int> > > viii;
typedef vector<vector<vector<vector<int> > > > viiii;
typedef vector<vector<vector<ll> > > vlll;
typedef vector<vector<vector<vector<ll> > > > vllll;
typedef vector<bool> vb;
typedef vector<vector<bool> > vbb;
typedef vector<vector<vector<bool> > > vbbb;
typedef vector<vector<vector<vector<bool> > > > vbbbb;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;

int h;
int w;

void printArray(vii& array) {
  for (int i = 0; i < array.size(); i++) {
    for (int j = 0; j < array[i].size(); j++) {
      cout << array[i][j] << "";
    }
    cout << "\n";
  }
}

int rotateDir(int originalDir, int rotate) {
  return (originalDir + rotate) % 4;
}

bool isOutOfRange(int y, int x) {
  return y < 0 || y >= h || x < 0 || x >= w;
}

int main(void){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  freopen("c.input.txt", "r", stdin);

  vi dx = {0, 1, 0, -1};
  vi dy = {-1, 0, 1, 0};
  cin >> h >> w;
  int y, x, dir; cin >> y >> x >> dir;
  
  vii A(h, vi(w, 0));
  vii B(h, vi(w, 0));

  for (int i = 0; i < h; i++) {
    string s; cin >> s;
    for (int j = 0; j < w; j++) {
      A[i][j] = s.at(j) - '0';
    }
  }

  for (int i = 0; i < h; i++) {
    string s; cin >> s;
    for (int j = 0; j < w; j++) {
      B[i][j] = s.at(j) - '0';
    }
  }
  
  int moveTime = 0;
  int zeroTime = 0;
  viiii visited(2, viii(4, vii(h, vi(w, 0))));
  vii isA(h, vi(w, 1));
  
  while (true) {
    if (isOutOfRange(y, x) || h * w <= visited[isA[y][x]][dir][y][x]) {
      break;
    }
    
    visited[isA[y][x]][dir][y][x]++;
    moveTime++;

    if (isA[y][x]) {
      zeroTime = 0;
      dir = rotateDir(dir, A[y][x]);
      isA[y][x] = 0;
    } else {
      zeroTime++;
      dir = rotateDir(dir, B[y][x]);
    }

    y += dy[dir];
    x += dx[dir];
  }
  
  cout << (moveTime - zeroTime) << "\n";
  return 0;
}