백준 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짜리 도미노도 넘어지게 된다. 이어서 마지막 도미노까지 쓰러지게 되는 것이다.

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

문제를 보고 든 생각

• 구현문제라서 기능별로 함수를 잘 쪼개면 되겠다.

풀이 간단 설명

1. 동서남북 방향을 map에 저장했다.
2. 공격하면 도미노의 위치와 높이를 큐에 저장해서 계속 넘어뜨렸다.
3. 수비할 때 넘어진 보드의 정보를 알아야 하기 때문에 초기 보드의 정보를 저장하는 originBoard 2차원 배열을 선언했다.

코드

#include <iostream>
#include <map>
#include <queue>

#define MAX_N 100

using namespace std;

struct pos{
  int r, c;
  int height;
};

int N, M, R;
int originBoard[MAX_N+1][MAX_N+1];
int board[MAX_N+1][MAX_N+1];
map<char, pos> dir;

void setDir(){
  dir['E'] = {0, 1};
  dir['W'] = {0 , -1};
  dir['S'] = {1, 0};
  dir['N'] = {-1 , 0};
}

void getInput(){
  cin >> N >> M >> R;
  for(int r=1; r<=N; ++r){
    for(int c=1; c<=M; ++c){
      cin >> originBoard[r][c];
    }
  }
}

bool checkBound(int r, int c){
  return (r < 1 || c < 1 || r > N || c > M);
}

int attack(){
  pos p; cin >> p.r >> p.c;
  char dirChar; cin >> dirChar;
  pos d = dir[dirChar];

  int score = 0;
  queue<pos> q;
  q.push({p.r, p.c, board[p.r][p.c]});
  while(!q.empty()){
    pos curr = q.front(); q.pop();
    if(checkBound(curr.r, curr.c)){
      continue;
    }
    if(board[curr.r][curr.c] == -1){
      continue;
    }
    board[curr.r][curr.c] = -1;
    ++score;
    
    for(int i=1; i<curr.height; ++i){
      int nr = curr.r + d.r*i;
      int nc = curr.c + d.c*i;
      if(checkBound(nr, nc)){
        continue;
      }
      if(board[nr][nc] == -1){
        continue;
      }
      q.push({nr, nc, board[nr][nc]});
    }
  }

  return score;
}

void defense(){
  pos p; cin >> p.r >> p.c;
  if(board[p.r][p.c] != -1){
    return;
  }

  board[p.r][p.c] = originBoard[p.r][p.c];
}

void copyOriginBoard(){
  for(int r=1; r<=N; ++r){
    for(int c=1; c<=M; ++c){
      board[r][c] = originBoard[r][c];
    }
  }
}

void printBoard(){
  for(int r=1; r<=N; ++r){
    for(int c=1; c<=M; ++c){
      if(board[r][c] == -1){
        cout << "F ";
      } else{
        cout << "S ";
      }
    }cout << "\n";
  }
}

void solve(){
  setDir();
  getInput();
  copyOriginBoard();
  int score = 0;
  while(R--){
    score += attack();
    defense();
  }

  cout << score << "\n";
  printBoard();
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();

  return 0;
}