백준 26124번: 조명 배치 (C++)

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

26124번: 조명 배치

---

Level: Gold V

Solved By: BFS, Implementation

 

구현이 꽤 어려운 문제였습니다. 아이디어는 꽤 직관적입니다. BFS를 통해 현재 좌표값에서 조명을 켤 수 있는가, 없는가를 알아냅니다. 켤 수 있다면, check 2차원 배열을 통해 조명으로 비춘 지역들을 check 해주었습니다.

 

그리고, 켤 수 없는 경우에는 이미 BFS를 진행하는 동안 좌표값들을 여러 개 방문 체크를 했었는데 어떻게 해야 할지 고민했습니다. 이런 경우 BFS에서 큐를 하나 사용하여 BFS가 진행하는 동안 사용된 좌표 값을 전부 담아서 아니라고 판단된 경우, 큐의 담긴 좌표 값들은 check 할 수 없다고 해주었습니다.

 

BFS의 다음 좌표 값을 넘어가는 과정이 꽤나 복잡한데 하나씩 설명하겠습니다.

if(dy < 1 || dy > H || dx < 1 || dx > W) continue; // out of bound

당연히 범위를 넘어가면 좌표값을 알 수 없습니다. 넘어가 줍니다.

if(visited[dy][dx]) continue; // 중복 제거

방문 체크를 하지 않으면 무한 루프를 돌게 됩니다.

if(graph[dy][dx] == -1) continue; // 벽은 뛰어넘기

벽에 부딪히게 되면 더 이상 빛이 넘어가지 않습니다. 그리고, 벽이 BFS에 걸릴 경우 base case로 check 처리하기 때문에 괜찮습니다. 0도 마찬가지입니다.

if(graph[ny][nx] - 1 == graph[dy][dx]){ // 가능하다면 다음 q로 push
	q.push({dy, dx});
	q_p.push({dy, dx});
	visited[dy][dx] = true;
}

현재 좌표 값에서 빛이 점점 옅어지는 경우입니다. 즉, -1이 된다면 큐에 push를 해주어야 합니다.

else if(graph[ny][nx] == graph[dy][dx]) continue; // 같다면 뛰어넘기

같은 경우는 거리가 서로 먼 조명 2개에서 비추다가 옅어지는 부분에서 만난 경우가 될 수도 있고, 둘 다 조명이 될 수 있습니다. 그렇기 때문에 넘어가 줍니다.

else if(graph[ny][nx] < graph[dy][dx]) continue;

현재 BFS에서는 가능한지도 알아내지만, row, col에서 비치는 조명의 구역을 구하기 때문에 빛의 세기가 갈수록 커진다면 당연히 넘어가 줍니다.

else{ // 현재 조명으로 할 수 없다면 불가능하다고 판단
	flag = false;
	break;
}

그렇게 되면 남은 else는 현재 좌표값에서 다음 좌표값의 조명 세기를 뺀 값이 2 이상 차이 나게 되므로 불가능한 것입니다. 이러한 경우에는 불가능하다고 판단하고 flag에 false 처리하여 check하지 않습니다.

 

BFS에서 조건은 이게 끝이지만, 전체적인 문제에서 위 조건들만 따지면 틀리게 됩니다. 아래가 그에 대한 반례입니다.

input:
2 2
1 2
2 2
output:
4

(1, 1)부터 (H, W)까지 탐색하니 이러한 경우가 발생합니다. (1, 1)은 조명 값이 1로 인접해있는 구역의 조명 값은 1보다 크므로 건너뛰게 됩니다. 그러므로 설치해도 된다고 인식합니다. 나머지 (1, 2), (2, 1), (2, 2)도 설치해도 된다고 인식하고요. 이러한 반례는 아래와 같이 처리했습니다.

 

좌표값을 받아서 조명 값의 크기를 기준으로 내림차순으로 정렬 후, 순차적으로 탐색을 실행한다.

즉, (1, 1) ~ (H, W) 같은 탐색이 아닌 정렬을 하여 큰 값부터 BFS를 해보자는 뜻입니다. 다음과 같은 반례까지 정리해주면 문제를 풀 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define INF 1e9
#define MAX 1001
using namespace std;
typedef pair<int, int> pii;

int H, W;
int graph[MAX][MAX];
bool visited[MAX][MAX]; // 조명 비추는 구역 확인용
bool check[MAX][MAX]; // 모든 구역 확인용

struct Dir{
    int y, x;
};

Dir dir[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

bool bfs(int row, int col){
    if(graph[row][col] == -1 || graph[row][col] == 0){
        check[row][col] = true;
        return false;
    }
    queue<pii> q; q.push({row, col});
    visited[row][col] = true;
    
    queue<pii> q_p; q_p.push({row, col});
    bool flag = true;
    
    
    while(!q.empty()){
        int ny = q.front().first;
        int nx = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int dy = ny + dir[i].y;
            int dx = nx + dir[i].x;
            if(dy < 1 || dy > H || dx < 1 || dx > W) continue; // out of bound
            if(visited[dy][dx]) continue; // 중복 제거
            if(graph[dy][dx] == -1) continue; // 벽은 뛰어넘기
            if(graph[ny][nx] - 1 == graph[dy][dx]){ // 가능하다면 다음 q로 push
                q.push({dy, dx});
                q_p.push({dy, dx});
                visited[dy][dx] = true;
            }
            else if(graph[ny][nx] == graph[dy][dx]) continue; // 같다면 뛰어넘기
            else if(graph[ny][nx] < graph[dy][dx]) continue;
            else{ // 현재 조명으로 할 수 없다면 불가능하다고 판단
                flag = false;
                break;
            }
        }
        if(!flag) break;
    }
    
    if(flag){ // row, col의 조명으로 될 경우 조명으로 밝힌 구역들 check
        while(!q_p.empty()){
            int ny = q_p.front().first;
            int nx = q_p.front().second;
            q_p.pop();
            
            check[ny][nx] = true;
            visited[ny][nx] = false;
        }
        return true;
    }
    else{
        while(!q_p.empty()){
            int ny = q_p.front().first;
            int nx = q_p.front().second;
            q_p.pop();
            
            visited[ny][nx] = false;
        }
        return false;
    }
}

bool cmp(pii a, pii b){
    return graph[a.first][a.second] > graph[b.first][b.second];
}

int main(){
    FASTIO
    cin >> H >> W;
    
    vector<pii> p;
    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            cin >> graph[i][j];
            p.push_back({i, j});
        }
    }
    sort(p.begin(), p.end(), cmp);
    
    int res = 0;
    
    for(int i = 0; i < p.size(); i++){
        int y = p[i].first, x = p[i].second;
        if(!check[y][x]){
            if(bfs(y, x)) res++;
        }
    }
    
    bool res_flag = true;
    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            if(!check[i][j]) res_flag = false;
        }
    }
    
    if(res_flag) cout << res;
    else cout << -1;
    
    return 0;
}