[BOJ] 20165 - 인내의 도미노 장인 호석

💎 문제

사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 공격과 수비를 하는 게임이다. 공격수는 도미노를 계속 넘어뜨리고 수비수는 도미노를 계속 세우려고 한다. 본 게임은 다음과 같이 진행된다.

1. N 행 M 열의 2차원 격자 모양의 게임판의 각 격자에 도미노를 세운다. 각 도미노는 1 이상 5 이하의 높이를 가진다.
2. 매 라운드는 공격수가 먼저 공격하고, 수비수는 공격이 끝난 뒤에 수비를 한다.
3. 공격수는 특정 격자에 놓인 도미노를 동, 서, 남, 북 중 원하는 방향으로 넘어뜨린다. 길이가 K인 도미노가 특정 방향으로 넘어진다면, 그 방향으로 K-1 개의 도미노들 중에 아직 넘어지지 않은 것들이 같은 방향으로 연달아 넘어진다. 이 때, 당연히 도미노의 특성상, 연쇄적으로 도미노가 넘어질 수 있다. 이미 넘어진 도미노가 있는 칸을 공격한 경우에는 아무 일이 일어나지 않는다.
4. 수비수는 넘어져 있는 도미노들 중에 원하는 것 하나를 다시 세울 수 있다. 넘어지지 않은 도미노를 세우려고 하면 아무 일이 일어나지 않는다.
5. 총 R 번의 라운드동안 3, 4번 과정이 반복된다. 매 라운드마다 공격수가 해당 라운드에 넘어뜨린 도미노의 개수를 세고, R 라운드에 걸친 총합이 곧 공격수의 점수가 된다.

도미노 공격에 대한 예시 그림이다. 그림의 빨간 숫자들은 넘어진 도미노들을 의미한다.

예를 들어 {3, 1, 2, 2, 2} 높이의 도미노가 일렬로 서 있는 과정에서 3번을 오른쪽으로 밀면 왼쪽의 3개가 오른쪽으로 넘어지게 된다. 이에 따라 새롭게 넘어진 도미노들의 연쇄작용이 발생하는데, 이 과정에서 4번째에 위치한 길이 2짜리 도미노도 넘어지게 된다. 이어서 마지막 도미노까지 쓰러지게 되는 것이다.

인내를 빼면 시체라고 자부하는 호석이는 당신의 공격을 이겨내고자 수비수를 자처했다. 초기 도미노 판의 상태와, 각 라운드에서 둘의 행동의 기록을 받아서 공격수의 점수와 게임판의 최종 상태를 출력하는 프로그램을 작성하라.

💎 입력

첫 번째 줄에는 게임판의 행 개수 N, 열 개수 M, 라운드 횟수 R 이 주어진다.

이어서 N개의 줄에 게임판의 상태가 주어진다. 1행부터 주어지며, M 개의 숫자는 각 격자에 놓인 도미노의 길이를 의미한다.

이어서 R×2 개의 줄에 걸쳐서 공격수와 수비수의 행동이 주어진다. 각 라운드는 두 줄로 이뤄지며, 첫 줄은 공격수, 두번째 줄은 수비수의 행동이 주어진다. 공격수의 행동은 "X Y D"로 주어진다. 이는 X행 Y열의 도미노를 D 방향으로 민다는 뜻이다. D는 E, W, S, N 중 하나이며 각각 동, 서, 남, 북 방향을 의미한다. 수비수의 행동은 "X Y"로 주어진다. 이는 X행 Y열의 도미노를 다시 세운다는 뜻이다.

만약 이미 넘어진 격자의 도미노를 공격수가 넘어뜨리려 할 때에는 아무 일도 일어나지 않는다. 또한 만약 넘어지지 않은 도미노를 수비수가 세우려고 할 때에도 아무 일도 일어나지 않는다.

💎 출력

첫 줄에 공격수의 점수를 출력한다.

이어서 게임판의 상태를 N 줄에 걸쳐서 출력한다. 각 격자마다 넘어진 것은 F, 넘어지지 않은 것은 S 를 공백으로 구분하여 출력한다.

💎 제한

입력되는 모든 값은 양의 정수이다.

• 1 ≤ N, M ≤ 100
• 1 ≤ R ≤ 10,000
• 1 ≤ 도미노의 길이 ≤ 5
• 공격수와 수비수는 격자를 벗어나는 행동은 하지 않는다.

💎 풀이 방법

문제를 보고 살짝 당황했는데 생각보다 쉬웠다. 찬찬히 잘 읽는다면 이해하기 쉬웠고 적용하는 방법도 그대로 한다면 수월하게 해결할 수 있을 것 같다!!
중요한 점은 도미노를 넘어뜨렸을 때 도미노의 길이를 어떤 식으로 업데이트 해줄지, 그리고 이미 넘어진 도미노를 어떻게 고려해줄지 정도만 생각한다면 easy~한 문제였다.

문제를 해결하기 위해서 int형의 domino 배열과 함께 char형의 state배열을 선언해주어 도미노의 크기와 도미노가 넘어졌는지 서있는지 상태를 확인받고자하였다. 공격자가 공격을 진행하는 R번의 횟수동안에서 우리는 도미노의 크기에 따라서 넘어지는 도미노를 카운트해주고 상태를 적용해주면 된다!!

		.
		.
		.
        int n, m;
        char way;
        cin >> n >> m >> way;
        int count = domino[n][m];
        if(way == 'E'){
            while(count != 0 && m <= M){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                m++;
                count--;
            }
        }
        .
        .
        .

따라서,,, 위의 코드 처럼 n행 m열에 위치한 도미노를 기준으로 동,서,남,북 중 하나의 방향을 정하여 도미노가 넘어지는 과정을 수행해주면된다. 이 때 count라는 변수를 통해서 도미노의 크기는 방향을 진행함에 따라 하나씩 감소할 것이며 만약 자신보다 더 큰 도미노의 크기를 만난다면 그 도미노의 크기를 따라갈 것이다.

그렇기 때문에 서있는 상태의 도미노를 만나게 된다면 서있는 도미노의 크기를 확인하여 업데이트 여부를 결정하고 그 도미노를 넘어져있는 상태로 바꾸어주어 넘어진 도미노를 카운트해주면 되는 것이다!! 그리고 이러한 반복은 도미노의 크기가 0이 되거나 설정한 N, M의 크기의 2차원배열의 도미노 게임판을 넘어가는 경우 종료해주면 된다.

이외의 내용들은 정말 문제 그대로 구현하면 되기 때문에 고려해야할 점은 위를 조심하면 될 것 같다!!

💎 전체 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int domino[101][101];
char state[101][101];
int N, M, R;

int main(int argc, const char * argv[]) {
    
    cin >> N >> M >> R;
    memset(state, 'S', sizeof(state));
    
    for(int i = 1;i <= N;i++){
        for(int j = 1;j <= M;j++){
            cin >> domino[i][j];
        }
    }
    int result = 0;
    while(R--){
        int n, m;
        char way;
        cin >> n >> m >> way;
        int count = domino[n][m];
        if(way == 'E'){
            while(count != 0 && m <= M){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                m++;
                count--;
            }
        }
        else if(way == 'W'){
            while(count != 0 && m > 0){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                m--;
                count--;
            }
        }
        else if(way == 'S'){
            while(count != 0 && n <= N){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                n++;
                count--;
            }
        }
        else{
            while(count != 0 && n > 0){
                if(state[n][m] == 'S'){
                    count = max(count, domino[n][m]);
                    state[n][m] = 'F';
                    result++;
                }
                n--;
                count--;
            }
        }
        int standX, standY;
        cin >> standX >> standY;
        state[standX][standY] = 'S';
    }
    cout << result << "\n";
    
    for(int i = 1;i <= N;i++){
        for(int j = 1;j <= M;j++){
            cout << state[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

💎 고민

오랜만에 velog 업로드인데 꾸준히 하려구해도 후,,,,학기가 시작하니 확실히 바빠진 것 같다. 주말에 알고리즘을 풀었을 때 내가 고민을 많이 했던 문제는 정리해보고 싶은데 쉽지 않넴,,, 벌써 3월이 다 지나고 4월이 되서 1년의 1분기가 지났는데 이것저것 하나씩 해내고 있으면서도 일을 벌리는 느낌이다,,,꾸준히 알고리즘은 풀어줄 수 있도록 하자!! 하지만 학기중에는 동아리랑 수업을 제발 더 우선시~~

화이팅!!