백준 11975 Build Gates (USACO January 2016 Silver 3번)

문제 링크: https://www.acmicpc.net/problem/11975

11975번: Build Gates

BFS

방향 char를 하나 받을때마다 두칸씩 해당 방향으로 움직이면서 fence를 설치함. 다 설치하고 나서, fence가 없는곳에서 bfs를 실행시키고, 실행 횟수에서 1을 빼면 답임.

#include <bits/stdc++.h>
using namespace std;
 
int n, a[4001][4001], dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1};
queue<pair<int, int>> q;
 
void bfs(int y, int x) {
    a[y][x] = 1;
    q.push({y, x});
 
    while(!q.empty()) {
        int cy = q.front().first, cx = q.front().second;
        q.pop();
        for(int d = 0; d < 4; d++) {
            int ny = cy + dy[d], nx = cx + dx[d];
            if(ny >= 0 && nx >= 0 && ny <= 4000 && nx <= 4000 && a[ny][nx] == 0) {
                a[ny][nx] = 1;
                q.push({ny, nx});
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int y = 2000, x = 2000;
    a[y][x] = 1;
 
    cin >> n;
    while(n--) {
        char d;
        cin >> d;
 
        int yy, xx;
        for(int i = 0; i < 2; i++) {
            if(d == 'N')
                yy = y + dy[0], xx = x + dx[0];
            if(d == 'S')
                yy = y + dy[1], xx = x + dx[1];
            if(d == 'W')
                yy = y + dy[2], xx = x + dx[2];
            if(d == 'E')
                yy = y + dy[3], xx = x + dx[3];
 
            a[yy][xx] = 1;
            y = yy;
            x = xx;
        }
    }
 
    int ans = -1;
    for(int i = 0; i <= 4000; i++) for(int j = 0; j <= 4000; j++) {
        if(a[i][j] == 0) {
            bfs(i, j);
            ans++;
        }
    }
 
    cout << ans << '\n';
    return 0;
}