[백준/C++/Gold(5)] 28291 - 레드스톤

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

28291번: 레드스톤

본인이 해당 문제의 출제자가 아니며, 문제 자체에 대한 모든 사항은 위의 링크가 출처임을 명시합니다.

 

 문제의 제목을 마인크래프트의 레드스톤! 이라고 바로 생각이 들어서 들어간 문제이다. 실제로 게임에서 보았던 "레드스톤"과 비슷한 기믹을 들고온 문제이기 때문에 일단 풀어보기로 하였다. 일단 기본적으로 어딘가에서 "퍼지는" 것을 시뮬레이션 해야할 것 같았기 때문에 적어도 그래프 이론 문제일거라 생각했고, 실제로 적중했다.

 

문제는 이렇다 : 

 

레드스톤 회로 블록들을 이용해 $W×H$ 크기의 사각형 맵에 회로를 만들었다. 회로 블록에는 레드스톤 가루, 레드스톤 블록, 레드스톤 램프가 있다.

• 레드스톤 가루(redstone_dust)는 상하좌우로 인접한 회로 블록에 매초마다 전기 신호를 전달하며, 전달할 회로 블록에 더 큰 전기 신호가 있다면 전달하지 않는다.
• 레드스톤 블록(redstone_block)은 전기 신호를 15만큼 가지고 있으며 상하좌우로 인접한 회로 블록에 15만큼의 전기 신호를 매초마다 전달한다.
• 레드스톤 램프(redstone_lamp)는 1 이상의 전기 신호를 받을 경우 불이 켜진다.

전기 신호는 회로 블록들이 작동하기 위해 필요한 에너지로 레드스톤 가루(redstone_dust)에서 다른 블록으로 전달될 때 1 감소하며 0 이하가 될 시 사라진다. 또한 여러 전기 신호가 한 블록에 모일 경우 그중 가장 큰 신호가 그 블록의 신호의 세기가 된다.

모든 회로 블록은 여러 번 행동할 수 있으며, 모두 동시에 행동한다.

 

생각 : 

 

 "레드스톤 블록(redstone_block) 에서 신호가 퍼져서 인접한 다른 블록에 하나씩 신호를 전달하며, 이는 레드스톤 가루(redstone_dust) 가 있는 곳에 한정한다."고 관점을 바꾸어서 보자. 모든 블록, 가루, 램프는 그래프의 정점으로 본다. 이 문제는 어떤 블록에서 시작하는 bfs를 이용해, "어떤 블록에서 램프까지 15 depth 미만에 도달할 수 있는가?"라는 질문에 답함으로써 풀 수 있다.

 여기서 레드스톤 가루와 블록, 램프의 위치를 줄테니, 모든 램프가 켜지는지를 알려달라는 것이 문제였다. 처음 만든 코드가 이것이었다. 해당코드는 대략 52%까지 채점을 진행하다 실패했다.

 

코드 1 : 

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int map[55][55] = {0};
int power[55][55] = {0};
int total = 0;
int w, h, n;

#define Cord pair<int, int>

void bfs(Cord start){
    queue<Cord> q;
    int curr_power = 15;
    q.push(start);
    power[start.first][start.second] = curr_power;
    while(!(q.empty())){
        int track = q.size();
        for(int i = 0; i < track; i++){
            Cord node = q.front();
            q.pop();
            Cord near[5] = {
                {node.first + 1, node.second},
                {node.first, node.second + 1},
                {node.first - 1, node.second},
                {node.first, node.second - 1},
            };
            for(Cord check : near){
                if(1 <= check.first && check.first <= w && 1 <= check.second && check.second <= h){
                    if(map[check.first][check.second] && power[check.first][check.second] < curr_power){
                        q.push(check);
                        power[check.first][check.second] = curr_power;
                    }
                }
            }
        }
        curr_power--;
    }
}

int main()
{
    cin >> w >> h >> n;
    
    vector<Cord> all_blocks;
    vector<Cord> all_lamps;
    
    for(int i = 0; i < n; i++){
        Cord input;
        string type;
        cin >> type >> input.first >> input.second;
        ++input.first;
        ++input.second;
        if(type == "redstone_block"){
            map[input.first][input.second] = 2;
            all_blocks.push_back(input);
        } else if(type == "redstone_lamp"){
            map[input.first][input.second] = 3;
            all_lamps.push_back(input);
        } else {
            map[input.first][input.second] = 1;
        }
    }
    
    /*for(int i = 1; i <= w; i++){
        for(int j = 1; j <= h; j++){
            cout << map[i][j] << ' ';
        }
        cout << '\n';
    }*/
    
    for(Cord block : all_blocks){
        bfs(block);
    }
    
    /*for(int i = 1; i <= w; i++){
        for(int j = 1; j <= h; j++){
            cout << power[i][j] << ' ';
        }
        cout << '\n';
    }*/
    
    bool lit = true;
    for(Cord lamp : all_lamps){
        lit = lit && power[lamp.first][lamp.second];
    }
    
    cout << (lit ? "success" : "failed");

    return 0;
}

 

당연히 모든 예제를 통과 했었으며, 가루 없이 블록과 램프로만 되어있거나 하는 경우도 전부 테스트 해봤는데, 도저히 뭐가 문제인지 가늠이 되지 않았다...

 

예제 :

 

5 5
6
redstone_lamp 0 1
redstone_lamp 1 0
redstone_lamp 2 1
redstone_lamp 1 2
redstone_block 2 2
redstone_block 0 0

결과 : success

19 1
19
redstone_block 0 0
redstone_dust 1 0
redstone_dust 2 0
redstone_dust 3 0
redstone_dust 4 0
redstone_dust 5 0
redstone_dust 6 0
redstone_dust 7 0
redstone_dust 8 0
redstone_dust 9 0
redstone_dust 10 0
redstone_dust 11 0
redstone_dust 12 0
redstone_dust 13 0
redstone_dust 14 0
redstone_dust 15 0
redstone_dust 18 0
redstone_dust 17 0
redstone_lamp 16 0

결과 : success

19 19
20
redstone_block 0 15
redstone_block 0 0
redstone_dust 1 0
redstone_dust 1 1
redstone_dust 1 2
redstone_dust 1 3
redstone_dust 1 4
redstone_dust 1 5
redstone_dust 1 6
redstone_dust 1 7
redstone_dust 1 8
redstone_dust 1 9
redstone_dust 1 10
redstone_dust 1 11
redstone_dust 1 12
redstone_dust 1 13
redstone_dust 1 14
redstone_dust 1 15
redstone_lamp 2 2
redstone_lamp 8 8

결과 : failed

 

그래서 램프가 신호를 확인하는 조건이나 dfs에서 퍼지는 조건을 바꾸어 보기도 했다.

 

코드 2 (인접한 4칸의 power 확인으로 변경): 

 

    bool lit = true;
    for(Cord lamp : all_lamps){
        bool powa = 
             power[lamp.first + 1][lamp.second] || 
             power[lamp.first - 1][lamp.second] || 
             power[lamp.first][lamp.second + 1] || 
             power[lamp.first][lamp.second - 1];
        lit = lit && powa;
        //lit = lit && power[lamp.first][lamp.second];
    }

 

코드 3 (가루에서만 전파되게끔 변경) : 

     	for(Cord check : near){
                if(1 <= check.first && check.first <= w && 1 <= check.second && check.second <= h){
                    if(power[check.first][check.second] < curr_power){
                        if(map[check.first][check.second] == 1){
                            q.push(check);
                            power[check.first][check.second] = curr_power;
                        }
                    }
                }
            }

 

하지만 둘 다 되려 낮은 정답률을 보였다. 하지만 2~3을 작성하면서 알아낸 사실은, 램프는 신호를 전파하지 않는다는 것이다. 실제로 3번의 코드는 맞는 코드였다. 그럼에도 불구하고 점수가 낮은 것은, 다른 곳에 문제가 있다는 것을 알려주었다. 나는 아예 dfs를 돌리면서 인접한 lamp들을 전부 등록시켜서 그게 lamp의 총 개수와 같다면 success를 출력하게끔 바꾸어 보는 것은 어떤가하는 생각이 들었다.

 

정답 코드 : 

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int map[55][55] = {0};
int power[55][55] = {0};
int total = 0;
int w, h, n;

#define Cord pair<int, int>

void bfs(Cord start){
    queue<Cord> q;
    int curr_power = 15;
    q.push(start);
    power[start.first][start.second] = curr_power;
    while(!(q.empty())){
        int track = q.size();
        for(int i = 0; i < track; i++){
            Cord node = q.front();
            q.pop();
            Cord near[5] = {
                {node.first + 1, node.second},
                {node.first, node.second + 1},
                {node.first - 1, node.second},
                {node.first, node.second - 1},
            };
            for(Cord check : near){
                if(1 <= check.first && check.first <= w && 1 <= check.second && check.second <= h){
                    if(power[check.first][check.second] < curr_power){
                        if(map[check.first][check.second] == 1){
                            q.push(check);
                            power[check.first][check.second] = curr_power;
                        } else if(map[check.first][check.second] == 3) {
                            power[check.first][check.second] = 16;
                            total++;
                        }
                    }
                }
            }
        }
        curr_power--;
    }
}

int main()
{
    cin >> w >> h >> n;
    
    vector<Cord> all_blocks;
    vector<Cord> all_lamps;
    
    for(int i = 0; i < n; i++){
        Cord input;
        string type;
        cin >> type >> input.first >> input.second;
        ++input.first;
        ++input.second;
        if(type == "redstone_block"){
            map[input.first][input.second] = 2;
            all_blocks.push_back(input);
        } else if(type == "redstone_lamp"){
            map[input.first][input.second] = 3;
            all_lamps.push_back(input);
        } else {
            map[input.first][input.second] = 1;
        }
    }
    
    for(Cord block : all_blocks){
        bfs(block);
    }
    
    cout << (total == all_lamps.size() ? "success" : "failed");

    return 0;
}

 

그랬더니 정답이 나왔다. 여전히 의문이다. 분명 거의 같은 역할을 할텐데 왜 나중에 따로 power를 검사하는 것은 안 되는지? dfs에서 인접한 것을 찾는 것은 왜 되는 것일까? 뭐가 반례였던 걸까? 싶다. 지금 글을 쓰면서 생각나는 건데, 거의 신호가 끊기기 직전에 가루를 한 차례 꺾어서? 보는게 반례가 아닐까 싶기도 하지만... 일단 오늘은 졸리니까 이만하고 기록을 마치는게 좋을 것 같다.