Baekjoon 11967번 불켜기

문제

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

걸린 시간

01 : 18 : 38

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int n, m, x, y, a, b;
int room[101][101];
int hopCount[101][101];
vector<pair<int, int>> light[101][101];

int bfs(){
    queue<pair<int, int>> q; // loc, hop count
    q.push(make_pair(1, 1));
    int cnt = 1;
    while(!q.empty()){
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
        if(hopCount[cx][cy] == 0) continue;
        if(room[cx][cy] == 0){ // 방 불이 꺼져있다면
            q.push(make_pair(cx, cy));
            hopCount[cx][cy]--;
            continue;
        }
        else{
            hopCount[cx][cy] = 0;
            // 다른 방의 불 켜기
            for(int i = 0; i < light[cx][cy].size(); i++){
                int ox = light[cx][cy][i].first;
                int oy = light[cx][cy][i].second;
                if(room[ox][oy] == 0){
                    cnt++;
                    room[ox][oy] = 1;
                }
            }
            // 인접한 방으로 이동
            for(int i = 0; i < 4; i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if(1 <= nx && nx <= n && 1 <= ny && ny <= n){
                    if(hopCount[nx][ny] == 2*n){
                        q.push(make_pair(nx, ny));
                        hopCount[nx][ny]--;
                    }
                }
            }
        }
    }
    return cnt;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> x >> y >> a >> b;
        light[x][y].push_back(make_pair(a, b));
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            hopCount[i][j] = 2*n;
    memset(room, 0, sizeof(room));
    room[1][1] = 1;
    cout << bfs();
    return 0;
}

핵심 아이디어는 각 위치에 머물러 있을 수 있는 횟수를 정해놓고, 인접한 방에 들어가 값이 0이 되기 전에 불이 켜진다면 계속 진행하는 방식이다.

먼저 네트워크에서 미아 패킷을 방지하기 위해 패킷에 hop-count 를 정해두듯이 다른 방에서 현재 위치한 방의 불을 켜 주기까지 기다릴 수 있는 최대 횟수를 정해 놓는다. (bfs 탐색 개념을 이용하기 때문에 NxN 크기의 방에서의 최대 이동 횟수는 최대 2*N 이다.) 이동한 방이 불이 꺼져있다면 큐에 해당 좌표를 최대 2*N번 다시 삽입하게 되는데, 0이 되기 전까지 불이 켜지지 않는다면 이동할 수 없는 방으로 간주한다.

시간복잡도는 n이 100인 최악의 경우 모든 좌표(100x100)마다 200(2*100)씩 기다린다고 해도 최대 2,000,000 으로 1초 안에 문제없이 통과할 수 있다.