[백준] 12793 - 블록 게임

와...벽에 튕기는 경우가 한방향으로만 한바퀴 돈다고 계속 생각해서 계속 틀렸다...

이래서 사람이 멍청하면 몸이 고생한다고 하나보다...

리뷰를 하면서도 얼탱이가 없넼ㅋㅋㅋㅋ

일단 이 문제는 좌표계가 문제 예시1번 처럼 생각하면 백타 틀린다

즉, 입력으로 주어지는 좌표계를 그대로 사용해야한다

그 이유는 K가 0.5의 배수이기 때문에 좌표계 자체를 2배 늘려준다고 생각하면 편하다

1. map을 그대로 입력받는다

2. 주어진 map에서 블록들을 각각 그룹으로 만들어 주기 위해 BFS를 사용하여 번호를 붙인다

3. 이렇게 만들어진 visit을 map으로 사용해야한다 시작위치를 y = 2*N, x = 2*K로 잡고 시작

(나는 주로 N을 y로, M을 x로 두고 사용하기 때문에 입력을 거꾸로 받음)

4. 끝까지 갔다가 돌아오면서 위, 아래, 현재 칸에 블록이 있는지 확인하면서 돌아온다

  - 블록을 부서트릴 땐 부서트렸는지 check해주는 배열을 만들어서 반드시 중복을 피하도록 한다

  - 왜 visit에서 현재 뿐만아니라 위, 아래칸도 검사하는지는 5분만 고민해보면 알 것이다

#include <iostream>
#include <cmath>
#define MAXSIZE 203
using namespace std;
 
struct QUEUE {
    int x, y;
}q[MAXSIZE*MAXSIZE];
 
char map[MAXSIZE][MAXSIZE];
int visit[MAXSIZE][MAXSIZE], broken[MAXSIZE*MAXSIZE];
const int dx[] = { 0, 0, -1, 1, 0 };
const int dy[] = { -1, 1, 0, 0 , 0};
const int dx_[] = { -1, 1, 1, -1 };
const int dy_[] = { -1, -1, 1, 1 };
int N, M, dab;
float K;
 
void bfs(int x, int y, int cnt) {
    int st, ed, ix, iy, nx, ny;
    st = ed = -1;
    q[++st].x = x; q[st].y = y; visit[y][x] = cnt;
    while (st != ed) {
        ix = q[++ed].x; iy = q[ed].y;
        for (int i = 0; i < 4; i++) {
            nx = ix + dx[i]; ny = iy + dy[i];
            if (nx < 0 || ny < 0 || ny >= 2 * N + 1 || nx >= 2 * M + 1 || visit[ny][nx]) continue;
            if (map[ny][nx] != '.' && map[ny][nx] != 'B') continue;
            q[++st].x = nx; q[st].y = ny; visit[ny][nx] = cnt;
        }
    }
}
 
void dfs(int d, int x, int y, int dir) {
    if (d && y == 2 * N + 1) {
        return;
    }
    int nx = x + dx_[dir], ny = y + dy_[dir];
 
    if (nx < 0) {
        if (dir == 0) dir = 1;
        else dir = 2;
    }
    else if (ny < 0) {
        if (dir == 1) dir = 2;
        else dir = 3;
    }
    else if (nx > 2 * M) {
        if (dir == 2) dir = 3;
        else dir = 0;
    }
 
    nx = x + dx_[dir]; ny = y + dy_[dir];
 
    dfs(d + 1, nx, ny, dir);
 
    if (visit[y - 1][x]) {
        if (broken[visit[y - 1][x]] == 0) {
            dab++; broken[visit[y - 1][x]] = 1;
        }
    }
    if (visit[y + 1][x]) {
        if (broken[visit[y + 1][x]] == 0) {
            dab++; broken[visit[y + 1][x]] = 1;
        }
    }
    if (visit[y][x]) {
        if (broken[visit[y][x]] == 0) {
            dab++; broken[visit[y][x]] = 1;
        }
    }
}
 
int main(void) {
    int blockcnt = 0;
    cin >> M >> N >> K;
 
    for (int i = 0; i < 2 * N + 1; i++)
        cin >> map[i];
 
    for (int i = 0; i < 2 * N + 1; i++)
        for (int j = 0; j < 2 * M + 1; j++)
            if (!visit[i][j] && map[i][j] == 'B') {
                blockcnt++;
                bfs(j, i, blockcnt);
            }
 
    K = floor(2 * K);
    int ix = K, iy = 2 * N;
    dfs(0, ix, iy, 0);
    cout << dab << endl;
 
    return 0;
}