[백준] 20165번 인내의 도미노 장인
백준 20165번 인내의 도미노 장인 문제 풀이
문제 설명
사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 공격과 수비를 하는 게임이다. 공격수는 도미노를 계속 넘어뜨리고 수비수는 도미노를 계속 세우려고 한다. 본 게임은 다음과 같이 진행된다.
- N 행 M 열의 2차원 격자 모양의 게임판의 각 격자에 도미노를 세운다. 각 도미노는 1 이상 5 이하의 높이를 가진다.
- 매 라운드는 공격수가 먼저 공격하고, 수비수는 공격이 끝난 뒤에 수비를 한다.
- 공격수는 특정 격자에 놓인 도미노를 동, 서, 남, 북 중 원하는 방향으로 넘어뜨린다. 길이가 K인 도미노가 특정 방향으로 넘어진다면, 그 방향으로 K-1 개의 도미노들 중에 아직 넘어지지 않은 것들이 같은 방향으로 연달아 넘어진다. 이 때, 당연히 도미노의 특성상, 연쇄적으로 도미노가 넘어질 수 있다. 이미 넘어진 도미노가 있는 칸을 공격한 경우에는 아무 일이 일어나지 않는다.
- 수비수는 넘어져 있는 도미노들 중에 원하는 것 하나를 다시 세울 수 있다. 넘어지지 않은 도미노를 세우려고 하면 아무 일이 일어나지 않는다.
- 총 R 번의 라운드동안 3, 4번 과정이 반복된다. 매 라운드마다 공격수가 해당 라운드에 넘어뜨린 도미노의 개수를 세고, R 라운드에 걸친 총합이 곧 공격수의 점수가 된다.
도미노 공격에 대한 예시 그림이다. 그림의 빨간 숫자들은 넘어진 도미노들을 의미한다.
예를 들어 {3, 1, 2, 2, 2} 높이의 도미노가 일렬로 서 있는 과정에서 3번을 오른쪽으로 밀면 왼쪽의 3개가 오른쪽으로 넘어지게 된다. 이에 따라 새롭게 넘어진 도미노들의 연쇄작용이 발생하는데, 이 과정에서 4번째에 위치한 길이 2짜리 도미노도 넘어지게 된다. 이어서 마지막 도미노까지 쓰러지게 되는 것이다.
인내를 빼면 시체라고 자부하는 호석이는 당신의 공격을 이겨내고자 수비수를 자처했다. 초기 도미노 판의 상태와, 각 라운드에서 둘의 행동의 기록을 받아서 공격수의 점수와 게임판의 최종 상태를 출력하는 프로그램을 작성하라.
문제를 보고 든 생각
- 구현문제라서 기능별로 함수를 잘 쪼개면 되겠다.
풀이 간단 설명
- 동서남북 방향을 map에 저장했다.
- 공격하면 도미노의 위치와 높이를 큐에 저장해서 계속 넘어뜨렸다.
- 수비할 때 넘어진 보드의 정보를 알아야 하기 때문에 초기 보드의 정보를 저장하는
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;
}
Author And Source
이 문제에 관하여([백준] 20165번 인내의 도미노 장인), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kkoma2623/백준-20165번-인내의-도미노-장인
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 공격과 수비를 하는 게임이다. 공격수는 도미노를 계속 넘어뜨리고 수비수는 도미노를 계속 세우려고 한다. 본 게임은 다음과 같이 진행된다.
- N 행 M 열의 2차원 격자 모양의 게임판의 각 격자에 도미노를 세운다. 각 도미노는 1 이상 5 이하의 높이를 가진다.
- 매 라운드는 공격수가 먼저 공격하고, 수비수는 공격이 끝난 뒤에 수비를 한다.
- 공격수는 특정 격자에 놓인 도미노를 동, 서, 남, 북 중 원하는 방향으로 넘어뜨린다. 길이가 K인 도미노가 특정 방향으로 넘어진다면, 그 방향으로 K-1 개의 도미노들 중에 아직 넘어지지 않은 것들이 같은 방향으로 연달아 넘어진다. 이 때, 당연히 도미노의 특성상, 연쇄적으로 도미노가 넘어질 수 있다. 이미 넘어진 도미노가 있는 칸을 공격한 경우에는 아무 일이 일어나지 않는다.
- 수비수는 넘어져 있는 도미노들 중에 원하는 것 하나를 다시 세울 수 있다. 넘어지지 않은 도미노를 세우려고 하면 아무 일이 일어나지 않는다.
- 총 R 번의 라운드동안 3, 4번 과정이 반복된다. 매 라운드마다 공격수가 해당 라운드에 넘어뜨린 도미노의 개수를 세고, R 라운드에 걸친 총합이 곧 공격수의 점수가 된다.
도미노 공격에 대한 예시 그림이다. 그림의 빨간 숫자들은 넘어진 도미노들을 의미한다.
예를 들어 {3, 1, 2, 2, 2} 높이의 도미노가 일렬로 서 있는 과정에서 3번을 오른쪽으로 밀면 왼쪽의 3개가 오른쪽으로 넘어지게 된다. 이에 따라 새롭게 넘어진 도미노들의 연쇄작용이 발생하는데, 이 과정에서 4번째에 위치한 길이 2짜리 도미노도 넘어지게 된다. 이어서 마지막 도미노까지 쓰러지게 되는 것이다.
인내를 빼면 시체라고 자부하는 호석이는 당신의 공격을 이겨내고자 수비수를 자처했다. 초기 도미노 판의 상태와, 각 라운드에서 둘의 행동의 기록을 받아서 공격수의 점수와 게임판의 최종 상태를 출력하는 프로그램을 작성하라.
- 구현문제라서 기능별로 함수를 잘 쪼개면 되겠다.
풀이 간단 설명
- 동서남북 방향을 map에 저장했다.
- 공격하면 도미노의 위치와 높이를 큐에 저장해서 계속 넘어뜨렸다.
- 수비할 때 넘어진 보드의 정보를 알아야 하기 때문에 초기 보드의 정보를 저장하는
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;
}
Author And Source
이 문제에 관하여([백준] 20165번 인내의 도미노 장인), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kkoma2623/백준-20165번-인내의-도미노-장인
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 동서남북 방향을 map에 저장했다.
- 공격하면 도미노의 위치와 높이를 큐에 저장해서 계속 넘어뜨렸다.
- 수비할 때 넘어진 보드의 정보를 알아야 하기 때문에 초기 보드의 정보를 저장하는
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;
}
Author And Source
이 문제에 관하여([백준] 20165번 인내의 도미노 장인), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kkoma2623/백준-20165번-인내의-도미노-장인저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)