728x90
반응형
https://www.acmicpc.net/problem/17837
17837번: 새로운 게임 2
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ17837
//
// Created by 최화연 on 2022/04/28.
//
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int N, K;
struct Horse {
int num = 0;
int r;
int c;
int d;
};
Horse horse;
int board[13][13] = {0, };
vector<Horse> chess[13][13];
Horse horses[11];
int dr[5] = {0, 0, 0, -1, 1};
int dc[5] = {0, 1, -1, 0, 0};
int opposite[5] = {0, 2, 1, 4, 3};
int play_game() {
int turn = 0;
while (turn < 1000) {
turn ++;
for (int i=1; i<=K; i++) {
deque<Horse> dq;
int k = -1;
for (int j=0; j<chess[horses[i].r][horses[i].c].size(); j++) {
if (chess[horses[i].r][horses[i].c][j].num == i) {
k = j;
break;
}
}
int size = chess[horses[i].r][horses[i].c].size();
for (int j=0; j<size-k; j++) {
dq.push_front(chess[horses[i].r][horses[i].c].back());
chess[horses[i].r][horses[i].c].pop_back();
}
int nr = horses[i].r + dr[horses[i].d];
int nc = horses[i].c + dc[horses[i].d];
//파란색 칸이거나 격자를 벗어난 경우,
if (nr < 1 || nr > N || nc < 1 || nc > N || board[nr][nc] == 2) {
dq[0].d = opposite[dq[0].d];
nr += 2*dr[dq[0].d];
nc += 2*dc[dq[0].d];
//파란색 칸이거나 격자를 벗어난 경우, 이동하지 않는다
if (nr < 1 || nr > N || nc < 1 || nc > N || board[nr][nc] == 2) {
while (!dq.empty()) {
Horse h = dq.front();
horses[h.num] = h;
dq.pop_front();
chess[h.r][h.c].push_back(h);
}
}
//이동한다
else {
if (chess[nr][nc].size() + dq.size() >= 4) return turn;
//빨간색인 경우,
if (board[nr][nc] == 1) {
while (!dq.empty()) {
Horse h = dq.back();
h.r = nr;
h.c = nc;
horses[h.num] = h;
dq.pop_back();
chess[nr][nc].push_back(h);
}
}
//흰색인 경우,
{
while (!dq.empty()) {
Horse h = dq.front();
h.r = nr;
h.c = nc;
horses[h.num] = h;
dq.pop_front();
chess[nr][nc].push_back(h);
}
}
}
}
//빨간색 칸인 경우,
else if (board[nr][nc] == 1) {
if (chess[nr][nc].size() + dq.size() >= 4) return turn;
while (!dq.empty()) {
Horse h = dq.back();
h.r = nr;
h.c = nc;
horses[h.num] = h;
dq.pop_back();
chess[nr][nc].push_back(h);
}
}
//흰색인 경우,
else {
if (chess[nr][nc].size() + dq.size() >= 4) return turn;
while (!dq.empty()) {
Horse h = dq.front();
h.r = nr;
h.c = nc;
horses[h.num] = h;
dq.pop_front();
chess[nr][nc].push_back(h);
}
}
}
}
return -1;
}
int main(int argc, const char * argv[]) {
cin >> N >> K;
for (int r=1; r<=N; r++) {
for (int c=1; c<=N; c++) {
cin >> board[r][c];
}
}
for (int k=1; k<=K; k++) {
horse.num = k;
cin >> horse.r >> horse.c >> horse.d;
chess[horse.r][horse.c].push_back(horse);
horses[k] = horse;
}
cout << play_game() << endl;
return 0;
}풀이 과정
풀이 시간 1시간 52분
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int N, K;
struct Horse {
int num = 0;
int r;
int c;
int d;
};
Horse horse;
int board[13][13] = {0, };
vector<Horse> chess[13][13];
Horse horses[11];
int dr[5] = {0, 0, 0, -1, 1};
int dc[5] = {0, 1, -1, 0, 0};
int opposite[5] = {0, 2, 1, 4, 3};
int play_game() {
int turn = 0;
while (turn < 1000) {
turn ++;
for (int i=1; i<=K; i++) {
deque<Horse> dq;
int k = -1;
for (int j=0; j<chess[horses[i].r][horses[i].c].size(); j++) {
if (chess[horses[i].r][horses[i].c][j].num == i) {
k = j;
break;
}
}
int size = chess[horses[i].r][horses[i].c].size();
for (int j=0; j<size-k; j++) {
dq.push_front(chess[horses[i].r][horses[i].c].back());
chess[horses[i].r][horses[i].c].pop_back();
}
int nr = horses[i].r + dr[horses[i].d];
int nc = horses[i].c + dc[horses[i].d];
//파란색 칸이거나 격자를 벗어난 경우,
if (nr < 1 || nr > N || nc < 1 || nc > N || board[nr][nc] == 2) {
dq[0].d = opposite[dq[0].d];
nr += 2*dr[dq[0].d];
nc += 2*dc[dq[0].d];
//파란색 칸이거나 격자를 벗어난 경우, 이동하지 않는다
if (nr < 1 || nr > N || nc < 1 || nc > N || board[nr][nc] == 2) {
while (!dq.empty()) {
Horse h = dq.front();
horses[h.num] = h;
dq.pop_front();
chess[h.r][h.c].push_back(h);
}
}
//이동한다
else {
if (chess[nr][nc].size() + dq.size() >= 4) return turn;
//빨간색인 경우,
if (board[nr][nc] == 1) {
while (!dq.empty()) {
Horse h = dq.back();
h.r = nr;
h.c = nc;
horses[h.num] = h;
dq.pop_back();
chess[nr][nc].push_back(h);
}
}
//흰색인 경우,
{
while (!dq.empty()) {
Horse h = dq.front();
h.r = nr;
h.c = nc;
horses[h.num] = h;
dq.pop_front();
chess[nr][nc].push_back(h);
}
}
}
}
//빨간색 칸인 경우,
else if (board[nr][nc] == 1) {
if (chess[nr][nc].size() + dq.size() >= 4) return turn;
while (!dq.empty()) {
Horse h = dq.back();
h.r = nr;
h.c = nc;
horses[h.num] = h;
dq.pop_back();
chess[nr][nc].push_back(h);
}
}
//흰색인 경우,
else {
if (chess[nr][nc].size() + dq.size() >= 4) return turn;
while (!dq.empty()) {
Horse h = dq.front();
h.r = nr;
h.c = nc;
horses[h.num] = h;
dq.pop_front();
chess[nr][nc].push_back(h);
}
}
}
}
return -1;
}
int main(int argc, const char * argv[]) {
cin >> N >> K;
for (int r=1; r<=N; r++) {
for (int c=1; c<=N; c++) {
cin >> board[r][c];
}
}
for (int k=1; k<=K; k++) {
horse.num = k;
cin >> horse.r >> horse.c >> horse.d;
chess[horse.r][horse.c].push_back(horse);
horses[k] = horse;
}
cout << play_game() << endl;
return 0;
}이전 풀이
풀이 시간 2시간 49분
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int N, K;
int board[13][13] = {0, };
//chess[r][c] = (r,c)에 놓여있는 말
//chess[r][c][0] = 가장 아래에 있는 말, chess[r][c][1] = 중간에 있는 말, chess[r][c][2] = 가장 위에 있는 말
int chess[13][13][3] = {0, };
//1-우, 2-좌, 3-상, 4-하
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};
struct Piece{
int r;
int c;
int d;
};
Piece piece;
//pieces[i-1] = i번의 말 상태
vector<Piece> pieces;
int turn = 0;
int get_opposite_dir(int dir){
int ndir = -1;
switch(dir){
case 1:
ndir = 2;
break;
case 2:
ndir = 1;
break;
case 3:
ndir = 4;
break;
case 4:
ndir = 3;
break;
}
return ndir;
}
void play_game(){
//움직일 말을 담을 덱
deque<int> move_pieces;
while(true){
turn++;
//1000번 넘는 턴에도 같은 칸에 4개 이상의 말이 있는 경우가 없다면 while문을 빠져나온다
if(turn > 1000){
turn = -1;
break;
}
//말을 순서대로 하나씩 옮긴다
for(int i=0; i<K; i++){
int nr = pieces[i].r + dy[pieces[i].d];
int nc = pieces[i].c + dx[pieces[i].d];
//이동할 위치가 체스판을 벗어나거나, 파란색인 경우
if((nr<1 || nr>N || nc<1 || nc>N) || board[nr][nc] == 2){
//이동 방향을 반대로 바꾼다
pieces[i].d = get_opposite_dir(pieces[i].d);
nr = pieces[i].r + dy[pieces[i].d];
nc = pieces[i].c + dx[pieces[i].d];
//이동하려는 칸이 파란색이거나 체스판을 벗어나는 경우, 이동하지 않는다
if(board[nr][nc] == 2 || (nr<1 || nr>N || nc<1 || nc>N)) continue;
//이동하려는 칸이 흰색인 경우
if(board[nr][nc] == 0){
//이동하려는 칸의 말 개수 구하기
int dest_cnt = 0;
for(int j=0; j<3; j++){
if(chess[nr][nc][j] == 0) break;
dest_cnt++;
}
//이동해야하는 말 구하기
int group_from = -1;
int group_to = -1;
for(int j=0; j<3; j++){
if(chess[pieces[i].r][pieces[i].c][j] == i+1){
group_from = j;
move_pieces.push_back(i+1);
}
else if(chess[pieces[i].r][pieces[i].c][j] != 0 && group_from != -1){
group_to = j;
move_pieces.push_back(chess[pieces[i].r][pieces[i].c][j]);
}
}
if(group_to == -1) group_to = group_from;
int src_cnt = move_pieces.size();
//이동 후 말이 4개 이상 쌓이면, 함수를 종료한다
if(dest_cnt + src_cnt >= 4){
return;
}
//위에 올려져 있는 말과 함께 한 칸 이동
for(int j=dest_cnt; j<dest_cnt+src_cnt; j++){
chess[nr][nc][j] = move_pieces.front();
move_pieces.pop_front();
}
for(int j=group_from; j<=group_to; j++){
chess[pieces[i].r][pieces[i].c][j] = 0;
}
for(int j=dest_cnt; j<dest_cnt+src_cnt; j++){
pieces[chess[nr][nc][j]-1].r = nr;
pieces[chess[nr][nc][j]-1].c = nc;
}
}
//이동하려는 칸이 빨간색인 경우
else if(board[nr][nc] == 1){
//이동하려는 칸의 말 개수 구하기
int dest_cnt = 0;
for(int j=0; j<3; j++){
if(chess[nr][nc][j] == 0) break;
dest_cnt++;
}
//이동해야하는 말 구하기
int group_from = -1;
int group_to = -1;
for(int j=0; j<3; j++){
if(chess[pieces[i].r][pieces[i].c][j] == i+1){
group_from = j;
move_pieces.push_back(i+1);
}
else if(chess[pieces[i].r][pieces[i].c][j] != 0 && group_from != -1){
group_to = j;
move_pieces.push_back(chess[pieces[i].r][pieces[i].c][j]);
}
}
if(group_to == -1) group_to = group_from;
int src_cnt = move_pieces.size();
//이동 후 말이 4개 이상 쌓이면, 함수를 종료한다
if(dest_cnt + src_cnt >= 4){
return;
}
//위에 올려져 있는 말과 함께 한 칸 이동
for(int j=dest_cnt; j<dest_cnt+src_cnt; j++){
chess[nr][nc][j] = move_pieces.back();
move_pieces.pop_back();
}
for(int j=group_from; j<=group_to; j++){
chess[pieces[i].r][pieces[i].c][j] = 0;
}
for(int j=dest_cnt; j<dest_cnt+src_cnt; j++){
pieces[chess[nr][nc][j]-1].r = nr;
pieces[chess[nr][nc][j]-1].c = nc;
}
}
}
//이동할 위치가 흰색인 경우
else if(board[nr][nc] == 0){
//이동하려는 칸의 말 구하기
int dest_cnt = 0;
for(int j=0; j<3; j++){
if(chess[nr][nc][j] == 0) break;
dest_cnt++;
}
//이동해야하는 말 구하기
int group_from = -1;
int group_to = -1;
for(int j=0; j<3; j++){
if(chess[pieces[i].r][pieces[i].c][j] == i+1){
group_from = j;
move_pieces.push_back(i+1);
}
else if(chess[pieces[i].r][pieces[i].c][j] != 0 && group_from != -1){
group_to = j;
move_pieces.push_back(chess[pieces[i].r][pieces[i].c][j]);
}
}
if(group_to == -1) group_to = group_from;
int src_cnt = move_pieces.size();
//이동 후 말이 4개 이상 쌓이면, 함수를 종료한다
if(dest_cnt + src_cnt >= 4){
return;
}
//위에 올려져 있는 말과 함께 한 칸 이동
for(int j=dest_cnt; j<dest_cnt+src_cnt; j++){
chess[nr][nc][j] = move_pieces.front();
move_pieces.pop_front();
}
for(int j=group_from; j<=group_to; j++){
chess[pieces[i].r][pieces[i].c][j] = 0;
}
for(int j=dest_cnt; j<dest_cnt+src_cnt; j++){
pieces[chess[nr][nc][j]-1].r = nr;
pieces[chess[nr][nc][j]-1].c = nc;
}
}
//이동할 위치가 빨간색인 경우
else if(board[nr][nc] == 1){
//이동하려는 칸의 말 개수 구하기
int dest_cnt = 0;
for(int j=0; j<3; j++){
if(chess[nr][nc][j] == 0) break;
dest_cnt++;
}
//이동해야하는 말 구하기
int group_from = -1;
int group_to = -1;
for(int j=0; j<3; j++){
if(chess[pieces[i].r][pieces[i].c][j] == i+1){
group_from = j;
move_pieces.push_back(i+1);
}
else if(chess[pieces[i].r][pieces[i].c][j] != 0 && group_from != -1){
group_to = j;
move_pieces.push_back(chess[pieces[i].r][pieces[i].c][j]);
}
}
if(group_to == -1) group_to = group_from;
int src_cnt = move_pieces.size();
//이동 후 말이 4개 이상 쌓이면, 함수를 종료한다
if(dest_cnt + src_cnt >= 4){
return;
}
//위에 올려져 있는 말과 함께 한 칸 이동
for(int j=dest_cnt; j<dest_cnt+src_cnt; j++){
chess[nr][nc][j] = move_pieces.back();
move_pieces.pop_back();
}
for(int j=group_from; j<=group_to; j++){
chess[pieces[i].r][pieces[i].c][j] = 0;
}
for(int j=dest_cnt; j<dest_cnt+src_cnt; j++){
pieces[chess[nr][nc][j]-1].r = nr;
pieces[chess[nr][nc][j]-1].c = nc;
}
}
}
}
}
int main(int argc, const char * argv[]) {
cin >> N >> K;
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
cin >> board[i][j];
}
}
for(int i=1; i<=K; i++){
cin >> piece.r >> piece.c >> piece.d;
pieces.push_back(piece);
//체스판 위에 말을 놓는다. 이때, 같은 칸에 위치하는 말은 입력으로 주어지지 않으므로 가장 맨 아래인 0번째 인덱스에 말을 놓는다
chess[piece.r][piece.c][0] = i;
}
play_game();
cout << turn << endl;
return 0;
}
//시간복잡도 = O(n), 공간복잡도 = O(n)
728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 17825 주사위 윷놀이 C++ (0) | 2021.10.06 |
|---|---|
| 백준 7453 합이 0인 네 정수 Python 3 (0) | 2021.10.05 |
| 백준 17143 낚시왕 C++ (0) | 2021.10.05 |
| 백준 16472 고냥이 Python3 (0) | 2021.10.04 |
| 백준 3649 로봇 프로젝트 Python3 (0) | 2021.10.04 |