[백준/c++] BOJ 28471 - W키가 빠진 성원이

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

28471번: W키가 빠진 성원이

 

문제 설명

q, w, e, a, d, z, x, c 키를 이용해 8방향으로 캐릭터를 움직일 수 있다. 성원이는 w키가 빠져 7 방향으로 캐릭터를 움직일 수 있다.

NxN 게임판 위에서 목적지에 도달한다. 빈 공간이 ".", 이동할 수 없는 공간이 "#", 목적지가 "F"로 주어진다. 목적지는 항상 한 개 존재한다. 목적지에 도달할 수 있도록 하는 시작 지점의 개수를 구한다.

N (1 <= N <= 2000)

 

Q: 왼쪽 위 대각선으로 1칸 이동

W: 위쪽으로 1칸 이동

E: 오른쪽 위 대각선으로 1칸 이동

A: 왼쪽으로 1칸 이동

D: 오른쪽으로 1칸 이동

Z: 오른쪽 아래 대각선으로 1칸 이동

X: 아래쪽으로 1칸 이동

C: 왼쪽 아래 대각선으로 1칸 이동

해결

처음엔 보드 위의 모든 지점을 방문하여 목적지에 도달할 수 있는지 확인하는 브루트포스 식으로 접근하였다. 하지만 당연히 시간초과가 났다.

시작 지점 -> 목적지 가 아닌, 목적지 -> 시작 지점으로 찾아가는 게 더 효율적일 거라는 생각이 들었다.

목적지로부터 시작하여 방문할 수 있는 모든 지점이 시작 지점이 되는 것이다.

 

단, w키는 사용할 수 없다. 시작 지점 -> 목적지로 갈 때 w키는 위쪽으로 1칸 이동을 수행한다.

하지만 우리는 목적지 -> 시작 지점 방향으로 갈 것이므로 아래쪽 1칸 이동을 수행할 수 없다.

 

방문할 수 있는 지점을 만나면 ans를 증가시켜 주는 형태로 bfs를 진행하였다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, ans = 0;
char board[2001][2001];
int visited[2001][2001];
pair<int, int> start;
int dx[7] = { -1, -1, -1, 0, 0, 1, 1 }, dy[7] = { -1, 0, 1, -1, 1, 1, -1};

int range_over(int nx, int ny) {
    return nx < 0 || ny < 0 || nx >= n || ny >= n;
}

void bfs() {
    queue<pair<int, int>> q;
    q.push(start);
    visited[start.x][start.y] = 1;

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 7; dir++) {
            int nx = cur.x + dx[dir], ny = cur.y + dy[dir];
            if (range_over(nx, ny) || visited[nx][ny] || board[nx][ny] == '#') continue;
            visited[nx][ny] = 1;
            ans++;
            q.push({ nx, ny });
        }
    }
    cout << ans;
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'F') start = make_pair(i, j);
        }
    }

    bfs();
}