[백준 - 11967] 불켜기 - C++

분류: BFS /

 

문제

문제 링크

문제 설명

농부 존은 최근에 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)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

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

 

풀이

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct xy {int x, y;};
int N, M;
bool lights[101][101];
bool vis[101][101];
vector<xy> btns[101][101];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    while(M--) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        btns[x][y].push_back({a, b});
    }
    queue<xy> Q;
    int cnt = 1;
    lights[1][1] = true;
    vis[1][1] = true;
    Q.push({1, 1});
    while(!Q.empty()) {
        xy cur = Q.front(); Q.pop();
        auto &curBtns = btns[cur.x][cur.y];
        while(!curBtns.empty()) {
            const xy &btn = curBtns.back(); curBtns.pop_back();
            if(btn.x && btn.y && !lights[btn.x][btn.y]) {
                lights[btn.x][btn.y] = true;
                cnt++;
                for(int i=4; i--;) {
                    int nx = btn.x + dx[i], ny = btn.y + dy[i];
                    if(nx<1 || nx>N || ny<1 || ny>N) continue;
                    if(vis[nx][ny]) {
                        vis[btn.x][btn.y] = true;
                        Q.push(btn);
                        break;
                    }
                }
            }
        }
        for(int i=4; i--;) {
            int nx = cur.x + dx[i], ny = cur.y + dy[i];
            if(nx<1 || nx>N || ny<1 || ny>N) continue;
            if(vis[nx][ny] || !lights[nx][ny]) continue;
            vis[nx][ny] = true;
            Q.push({nx, ny});
        }
    }
    cout << cnt;
}

• `btns`에 2차원 인접리스트로 버튼 저장(btn이 짧고 switch는 키워드여서 btn이라 하겠음)
• 더이상 갈 수 있는 곳이 없을 때까지 다음일 수행(BFS + 추가 삽입)
  • 현재있는 방(`cur`)의 버튼들로 다음을 수행 (`curBtns`는 현재 방에 있는 버튼들)
    • 불이 꺼져있다면 불을 킴 + `cnt++` (`cnt`는 켠 불의 수, 답)
    • 방금 킨 불이 지나갈때는 꺼져있었어서 지나친 곳이라면 큐에 삽입, 방문
  • 현재 방에 인접하고 방문하지 않은 방 중 불이 켜져있는 곳이 있다면 이동(큐에 삽입, 방문)

 

BFS라고 하기는 애매하다.

중간에 지나칠 당시에는 불이 꺼져있어 가지 않고 지나쳤던 곳을 나중에 다시 삽입한다.

"지나쳤다"의 의미는 "주변에 방문한 곳이 있다."이다.

방금 불을 킨 방은 불이 꺼져있었기 때문에 절대 방문하지 않았다.

이때 주변에 방문했던 곳이 있다면 방금 킨 방은 지나쳤거나 지금 가야하는 방이다.

따라서 큐에 삽입하고 방문 표시를 한다.

 

갈 수 있는 곳중에 가장 먼 곳을 찾는 문제라면 더 재밌을것 같다.

순수한 BFS가 아니기 때문에 방문 순서가 거리를 보장하지 못한다.

불을 모두 키고 다시 BFS로 거리를 측정하거나

방금 불을 킨 방에 인접한 지나쳤던 곳까지의 거리를 이용해 계산할 수 있을 것 같다.

 

탈출하는데 걸리는 최소 시간도 괜찮은 문제일것 같다.

이건 매번 불을 새로 킬 때마다 현재 위치에서 다시 bfs를 해야하나? 

재귀 속에 bfs면 시간복잡도나 공간복잡도가 말도안되게 커질 것 같은데...

일단 최단 시간에 탈출을 하고 역추적을 해도 될것같다.