[백준] 31404, 31399 - 아리스, 청소합니다!

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

 

31399번: 아리스, 청소합니다! (Hard)

 

원래 Easy 버전을 먼저 풀고 시간을 어떻게 줄이면 좋을까 다른 코드를 둘러보다가 Hard 풀이를 발견해 버렸습니다.

풀이가 신기해서 공부해서 다시 풀어봤습니다.

원본 코드는 맨 아래에 있습니다.

 

 

    cin >> n >> m;

    int x, y, d;
    cin >> x >> y >> d;

    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];

 

입력을 받아줍니다.

a, b는 string 배열입니다.

 

 

    for(int i = 0; i < 1024; i++) {
        for(int j = 0; j < 1024; j++) {
            for(int k = 0; k < 4; k++) {
                dist[i][j][k] = 1;
                
                int nd = (k + (b[i][j] - '0')) % 4;
                int nx = i + dx[nd];
                int ny = j + dy[nd];
                
                if(check(nx, ny)) {
                    nxt[i][j][k] = {nx, ny, nd};
                } else nxt[i][j][k] = {-1,-1, 0};
            }
        }
    }

 

 

청소한 곳을 들렀을 때 다음 도착 위치와 방향을 b값을 사용해 전처리해 줍니다.

주어진 격자를 넘어가면 -1로 처리해 줍니다.

 

dist는 1로 초기화해 줍니다.

 

nxt값과 dist값은 뒤에서 경로 압축을 하며 계속 바뀌게 됩니다

 

 

 

    ll ans = 0;
    int val = 0;
    stack<asdf> st;
    while(check(x, y)) {
        ll moved = 0;
        val++;
        
        while(check(x, y) && visited[x][y]) {
            if(cnt[x][y][d] == val) {
                x = -1;
                break;
            }

            cnt[x][y][d] = val;
            st.push({x, y, d});
            moved += dist[x][y][d];

            asdf next = nxt[x][y][d];
            x = next.x;
            y = next.y;
            d = next.d;
        }

 

위치가 격자 밖으로 나가는지 검사를 하고, 이미 청소한 곳이라면 반복문을 진행합니다.

 

 

cnt 배열, val 값은 현재 경로를 체크하는 데 사용합니다

 

두 번째 while 문 전에 val 값을 증가시켜 주기 때문에

 

cnt[x][y][d] == val 이라는 것은 현재 경로가 한 바퀴 돌면서 아무 곳도 청소하지 못하고 시작 자리, 방향으로 돌아왔다는 뜻이 됩니다.

이 경우 x값을 -1로 바꿔주며 반복문을 빠져나옵니다.

 

그렇지 않다면, cnt배열을 갱신해 주고 이동한 거리를 더해줍니다.

 

 

경로 압축을 위해 스택에 위치와 방향도 넣어줍니다.

 

 

        if(check(x, y) && !visited[x][y]) {
            while(!st.empty()) {
                asdf now = st.top();
                st.pop();
                asdf next = nxt[now.x][now.y][now.d];
                dist[now.x][now.y][now.d] += dist[next.x][next.y][next.d];
                nxt[now.x][now.y][now.d] = nxt[next.x][next.y][next.d];
            }
            ans += moved;
            int nd = (d + (a[x][y] - '0')) % 4;
            visited[x][y] = true;
            x += dx[nd];
            y += dy[nd];
            d = nd;
            ans++;
        }

 

격자 밖으로 나가거나, 청소되지 않은 곳에 도착하게 됩니다.

 

스택에 값이 있다면 청소된 곳을 돌아다니다 현재 위치에 도착했다는 것이므로

스택의 값을 꺼내주면서  nxt 값을 전부 현재 위치, 방향값으로 바꿔주고 nxt까지의 거리롤 더해서 경로 압축을 해줍니다.

 

a 값을 사용해서 한 칸 이동해 줍니다.

 

정답에 위의 청소된 곳을 돌아다닌 거리를 더해주고 a 값을 이용해 한 칸 더 이동하므로 +1 해줍니다.

 

위 과정을 반복해 줍니다

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

int n, m;

struct asdf {
    int x, y, d;
};

asdf nxt[1024][1024][4];
int dist[1024][1024][4];
int cnt[1024][1024][4];
bool visited[1024][1024];
string a[1024], b[1024];

bool check(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

int main() {
    fastio;
    cin >> n >> m;

    int x, y, d;
    cin >> x >> y >> d;

    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];

    for(int i = 0; i < 1024; i++) {
        for(int j = 0; j < 1024; j++) {
            for(int k = 0; k < 4; k++) {
                dist[i][j][k] = 1;
                int nd = (k + (b[i][j] - '0')) % 4;
                int nx = i + dx[nd];
                int ny = j + dy[nd];
                if(check(nx, ny)) {
                    nxt[i][j][k] = {nx, ny, nd};
                } else nxt[i][j][k] = {-1,-1, 0};
            }
        }
    }

    ll ans = 0;
    int val = 0;
    stack<asdf> st;
    while(check(x, y)) {
        ll moved = 0;
        val++;
       
        while(check(x, y) && visited[x][y]) {
            if(cnt[x][y][d] == val) {
                x = -1;
                break;
            }

            cnt[x][y][d] = val;
            st.push({x, y, d});
            moved += dist[x][y][d];

            asdf next = nxt[x][y][d];
            x = next.x;
            y = next.y;
            d = next.d;
        }

        if(check(x, y) && !visited[x][y]) {
            while(!st.empty()) {
                asdf now = st.top();
                st.pop();
                asdf next = nxt[now.x][now.y][now.d];
                dist[now.x][now.y][now.d] += dist[next.x][next.y][next.d];
                nxt[now.x][now.y][now.d] = nxt[next.x][next.y][next.d];
            }
            ans += moved;
            int nd = (d + (a[x][y] - '0')) % 4;
            visited[x][y] = true;
            x += dx[nd];
            y += dy[nd];
            d = nd;
            ans++;
        }
    }

    cout << ans << '\n';

    return 0;
}