[C++] 백준 11967번: 불켜기

> 문제

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

11967번: 불켜기

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다. 베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

 

> 풀이

기본적으로 예전에 풀었던 카카오 인턴 문제' 동굴탐험'과 유사하게 풀었다. 

https://korini.tistory.com/26?category=986031 

[C++] Programmers 동굴탐험 (2020 카카오 인턴십)

하지만, 동굴 탐험 문제에서는 위상정렬을 이용하면 더 문제를 쉽게 풀 수 있었지만, 이번 문제에서는 하나의 방의 불을 킬 수 있는 방이 여러개이고 그 중 어느 방이라도 먼저 방문하면 된다는 점에서 위상정렬 알고리즘을 직접적으로 사용할 수 없다. 대신, 해당 코드에서 동굴을 방문했지만 우선으로 방문해야하는 동굴이 있어 아직 가지는 못하는 동굴을 표시해놓고, 만약 우선 순위 동굴을 방문하면 표시했던 동굴을 바로 다음으로 방문한다는 부분을 차용했다. 이번 문제에서도 방문했지만 아직 불이 켜지지 않은 방을 따로 표시해놓고 다른 방을 들렸을 때 표시한 해당 방의 불을 켤 수 있다면 바로 다음으로 방문한다. '동굴탐험' 문제에서 선행해야하는 동굴이 하나로 한정되어있고, 이번 문제도 하나의 방을 제어할 수 있는 방은 여러개지만, 그 중 하나만이라도 먼저 접근할 수 있다면 해당 방을 방문할 수 있기 때문에 이렇게 코드를 짤 수 있었다.

 

> 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<vector<vector<pair<int,int>>>> graph;
vector<vector<int>> visited;  // -1: aleardy been, 0: never, 1: tried, but cannot
vector<vector<bool>> is_turnon;  // 0: turn-off, 1: turn-on

int x_d[] = {0, 0, -1, 1};
int y_d[] = {1, -1, 0, 0};

bool withinRange(int x, int y, int N) {
    if (x < N && x >= 0 && y < N && y >=0) return true;
    else return false;
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M); 
    graph.assign(N, vector<vector<pair<int,int>>>(N, vector<pair<int,int>>({})));
    visited.assign(N, vector<int>(N, 0));
    is_turnon.assign(N, vector<bool>(N, false));
    
    int x, y, a, b;
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d %d", &x, &y, &a, &b);
        graph[y-1][x-1].push_back({a-1,b-1});
    }
    
    
    is_turnon[0][0] = true;
    int cnt = 1;
    
    queue<pair<int,int>> q;
    q.push({0, 0});
    
    while(q.size()) {
        pair<int, int> ele = q.front();
        q.pop();
        int cur_x = ele.first;
        int cur_y = ele.second;
        visited[cur_y][cur_x] = -1;
        
        for (int d=0; d < 4; d++) {
            int next_x = cur_x + x_d[d];
            int next_y = cur_y + y_d[d];
            
            if (withinRange(next_x, next_y, N) && visited[next_y][next_x] != -1) { 
                visited[next_y][next_x] = 1;
                if (is_turnon[next_y][next_x]) {  // can go
                    q.push({next_x, next_y});
                }
            }
        }
        
        // turn on the switch which can turn on at the current place 
        // no need to check validity
        for (int k = 0; k < graph[cur_y][cur_x].size(); k++) {
            int temp_x = graph[cur_y][cur_x][k].first;
            int temp_y = graph[cur_y][cur_x][k].second;
            
            if (visited[temp_y][temp_x] == -1 || is_turnon[temp_y][temp_x] == true) continue;
            
            is_turnon[temp_y][temp_x] = true;
            cnt++;
            if (visited[temp_y][temp_x] == 1) {
                q.push({temp_x, temp_y});
            }
        }
    }
    printf("%d", cnt);

    return 0;
}

> 결과