[SWEA][C++] 5650 핀볼게임

[SWEA][C++] 5650 핀볼게임

문제

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

풀이

0인 모든 칸에서 핀볼을 던지고 탐색을 했습니다. 6개의 경우를 나눠서 다음 칸으로 이동할 수 있게 구현했어요.

다음 좌표의 값에 따라 여섯개의 경우는 이렇게 나뉩니다.

1. 벽을 만나면 무조건 오던 길을 다시 되돌아가기 때문에 (n*2)+1로 값을 구하고 return

2. 처음 시작한 위치와 값이 같은 경우 : max값 구해서 return

3. 0인 경우 : 방향 유지해서 이동

4. 1~5 값인 경우 : 방향 바꾸고 점수 더해서 이동

5. 6~10 값인 경우 : 웜홀, 이동할 웜홀 좌표를 찾은 뒤 바꿔서 이동

이렇게 구현하였습니다. 방향의 경우 헷갈려서 하나하나 그린 뒤 구현했습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n;
int map[101][101];
int res = 0;
vector<pair<int,int>> hole[5];
vector<pair<int, int>> start;
int dx[] = { -1,1,0,0 };//상하좌우
int dy[] = { 0,0,-1,1 };
int start_x, start_y;
int CheckDir(int x, int y, int block, int dir) {
    if (block == 1) {
        if (dir == 0) return 1;
        if (dir == 1) return 3;
        if (dir == 2) return 0;
        if (dir == 3) return 2;
    }
    else if (block == 2) {
        if (dir == 0) return 3;
        if (dir == 1) return 0;
        if (dir == 2) return 1;
        if (dir == 3) return 2;
    }
    else if (block == 3) {
        if (dir == 0) return 2;
        if (dir == 1) return 0;
        if (dir == 2) return 3;
        if (dir == 3) return 1;
    }
    else if (block == 4) {
        if (dir == 0) return 1;
        if (dir == 1) return 2;
        if (dir == 2) return 3;
        if (dir == 3) return 0;
    }
    else if (block == 5) {
        if (dir == 0) return 1;
        if (dir == 1) return 0;
        if (dir == 2) return 3;
        if (dir == 3) return 2;
    }

    return dir;
}
void DFS(int x, int y, int dir, int score) {
    int nx = x + dx[dir];
    int ny = y + dy[dir];

    //벽만나면 (n*2)+1
    if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
        int s = (score * 2) + 1;
        if (res < s) res = s;
        return;
    }
    //있던 곳 되돌아오기
    else if (nx == start_x && ny == start_y) {
        if (res < score) res = score;
        return;
    }
    //방향 유지 다음 DFS
    else if (map[nx][ny] == 0) {
        DFS(nx, ny, dir, score);
    }
    //블록, 점수 획득, 방향 바꾸기
    else if (map[nx][ny] > 0 && map[nx][ny] < 6) {
        dir = CheckDir(nx, ny, map[nx][ny], dir);
        DFS(nx, ny, dir, score + 1);
    }
    //웜홀, 좌표바꿔서 다음턴
    else if (map[nx][ny] > 5 && map[nx][ny] < 11) {
        int _x = hole[map[nx][ny]-6].at(0).first;
        int _y = hole[map[nx][ny]-6].at(0).second;
        if (_x == nx && _y == ny) {
            _x = hole[map[nx][ny]-6].at(1).first;
            _y = hole[map[nx][ny]-6].at(1).second;
        }
        DFS(_x, _y, dir, score);
    }
    //블랙홀
    else if (map[nx][ny] == -1) {
        if (res < score) res = score;
        return;
    }
}
int main() {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        memset(map, 0, sizeof(map));
        res = 0;
        for (int i = 0; i < 5; i++) {
            hole[i].clear();
        }
        start.clear();
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &map[i][j]);
                //웜홀
                if (map[i][j] >= 6 && map[i][j] <= 10) {
                    int num = map[i][j] - 6;
                    hole[num].push_back(make_pair(i, j));
                }
                else if (map[i][j] == 0) {
                    start.push_back(make_pair(i, j));
                }
            }
        }
        for (int i = 0; i < start.size(); i++) {
            for (int j = 0; j < 4; j++) { //dir
                start_x = start[i].first;
                start_y = start[i].second;
                DFS(start_x, start_y, j, 0);
            }
        }
        printf("#%d %d\n", t, res);
    }

}