← All Articles

[SW Expert Academy] 5650. 핀볼 게임

Posted on

문제 :

민기는 핀볼 게임을 개발 중에 있다. 핀볼게임은 N x N 크기의 핀볼 게임판에 정사각형 블록과 4가지 형태의 삼각형 블록들이 섞여 있고, 여기에 추가적으로 웜홀과 블랙홀이 존재한다. 핀볼게임의 게임판의 하나의 예는 아래 [그림1]과 같다.

image

각 블록들은 일정한 번호로 주어지는데, 블록들의 번호와 모양은 아래 [그림2]와 같다.

image

웜홀과 블랙홀은 각각 아래 [그림3]의 번호로 주어진다.

image

게임판 위에서는 작은 핀볼 하나가 상, 하, 좌, 우 중 한 방향으로 움직인다.

image

핀볼은 블록이나 웜홀 또는 블랙홀을 만나지 않는 한 현재 방향을 유지하면서 계속 직진하며,

블록의 수평면이나 수직면을 만날 경우 방향을 바꿔 반대 방향으로 돌아오고, 경사면을 만날 경우에는 직각으로 진행 방향이 꺾이게 된다.

image

또한 핀볼은 벽을 만날 경우에도 반대 방향으로 돌아온다. 아래의 그림과 같이 핀볼이 왼쪽으로 움직이다 벽을 만나면 반대 방향으로 다시 돌아오게 된다.

image

핀볼이 웜홀에 빠지면 동일한 숫자를 가진 다른 반대편 웜홀로 빠져 나오게 되며 진행방향은 그대로 유지된다. (웜홀은 반드시 쌍으로 주어지며, 입력에서는 6 이상 10 이하의 숫자로 표시된다.)

image

핀볼이 블랙홀을 만나면, 핀볼이 사라지게 되어 게임은 끝나게 된다.

게임은 핀볼이 출발 위치로 돌아오거나, 블랙홀에 빠질 때 끝나게 되며, 점수는 벽이나 블록에 부딪힌 횟수가 된다. (웜홀을 통과하는 것은 점수에 포함되지 않는다.)

블랙홀에 빠져서 게임이 끝나더라도, 벽이나 블록에 부딪혀 획득한 점수는 남아있게 된다.

게임판 위에서 출발 위치와 진행 방향을 임의로 선정가능 할 때,

▶ 게임에서 얻을 수 있는 점수의 최댓값을 구하여라!

단, 블록, 웜홀 또는 블랙홀이 있는 위치에서는 출발할 수 없다.


[ 제약 사항 ]

  1. 게임판의 크기는 정사각형으로 주어지며, 한 변의 길이 N 은 5 이상 100 이하이다. (5 ≤ N ≤ 100)
  2. 웜홀은 게임판 내에서 숫자 6 ~ 10으로 주어진다.
  3. 블랙홀은 게임판 내에서 숫자 -1 로 주어진다.
  4. 게임판에서 웜홀 또는 블랙홀이 존재하지 않는 경우도 있다.
  5. 웜홀이 있는 경우 반드시 쌍(pair)으로 존재하며, 웜홀이 주어지는 경우 최대 5쌍 존재한다.
  6. 웜홀을 통과한 핀볼은 동일한 숫자를 가진 반대편 웜홀로 이동하게 되며, 이때 진행방향은 그대로 유지된다.
  7. 블랙홀은 최대 5개가 주어진다.

입력 :

입력의 가장 첫 줄에는 총 테스트 케이스의 개수 T가 주어지며, 그 다음 줄부터 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 N이 주어지고, 다음 N줄에 걸쳐서 핀볼 게임판의 모양이 주어진다.

게임판의 모양은 -1 이상 10 이하의 정수로 주어지며, 각 숫자는 한 칸씩 띄어져서 주어진다. 숫자에 따른 의미는 다음과 같다


출력 :

테스트 케이스 t에 대한 결과는 “#t”를 찍고, 한 칸 띄고 정답을 출력한다.

(단, t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)



풀이 :

삼성 SW 역량 테스트에 대표적으로 출제될만한 시뮬레이션(구현) 문제 유형인 듯 하다.

공의 시작 위치, 시작 방향에 따라 벽, 블록에 가장 많이 부딪히는 횟수를 구하는 문제이다.

문제 해결에는 작은 몇 가지의 key point가 있다.


[ KEY POINT ]

  • 문제에서 map에 존재할 수 있는 칸의 종류에는 빈칸(0), 블록(1 ~ 5), 웜홀(6 ~ 10), 블랙홀(-1) 4가지가 있다. 이 중에서도 블록과 웜홀을 잘 구현해야 문제를 쉽게 해결할 수 있다.
  • 블록의 경우 총 5가지의 블록을 상, 하, 좌, 우 4가지 방향으로 들어왔을 경우 나갈 때 바뀌는 방향을 저장하는 changedir[6][4] 배열을 만들어 효과적으로 방향을 저장해두고 사용한다.
  • 웜홀의 경우 벡터를 사용하여 위치 정보를 관리한다. 웜홀의 경우 쌍을 지어 총 5가지 종류가 존재하는데 이를 2차원 벡터에 관리하여 웜홀에 도착했을 시 다른 한쪽의 출구 웜홀 정보에 접근할 수 있도록 구현한다.
  • 그리고 가장 중요한 key point는 구슬의 경로를 탐색할 때 도착한 칸이 빈 칸일 경우, 블록일 경우, 벽일 경우, 블랙홀일 경우, 웜홀일 경우를 잘 분류화하여 구현하는 것이다. 정확하게 분류하여 각 경우의 수를 순서를 맞추어 잘 구현해야 에러 케이스나, 비효율적인 코드 구현을 방지할 수 있다.


코드 :

코드 보기/접기 
#include<iostream>
#include <vector>
#include <utility>
#include <algorithm>

#define pii pair<int, int>

using namespace std;
vector<vector<pii>> wormvec(11);
int n, map[100][100], di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
int changedir[6][4] = {{0, 0, 0, 0,},
                       {2, 0, 3, 1},
                       {2, 3, 1, 0},
                       {1, 3, 0, 2},
                       {3, 2, 0, 1},
                       {2, 3, 0, 1}};

void init() {
    for (int i = 6; i < 11; i++)
        wormvec[i].clear();
}

int pathNavigation(int startx, int starty, int curdir) {
    int curx = startx, cury = starty, score = 0;

    while (true) {
        int cmpx = curx + di[curdir], cmpy = cury + dj[curdir];

        if (cmpx < 0 || cmpx >= n || cmpy < 0 || cmpy >= n) {    // 벽에 부딪혔을 시
            score++;
            curx = cmpx;
            cury = cmpy;
            curdir = (curdir + 2) % 4;
            continue;
        }

        int curnum = map[cmpx][cmpy];
        if (curnum == -1) return score;   // 블랙홀 도착 시
        if (5 < curnum) {   // 웜홀 도착 시
            if (wormvec[curnum][0].first != cmpx || wormvec[curnum][0].second != cmpy) {
                curx = wormvec[curnum][0].first;
                cury = wormvec[curnum][0].second;
            } else {
                curx = wormvec[curnum][1].first;
                cury = wormvec[curnum][1].second;
            }
            continue;
        }
        if (0 < curnum && curnum < 6) {   // 블록 도착 시
            curdir = changedir[curnum][curdir];
            score++;
        }
        curx = cmpx;
        cury = cmpy;

        if (curx == startx && cury == starty) return score; // 출발 위치로 복귀 시
    }
}

int testCase() {
    int input, maxscore = 0;

    cin >> n;
    init();

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            cin >> input;
            map[i][j] = input;
            if (input > 5) wormvec[input].push_back(pii(i, j));
        }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!map[i][j])
                for (int k = 0; k < 4; k++)
                    maxscore = max(maxscore, pathNavigation(i, j, k));

    return maxscore;
}

int main(int argc, char **argv) {
    int test_case, T;

    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
        cout << '#' << test_case << ' ' << testCase() << '\n';

    return 0;
}


AlgorithmalgorithmSW ExpertC++