11967번: 불켜기

1967번: 불켜기

사용 언어: C++

 

문제

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2 ≤ N ≤ 100)과, M(1 ≤ M ≤ 20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

 

풀이

좌표가 (1,1) -> (1,2)가 주어지면 이것을 효과적으로 표현하기 위해 인접 리스트는 아니지만 비슷한 벡터를 사용하고 추가적으로 (1,1)이나 (1,1)에서 갈 수 있는 좌표인 (1,2)를 갈 수 있는지, 갈 수 있으면 큐에 넣는 코드가 필요하다.

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

int board[102][102];
bool vis[102][102];
//인접 리스트와 비슷한 연결 형태로 표현
vector<pair<int,int>> adj[102][102];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int N, M, ans;
bool OOB(int a, int b){
    return a<1 || a>N || b<1 || b>N;
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    while(M--){
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        adj[x][y].push_back({a,b});
    }
    queue<pair<int, int>> Q;
    board[1][1] = vis[1][1] = 1;
    Q.push({1,1});
    while(!Q.empty()){
        auto cur = Q.front(); Q.pop();
        for(auto nxt : adj[cur.X][cur.Y]){
            if(vis[nxt.X][nxt.Y]) continue;
            //(1,1) 혹은 좌표에서 이동이 가능한지
            for(int dir=0; dir<4; dir++){
                int nx = nxt.X + dx[dir];
                int ny = nxt.Y + dy[dir];
                if(OOB(nx,ny)) continue;
                if(vis[nx][ny]){
                    vis[nxt.X][nxt.Y] = 1;
                    //방문 가능한 곳만 큐에 넣기
                    Q.push({nxt.X, nxt.Y});
                }
                board[nxt.X][nxt.Y] = 1;
            }
        }
        for(int dir=0; dir<4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(OOB(nx,ny) || vis[nx][ny] || board[nx][ny] == 0) continue;
            vis[nx][ny] = 1;
            Q.push({nx,ny});
        }
    }
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            ans += board[i][j];
    cout << ans << '\n';

    return 0;
}