[백준 17267] 상남자

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

문제 카테고리

BFS

접근 방법

처음에는 벽 부수기 문제 처럼, 왼쪽으로 갈 수 있는 횟수, 오른쪽으로 갈 수 있는 횟수를 Node 정보로 저장하는 방법을 생각했지만 그렇게 되면...

(x, y, l, r) 각 숫자 모두 1000의 크기를 가지므로 평생 풀 수 없다.

따라서 다음과 같은 아이디어를 고안했다. 별로 안어렵다.

1. 한 번의 BFS를 하며 각 x,y에 도달하기 위한 L, R을 기록한다.
2. 문제의 조건에 만족하는 노드만 count한다.

독특하게 처리해야 하는 곳은 "위 아래로 노빠구" 하는 부분이다. 코드 보면 이해하기 쉽다.

도움을 준 문제들

레이저 통신: https://www.acmicpc.net/problem/6087

상남자보다 더 노빠꾸인 레이저 문제다. 여기서 한번에 queue에 다 집어넣는 테크닉을 써먹었다.

코드

vvi A;
int N, M, L, R;

bool in_board(int x, int y) {
    return 0 <= x && x < N && 0 <= y && y < M;
}

int go(int sx, int sy) {
    vvi RD(N, vi(M, -1));
    vvi LD(N, vi(M, -1));

    queue<pair<int, int>> q;
    RD[sx][sy] = 0;
    LD[sx][sy] = 0;
    q.push({sx, sy});

    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        int cr = RD[cx][cy];
        int cl = LD[cx][cy];

        int nx, ny;
        // 아래 노빠구.
        for (nx = cx + 1; nx < N; nx++) {
            if (A[nx][cy] == 1) break;
            if (RD[nx][cy] != -1) continue;
            RD[nx][cy] = cr;
            LD[nx][cy] = cl;
            q.push({nx, cy});
        }

        // 위 노빠꾸.
        for (nx = cx - 1; nx >= 0; nx--) {
            if (A[nx][cy] == 1) break;
            if (RD[nx][cy] != -1) continue;
            RD[nx][cy] = cr;
            LD[nx][cy] = cl;
            q.push({nx, cy});
        }

        // 왼쪽으로 한 칸.
        ny = cy - 1;
        if (in_board(cx, ny) && A[cx][ny] != 1 && RD[cx][ny] == -1) {
            RD[cx][ny] = cr;
            LD[cx][ny] = cl + 1;
            q.push({cx, ny});
        }

        // 오른쪽으로 한 칸.
        ny = cy + 1;
        if (in_board(cx, ny) && A[cx][ny] != 1 && RD[cx][ny] == -1) {
            RD[cx][ny] = cr + 1;
            LD[cx][ny] = cl;
            q.push({cx, ny});
        }
    }

    int ans = 0;
    RP(x, N) {
        RP(y, M) {
            if (RD[x][y] != -1 && RD[x][y] <= R && LD[x][y] <= L) {
                ans++;
            }
        }
    }
    return ans;
}