[백준 31404번] 아리스, 청소합니다! (Easy) (C++)

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

분리집합으로 풀어야 하나 했는데 사이클을 어떻게 잡아야 할지 감이 안오고, 입력값들의 범위가 딱 봐도 구현이길래 구현만 하자라는 마인드로 풀었다.

먼지를 청소했을때는 ruleA를 따르고, 아닐때는 ruleB를 따르며 움직여야 한다. 3차원 배열을 이용해서 특정 위치 (r,c)에 들어가는 방향이 같은 경우 사이클이 생기므로 반복을 종료하면 된다.

또 중요한 건 먼지를 치웠을 때 사이클 확인을 위해 저장해놓은 3차원 배열을 모두 처음 상태로 초기화 시켜주어야 한다. ruleA와 ruleB가 다르기 때문에 같은 방향으로 들어가더라도 다음 이동이 달라질 수 있기 때문이다.

 

개인적으로 어려웠던 문제다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;

bool dust[65][65];
bool cache[65][65][4];
int ruleA[65][65];
int ruleB[65][65];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int H,W,r,c,d;

int clearCache(){
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			for(int k = 0; k < 4; k++){
				cache[i][j][k] = false;
			}
		}
	}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);

	string s;
	cin >> H >> W >> r >> c >> d;


	for(int i = 0; i < H; i++){
		cin >> s;
		for(int j = 0; j < W; j++){
			ruleA[i][j] = s[j]-'0';
		}
	}
	for(int i = 0; i < H; i++){
		cin >> s;
		for(int j = 0; j < W; j++){
			ruleB[i][j] = s[j] - '0';
		}
	}

	int cnt = 0, ans = 0;
	while(true){
		if(r<0 || r>=H || c<0 || c>=W) break;
		if(cache[r][c][d]) break;

		if(dust[r][c]) {
			cache[r][c][d] = true;
			d = (d+ruleB[r][c])%4;
		}
		else {
			clearCache();
			dust[r][c] = true;
			d = (d+ruleA[r][c])%4;
			ans = cnt;
		}
		r += dx[d], c += dy[d];
		cnt++;
	}
	cout << ans+1;
}