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

문제

SWEA 모의 SW 역량테스트 - 5650 핀볼 게임

SW Expert Academy

 

---

문제 풀이

접근 방식

핀볼 게임판의 구성요소

핀볼 게임판에는 위의 이미지와 같이 블록 5종류와 웜홀, 블랙홀이 존재한다.

문제의 조건에 맞게 코드를 짜면 되는 시뮬레이션 문제였는데, 조건들이 많아서 까다로운 문제였다.

 

우선 게임판을 입력받으며, 웜홀의 위치를 따로 저장해주었다.

(처음에는 위치를 저장해주지 않고, 웜홀을 만날 때마다 이중 for문으로 탐색하는 방식으로 구현했었는데,

위치를 vector나 map으로 따로 저장해주는 게 더 빠르다.)

그리고 go 함수에 모든 위치와 모든 방향을 넣어 탐색하여, 해당 게임판에서 얻을 수 있는 점수의 최댓값을 구해주었다.

 

go 함수는 아래와 같이 구현하였다.

void go(int x, int y, int d) {
    nx = x, ny = y;
    cnt = 0;
    bool first = true;
    bool black = false;
    while (1) {
        if (black || (!first && x == nx && y == ny)) break;
        first = false;
        nx += dir[d][0];
        ny += dir[d][1];
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
            cnt *= 2;
            cnt++;
            break;
        }
        switch (map[nx][ny]){
        case -1:
            black = true;
            break;
        case 0:
            break;
        case 1:
        case 2:
        case 3:
        case 4:
            d = change(map[nx][ny], d);
            cnt++;
            break;
        case 5:
            cnt *= 2;
            cnt++;
            black = true;
            break;
        default:
            int num = map[nx][ny] - 6;
            if (wormhole[num][0].first == nx && wormhole[num][0].second == ny) {
                nx = wormhole[num][1].first;
                ny = wormhole[num][1].second;
            }
            else {
                nx = wormhole[num][0].first;
                ny = wormhole[num][0].second;
            }
            break;
        }
    }
    if (MAX < cnt)
        MAX = cnt;
}

 

위의 코드에서 while문을 나가는 조건은 블랙홀을 만났을 때, 처음 위치로 돌아왔을 때이다.

처음 while문을 수행할 때는 nx, ny가 처음 위치일 수밖에 없기 때문에,

first 변수를 통해 처음 수행할 때에는 상관없도록 구현하였다.

(이 부분은 do ~ while 문으로 구현하면 더 간단할 거 같다.)

 

주어진 방향에 따라 다음칸으로 nx와 ny의 값을 바꿔준 후, 게임판의 범위를 벗어나는 지를 먼저 확인하였다.

게임판을 벗어나려고 하면 방향이 반대 방향으로 바뀌고 점수를 1점 얻는다.

처음에는 이렇게 문제에 주어진대로 구현하였으나, 이렇게 대각선이 아닌 평평한 벽에 부딪히게 되면

원래 왔던 길을 되돌아가게 된다는 것을 알게 되어서 코드를 위와 같이 구현하게 되었다.

즉, 원래 왔던 길을 되돌아가기 때문에 cnt의 값을 2배로 바꿔주고,

벽에 부딪혔기 때문에 cnt++를 해주면 그게 최종적인 점수가 되는 것이다.

 

게임판의 범위를 벗어나지 않는 경우에는 switch 문을 통해 해당 칸의 숫자에 따라 다른 처리를 해주었다.

해당 칸의 숫자가 -1인 경우에는 블랙홀을 만난 것이기 때문에 black을 true로 바꿔주어 while문을 종료시켜주었다.

0인 경우는 변화 없이 다음 칸으로의 이동을 수행하도록 한다.

 

해당 칸의 숫자가 1~4인 경우는 삼각형의 블록을 만난 경우이다.

이 때는 change 함수를 통해 방향을 변경해주었다.

블록 1을 만난 경우에는 0은 2, 1은 3, 2는 1, 3은 0으로 방향이 바뀌게 된다. (0 : 상, 1 : 우, 2 : 하, 3 : 좌)

즉, 원래의 값에서 +2, +2, -1, +1으로 값이 바뀐다.

블록 2의 경우에는 원래의 값에서 +1, +2, +2, -1으로 값이 바뀐다.

결국 같은 삼각형의 모양을 90도씩 회전시킨 것이기 때문에 이렇게 2, 2, -1, 1이 반복된다는 특징이 나타난다.

그래서 이러한 특징을 반영하여 change 함수를 구현하였다.

(여기서도 평평한 부분에 부딪히면 바로 점수를 2배 +1로 값으로 바꾸고 while문을 나가면 되는데,

기존의 코드에서 바꾸느라 고려하지 못했다.)

 

해당 칸의 숫자가 5인 경우는 평평한 벽에 부딪힌 경우로,

게임판을 벗어났을 때와 마찬가지로 점수를 2배 + 1의 값으로 바꿔주고,

black을 true로 바꿔주어 while문을 나갈 수 있게 구현하였다.

5 이상인 경우에는 웜홀을 만난 것이므로, 같은 번호의 웜홀 위치로 이동시켜주었다.

 

while문에서 나오면 MAX와 cnt를 비교하여 최종적인 최댓값을 구할 수 있도록 구현하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
int N, MAX, x, y, nx, ny, cnt;
int map[100][100];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
vector<pair<int, int>> wormhole[5];

int change(int a, int d) {
    int new_dir[4] = { 2,2,-1,1 };
    d = (d + new_dir[(d + 5 - a) % 4] + 4) % 4;
    return d;
}
 
void go(int x, int y, int d) {
    nx = x, ny = y;
    cnt = 0;
    bool first = true;
    bool black = false;
    while (1) {
        if (black || (!first && x == nx && y == ny)) break;
        first = false;
        nx += dir[d][0];
        ny += dir[d][1];
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
            cnt *= 2;
            cnt++;
            break;
        }
        switch (map[nx][ny]){
        case -1:
            black = true;
            break;
        case 0:
            break;
        case 1:
        case 2:
        case 3:
        case 4:
            d = change(map[nx][ny], d);
            cnt++;
            break;
        case 5:
            cnt *= 2;
            cnt++;
            black = true;
            break;
        default:
            int num = map[nx][ny] - 6;
            if (wormhole[num][0].first == nx && wormhole[num][0].second == ny) {
                nx = wormhole[num][1].first;
                ny = wormhole[num][1].second;
            }
            else {
                nx = wormhole[num][0].first;
                ny = wormhole[num][0].second;
            }
            break;
        }
    }
    if (MAX < cnt)
        MAX = cnt;
}
 
int main(int argc, char** argv)
{
    int test_case, i, j, k;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        // 입력 받기
        cin >> N;
        memset(map, 0, sizeof(map));
        for (int i = 0; i < 5; i++)
            wormhole[i].clear();        
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                cin >> map[i][j];
                // 웜홀 위치 저장
                if(map[i][j] > 5) {
                    wormhole[map[i][j] - 6].push_back({i, j});
                }
            }
        }
 
        // 핀볼 게임
        MAX = 0;
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                for (k = 0; k < 4; k++)  {
                    if(map[i][j] == 0)
                        go(i, j, k);
                }
            }
        }
        cout << "#" << test_case << " " << MAX << '\n';
    }
    return 0;
}

실행 결과

실행 결과 : Pass (168ms)