SWEA5650 [모의 SW 역량테스트] 핀볼 게임 C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo&categoryId=AWXRF8s6ezEDFAUo&categoryType=CODE&problemTitle=모의&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2 

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA5650.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA5650
//
//  Created by Hwayeon on 2021/10/18.
//

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

int N;
int board[101][101] = {0, };
int block[6][4] = {{0,0,0,0}, {2,3,1,0}, {1,3,0,2}, {3,2,0,1}, {2,0,3,1}, {2,3,0,1}};
int warmhole_x[11][2] = {-1, };
int warmhole_y[11][2] = {-1, };

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

struct Pinball{
    int sx;
    int sy;
    int x;
    int y;
    int d;
};
Pinball ball;
int max_score = 0;

bool move_ball(Pinball& ball, int& score){
    int nx = ball.x + dx[ball.d];
    int ny = ball.y + dy[ball.d];
    int nd = ball.d;

    while((nx<0 || nx>=N || ny<0 || ny>=N) || !(board[ny][nx] == -1 || (board[ny][nx] >= 6 && board[ny][nx] <= 10) || (nx == ball.sx && ny == ball.sy))){
        //벽에 부딪힌 경우,
        if(nx<0 || nx>=N || ny<0 || ny>=N){
            nx -= dx[nd];
            ny -= dy[nd];
            nd = block[5][nd];
            score++;
        }
        //블록에 부딪힌 경우, 계속 부딪힐 수 있음!!!
        else if(board[ny][nx] >= 1 && board[ny][nx] <= 5){
            nd = block[board[ny][nx]][nd];
            nx += dx[nd];
            ny += dy[nd];
            score++;
        }
        else{
            nx += dx[nd];
            ny += dy[nd];
        }
    }
    //블랙홀에 빠졌거나 시작 위치로 돌아온 경우, 게임 종료
    if(board[ny][nx] == -1 || (nx == ball.sx && ny == ball.sy)){
        if(score > max_score) max_score = score;
        return false;
    }
    //웜홀에 빠진 경우, 다른 웜홀로 핀볼 위치 변경
    for(int i=0; i<2; i++){
        if(nx == warmhole_x[board[ny][nx]][i] && ny == warmhole_y[board[ny][nx]][i]) continue;
        ball.x = warmhole_x[board[ny][nx]][i];
        ball.y = warmhole_y[board[ny][nx]][i];
        ball.d = nd;
        break;
    }
    return true;
}

void play_pinball(){
    queue<pair<Pinball, int>> q;
    for(int y=0; y<N; y++){
        for(int x=0; x<N; x++){
            if(board[y][x] != 0) continue;
            for(int d=0; d<4; d++){
                ball.sx = x;
                ball.sy = y;
                ball.x = x;
                ball.y = y;
                ball.d = d;
                q.push({ball, 0});
            }
        }
    }
    while(!q.empty()){
        ball = q.front().first;
        int now_score = q.front().second;
        q.pop();
        if(move_ball(ball, now_score)){
            q.push({ball, now_score});
        }
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        max_score = 0;
        memset(warmhole_x, -1, sizeof(warmhole_x));
        memset(warmhole_y, -1, sizeof(warmhole_y));
        cin >> N;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                cin >> board[y][x];
                //웜홀인 경우,
                if(board[y][x] >=6 && board[y][x] <= 10){
                    for(int i=0; i<2; i++){
                        if(warmhole_x[board[y][x]][i] == -1){
                            warmhole_x[board[y][x]][i] = x;
                            warmhole_y[board[y][x]][i] = y;
                            break;
                        }
                    }
                }
            }
        }
        play_pinball();
        cout << "#" << test_case << " " << max_score << endl;
    }
    return 0;
}

---

풀이 과정

풀이 시간 2시간 11분

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

int N;
int board[101][101] = {0, };

//블록 1~5에 부딪혔을 때 바뀌는 방향을 나타내는 배열
//block[i][d] = d 방향으로 블록 i에 부딪혔을 때 바뀌어야 하는 방향
int block[6][4] = {{0,0,0,0}, {2,3,1,0}, {1,3,0,2}, {3,2,0,1}, {2,0,3,1}, {2,3,0,1}};

//웜홀의 위치를 나타내는 배열
//두 개의 i번 웜홀의 위치 = (warmhole_x[i][0], warmhole_y[i][0]), (warmhole_x[i][1], warmhole_y[i][1])
int warmhole_x[11][2] = {-1, };
int warmhole_y[11][2] = {-1, };

//0-상, 1-우, 2-하, 3-좌
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

struct Pinball{
	//핀볼의 시작 위치
    int sx;
    int sy;
    //현재 핀볼의 위치
    int x;
    int y;
    //핀볼의 방향
    int d;
};
Pinball ball;

int max_score = 0;

bool move_ball(Pinball& ball, int& score){
    int nx = ball.x + dx[ball.d];
    int ny = ball.y + dy[ball.d];
    int nd = ball.d;

	//핀볼이 블랙홀에 빠지거나, 시작 위치로 돌아갔거나, 웜홀에 빠진 경우 while문에서 빠져나온다
    //핀볼이 벽에 부딪힌 경우는 while문을 계속 진행한다
    while((nx<0 || nx>=N || ny<0 || ny>=N) || !(board[ny][nx] == -1 || (board[ny][nx] >= 6 && board[ny][nx] <= 10) || (nx == ball.sx && ny == ball.sy))){
        //벽에 부딪힌 경우,
        if(nx<0 || nx>=N || ny<0 || ny>=N){
        	//이전 위치로 한 칸 돌아가고, 방향을 반대로 바꾼다
            nx -= dx[nd];
            ny -= dy[nd];
            nd = block[5][nd];
            //점수 1 카운팅
            score++;
        }
        //블록에 부딪힌 경우,
        else if(board[ny][nx] >= 1 && board[ny][nx] <= 5){
        	//방향을 바꾸고, 바뀐 방향으로 1칸 이동한다
            nd = block[board[ny][nx]][nd];
            nx += dx[nd];
            ny += dy[nd];
            //점수 1 카운팅
            score++;
        }
        //벽이나 블록에 부딪히지 않은 경우, nd방향으로 1칸 이동한다
        else{
            nx += dx[nd];
            ny += dy[nd];
        }
    }
    
    //블랙홀에 빠졌거나 시작 위치로 돌아온 경우, 게임 종료
    if(board[ny][nx] == -1 || (nx == ball.sx && ny == ball.sy)){
    	//max_score 값을 갱신하고, false를 반환하며 함수 종료
        if(score > max_score) max_score = score;
        return false;
    }
    
    //웜홀에 빠진 경우, 같은 번호의 다른 위치에 있는 웜홀로 핀볼 위치 변경 후, true를 반환하며 함수 종료
    for(int i=0; i<2; i++){
        if(nx == warmhole_x[board[ny][nx]][i] && ny == warmhole_y[board[ny][nx]][i]) continue;
        ball.x = warmhole_x[board[ny][nx]][i];
        ball.y = warmhole_y[board[ny][nx]][i];
        ball.d = nd;
        break;
    }
    return true;
}

void play_pinball(){
	//핀볼의 상태와 점수를 저장하는 큐
    queue<pair<Pinball, int>> q;
    
    //핀볼의 시작 위치가 될 수 있는 위치를 찾는다 -> O(N^2)
    for(int y=0; y<N; y++){
        for(int x=0; x<N; x++){
        	//빈 칸이 아니면, 핀볼의 시작 위치가 될 수 없다
            if(board[y][x] != 0) continue;
            
			//핀볼의 방향을 정한다
            for(int d=0; d<4; d++){
                ball.sx = x;
                ball.sy = y;
                ball.x = x;
                ball.y = y;
                ball.d = d;
                //(x, y) 시작 위치에서 d 방향으로 핀볼 게임을 시작하기 위해 q에 담는다
                q.push({ball, 0});
            }
        }
    }
    
    //모든 경우에 대해 핀볼 게임을 한다 -> O(N^4)
    while(!q.empty()){
    	//현재 핀볼의 상태
        ball = q.front().first;
        //현재 점수
        int now_score = q.front().second;
        q.pop();
        
        //핀볼을 움직인다
        //move_ball(ball, now_score) == false -> 핀볼이 시작 위치로 다시 돌아갔거나 블랙홀에 빠진 경우, 큐에 삽입하지 않고 핀볼 게임을 끝낸다 
        //move_ball(ball, now_score) == true -> 핀볼이 웜홀에 빠진 경우, 같은 번호의 웜홀의 다른 위치에서 핀볼 게임을 이어가기 위해 큐에 삽입한다
        if(move_ball(ball, now_score)){
            q.push({ball, now_score});
        }
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
    	//최대 점수와 웜홀의 위치를 담는 배열 초기화
        max_score = 0;
        memset(warmhole_x, -1, sizeof(warmhole_x));
        memset(warmhole_y, -1, sizeof(warmhole_y));
        
        cin >> N;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                cin >> board[y][x];
                //웜홀인 경우, 위치를 저장한다
                if(board[y][x] >=6 && board[y][x] <= 10){
                    for(int i=0; i<2; i++){
                        if(warmhole_x[board[y][x]][i] == -1){
                            warmhole_x[board[y][x]][i] = x;
                            warmhole_y[board[y][x]][i] = y;
                            break;
                        }
                    }
                }
            }
        }
        play_pinball();
        cout << "#" << test_case << " " << max_score << endl;
    }
    return 0;
}
//시간복잡도 = O(N^4), 공간복잡도 = O(N^2)