[C++] SWEA 5650 - 핀볼 게임(2)

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo 

SW Expert Academy

<풀이>

1. 게임판을 입력받는다.

2. 핀볼을 굴려서 얻을 수 있는 점수의 최댓값을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 게임판의 0인 곳에서 4방향으로 핀볼을 모두 굴려봐야합니다. 따라서, 저는 브루트포스를 선택했습니다.

 

2. 시뮬레이션 구현하기

=> 조건에 맞게 정확하게 구현하기만 하면 되는 시뮬레이션입니다. 구현에 정답은 없지만, 저가 좀 더 쉽게 구현하기 위해 만들었던 장치들을 소개하겠습니다.

(1) 게임판을 102x102로 만든다.

게임판을 102x102로 만들면, 벽을 처리하는 구현이 간단해집니다. 왜냐하면 벽도 하나의 공간으로 생각할 수 있기 때문입니다. 

(2) 게임판 테두리를 5번 블록으로 채운다.

결국 게임판 외곽의 벽들은 핀볼의 방향을 반대방향으로 바꾸는 5번 블록과 성질이 같습니다. 게임판 외곽을 5번 블록으로 채우면 벽도 블록으로 생각할 수 있으므로 구현이 간단해집니다.

(3) 만나는 블록과 핀볼의 방향에 따라 바뀌는 핀볼 방향을 미리 2차원 배열로 구현한다.

미리 만들어 놓으면, 핀볼이 바뀌는 방향을 쉽게 구할 수 있습니다.

 

3. 최적화할 수 있을까?

=> 조금 더 깊게 생각해보겠습니다. 핀볼의 방향이 반대로 바뀌면, 다시 왔던 길을 그대로 돌아서 갑니다. 이 말은 곧 무조건 시작지점으로 돌아가게 되어있고, 부딪혔던 벽도 다시 부딪히게 된다는 뜻입니다. 따라서 핀볼의 방향이 반대로 될 때, 점수는 (지금까지 점수 x 2 + 1)이되고 시뮬레이션을 종료할 수 있습니다. 위 방법으로 연산 횟수를 조금이나마 줄일 수 있습니다.

 

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int block[6][4] = { //-1은 왔던 방향의 반대로 가는 경우
    {0,0,0,0},
    {-1,-1,1,0},
    {1,-1,-1,2},
    {3,2,-1,-1},
    {-1,0,3,-1},
    {-1,-1,-1,-1}
};
 
int N;
int map[102][102];
vector<pos> wormhole[11];
int answer;
 
bool isStart(pos p, pos start) {
    if (p.x == start.x && p.y == start.y) return true;
    return false;
}
 
bool isBlackhole(pos p) {
    if (map[p.x][p.y] == -1) return true;
    return false;
}
 
bool isBlock(pos p) {
    if (1 <= map[p.x][p.y] && map[p.x][p.y] <= 5) return true;
    return false;
}
 
bool isEmptySpace(pos p) {
    if (map[p.x][p.y] == 0) return true;
    return false;
}
 
bool isWormhole(pos p) {
    if (6 <= map[p.x][p.y] && map[p.x][p.y] <= 10) return true;
    return false;
}
 
pos getPairWormhole(int num, pos p) {
    if (wormhole[num][0].x == p.x && wormhole[num][0].y == p.y) return wormhole[num][1];
    else return wormhole[num][0];
}
 
int simulation(pos start, int startDir) {
    int score = 0;
    pos p = start; 
    int dir = startDir;
    while (true) {
        p.x += dx[dir], p.y += dy[dir];
        //시작지점 or 블랙홀
        if (isStart(p, start) || isBlackhole(p)) break;
        //블록
        else if (isBlock(p)) {
            int blockNum = map[p.x][p.y];
            dir = block[blockNum][dir];
            if (dir == -1) {
                score = (score * 2) + 1;
                break;
            }
            else score++;
        }
        //웜홀
        else if (isWormhole(p)) {
            p = getPairWormhole(map[p.x][p.y], p);
        }
    }
    return score;
}
 
void solution() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (isEmptySpace({ i,j })) {
                for (int k = 0; k < 4; k++) {
                    answer = max(answer, simulation({ i, j }, k));
                }
            }
        }
    }
}
 
int main() {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        memset(map, 0, sizeof(map));
        for (int i = 6; i <= 10; i++) wormhole[i].clear();
        answer = 0;
 
        //입력
        cin >> N;
        for (int i = 1; i <= N; i++) {
            map[i][0] = 5, map[i][N + 1] = 5, map[0][i] = 5, map[N + 1][i] = 5;
            for (int j = 1; j <= N; j++) {
                cin >> map[i][j];
                if (isWormhole({ i,j })) wormhole[map[i][j]].push_back({ i,j });
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

브루트포스와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.