[백준/c++] BOJ 23747 - 와드

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

23747번: 와드

 

문제 설명

RxC 격자가 있다. 자신이 위치한 칸에서 위, 아래, 왼쪽, 오른쪽으로 인접한 칸만을 볼 수 있지만, 와드를 놓으면 와드가 놓인 칸이 속한 영역에 있는 모든 칸을 볼 수 있게 된다. 인접한 칸이 같은 문자라는 것은 두 칸이 같은 영역에 속해 있음을 의미한다. 여행 기록을 나타내는 200000 글자 이하의 문자열이 주어진다. U, D, L, R, W 중 하나도 이루어져 있으며, 각각 왼쪽, 아래쪽, 왼쪽, 오른쪽, 와드 설치를 의미한다.

R, C (1 <= R, C <= 1,000)

해결

여행 기록을 나타내는 문자열을 인덱스 0부터 돌며 현재 위치를 이동시킨다.

아래 코드에서 a, b는 현재 위치의 좌표를 나타내는데, U, D, L, R에 맞춰 움직여 주면 된다.

 

문자열을 돌면서 W가 나오면 BFS를 통해 와드를 설치했다.

 

문자열을 다 돌면 마지막 위치에서 상하좌우를 밝혀 줘야 한다.

코드

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

int n, m, a, b;
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
char board[1001][1001], visited[5001][5001];
string str;

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

void bfs(int i, int j) {
    char ch = board[i][j];
    queue<pair<int, int>> q;
    q.push({ i ,j });
    visited[i][j] = '.';

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
            visited[i][j] = '#';
        }
    }

    cin >> a >> b;
    cin >> str;
    a--, b--;

    for (int i = 0; i < str.length(); i++) {
        if (str[i] == 'L') b--;
        else if (str[i] == 'R') b++;
        else if (str[i] == 'U') a--;
        else if (str[i] == 'D') a++;
        else bfs(a, b);
    }

    visited[a][b] = '.';
    for (int dir = 0; dir < 4; dir++) {
        int nx = a + dx[dir], ny = b + dy[dir];
        visited[nx][ny] = '.';
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << visited[i][j];
        cout << "\n";
    }
}