[백준] 21922 - 학부 연구생 민상

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

21922번: 학부 연구생 민상

 

간단한 문제였지만, 생길 수 있는 반례를 좀 오래 생각한 문제였다.

처음에 ans[n][m]이라는 배열을 생성해 에어컨 바람이 오는 자리를 체크해 답을 내려했지만,

ans[n][m]을 채우는 과정에서 만약 이미 채워진 공간에 진입했을 때,

1. 어차피 왔던 공간이므로 탐색을 끝낸다.
2. 다른 경우의 수가 있을 수 있으므로 계속 채워나간다.

 

1번의 경우에는 어떤 방향으로 왔는지 기록을 해놓지 않았기 때문에, 탐색을 끝낼 수 없다.

2번의 경우에는 다음과 같은 입력이 들어왔을 때 무한 루프에 빠질 수 있다.

1 3
1 9 1

 

따라서 어떤 방향으로 지나갔는지에 대한 요소도 추가로 필요하다.

ans[dir][n][m] = (n, m)에 dir로 에어컨이 도달했으면 1, 아니면 0

 

다음은 에어컨 바람이 물건을 만났을 때인데, 이 경우는 모든 경우의 수를 따져보면 된다.

현재 격자의 상태는 물건 1~4, 물건이 없는 경우 총 5가지이다.

격자 상태 5 가지 * 방향 상태 4가지 = 20가지의 경우의 수가 나오는데 이때 실수만 안 하면 될 것 같다.

 

#include <iostream>
using namespace std;

int n, m, map[2000][2000], ans[4][2000][2000];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int changeDir(int now, int dir) {
    if (now == 1) {
        if (dir == 0 || dir == 2) {
            return 2 - dir;
        } else {
            return dir;
        }
    }
    if (now == 2) {
        if (dir == 1) {
            return 3;
        } else if (dir == 0 || dir == 2) {
            return dir;
        } else {
            return 1;
        }
    }
    if (now == 3) {
        if (dir == 0) {
            return 3;
        } else if (dir == 1) {
            return 2;
        } else if (dir == 2) {
            return 1;
        }
        return 0;
    }
    if (now == 4) {
        if (dir == 0) {
            return 1;
        } else if (dir == 1) {
            return 0;
        } else if (dir == 2) {
            return 3;
        }
        return 2;
    }
    return dir;
}

void go(int x, int y, int dir) {
    if (!(x >= 0 && x < n && y >= 0 && y < m)) {
        return;
    }
    if (ans[dir][x][y]) {
        return;
    }
    ans[dir][x][y] = 1;

    int nd = changeDir(map[x][y], dir);
    // cout << x << ' ' << y << ' ' << dir << '\n';
    go(x + dx[nd], y + dy[nd], nd);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 9) {
                for (int k = 0; k < 4; k++) {
                    go(i, j, k);
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ans[0][i][j] || ans[1][i][j] || ans[2][i][j] || ans[3][i][j]) {
                res++;
            }
        }
    }
    cout << res;
}

 

changeDir() 메서드를 비트 연산자로 리팩터링 하려고 했지만 오히려 시간을 더 쓰는 것 같아서 그만뒀다.