11967번 불켜기

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

# 복습 # 추천 # bfs # 필수 # 코딩 # 코테 # 구현 # 생각

처음에는 단순히 현재 위치(x, y)에서 킬 수 있는 방을 모두 키고, 모두 방문하는 식으로 구현하였으나, 틀렸다.

왜냐하면, 불을 켜도 방문할 수 없는 방이 있기 때문이다.(상, 하, 좌, 우로만 이동)

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 102
 
int n, m;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[Max][Max], room[Max][Max], isMove[Max][Max];
vector<pair<int, int> > v[Max][Max];
 
int bfs()
{
    int ret = 0;
 
    queue<pair<int, int> > q;
    q.push({ 1, 1 });
    visit[1][1] = room[1][1] = isMove[1][1] = true; // (1, 1) 방문 처리
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int x = q.front().first;
            int y = q.front().second;
 
            q.pop();
 
            // 현재 방(x, y)에서 상, 하, 좌, 우로 이동할 수 칸이면 '일단은' 표시.
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                // 범위를 벗어나거나 이미 방문한 곳이라면 무시
                if (nx < 1 || nx > n || ny < 1 || ny > n ) {
                    continue;
                }
 
                isMove[nx][ny] = true;
            }
 
            // 현재 방(x, y)에서 불을 킬 수 있는 방을 모두 킨다.
            for (auto p : v[x][y]) {
                if (!room[p.first][p.second]) {
                    room[p.first][p.second] = true; // 불을 킨 위치 표시
 
                    // 현재 위치(x, y)에서 불을 켰는데,
                    // 그 불을 킨 위치(p.first, p.second)가 
                    // 이전부터 지금까지 온 위치(x, y)들에서 인접하게 방문할 수 있는 곳이라면
                    // q에 넣는다.
                    if (isMove[p.first][p.second]) {
                        q.push({ p.first, p.second });
                    }
                }
            }
 
            // 현재 방(x, y)에서 상, 하, 좌, 우 인접한 방들 중 불을 켠 방으로만 이동할 수 있다.
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
 
                // 범위를 벗어나거나 이미 방문한 곳이라면 무시
                if (nx < 1 || nx > n || ny < 1 || ny > n || visit[nx][ny]) {
                    continue;
                }
 
                // 불을 킨 방으로만 이동 가능
                if (room[nx][ny]) {
                    visit[nx][ny] = true; // 방문 표시
                    q.push({ nx, ny });
                }
            }
        }
    }
 
    // 불을 킨 방의 개수를 센다.
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (room[i][j]) {
                ++ret;
            }
        }
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
    scanf("%d %d", &n, &m);
 
    int x, y, a, b;
 
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d %d", &x, &y, &a, &b);
        v[x][y].push_back({ a, b });
    }
 
    printf("%d\n", bfs());
 
    return 0;
}