문제 출처

1. 문제설명

  • N*M개의 방이 있다.
  • 각 방은 번호가 매겨져있다.
  • 불이 켜져있는 방으로만 들어갈 수 있고, 상하좌우 인접한 방으로 움직일 수 있다.
  • 불을 켤 수 있는 방의 최대 개수를 구하라.



2. 알고리즘 설계

  • 입력으로, 출발위치의 좌표(x,y), 도착위치의 좌표가 주어진다.
    • 이를 pair<int,int>를 가지는 2차원 배열에 저장한다.
    • 예를들어, 1 1 1 2라면, avail[1][1].push_back({1, 2})
  • (1,1)부터 시작해, BFS를 수행한다.
    • 벡터에서 연결된 점을 하나씩 꺼내면서 불을 켜지 않았다면,
      • 상,하,좌,우 인접한 칸을 큐에 넣고 체크한다.
    • 동시에, 현재 점에서 인접한 칸을 큐에 넣는다.
      • 각 방에서 인접한 칸으로 이동할 수 있기 때문!



3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};

vector<pair<int, int>> avail[101][101];
bool visited[101][101];
bool on[101][101];
int cnt = 0;
int n, m;
void bfs()
{
    queue<pair<int, int>> Q;
    Q.push({1, 1});
    visited[1][1] = true;
    on[1][1] = true;
    cnt++;
    
    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();
        for (auto &room : avail[cur.X][cur.Y])
        {
            if (!on[room.X][room.Y])
            { 
                on[room.X][room.Y] = true;
                cnt++;
                for (int dir = 0; dir < 4; dir++)
                {
                    int nx = room.X + dx[dir];
                    int ny = room.Y + dy[dir];
                    if (nx < 1 || ny < 1 || nx > n || ny > n)
                        continue;
                    if (visited[nx][ny])
                    { 
                        Q.push({room.X, room.Y});
                        visited[room.X][room.Y] = true;
                        break;
                    }
                }
            }
        }
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 1 || ny < 1 || nx > n || ny > n)
                continue;
            if (!on[nx][ny] || visited[nx][ny])
                continue;
            Q.push({nx, ny});
            visited[nx][ny] = true;
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        avail[x][y].push_back({a, b});
    }
    bfs();
    cout << cnt;

    return 0;
}