[SW Expert 5650] 핀볼 게임

#문제

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

#풀이

문제를 본 순간, 아....딱 재귀호출을 이용하여 풀면 딱 답이 나오겠다...라고 생각을 하고 풀게 되었습니다.

일단, 맵의 경우 부딪쳤을 때를 대비하여 양옆과 위, 아래에 1씩 추가를 해주었습니다. 

해당 위치에 들어가면, 벽에 부딪친걸로 판단하며 다시 되돌아오도록 하였습니다.

빠져나가는 조건으로 블랙홀과 시작지점이 있기 때문에 따로 저장을 하게 되었습니다.

특히 블랙홀의 경우, 나중에 쉽게 찾기 위해 set으로 저장하였고,

시작지점은 여러개의 시작 지점을 저장, 이를 탈출구로 인식하기 위해 하나씩 빼어 썻습니다.

다음 지점이 블럭일 경우에도 함수를 만들어 다음 방향을 처리하게 해두었습니다.

블럭일 경우와 벽인 경우에 하나씩 점수를 추가해 나갔고 해당 점수들은 빠져나가는 조건에 해당되면 횟수들을 비교하여 최대인 것을 뽑아냅니다.

이렇게 해서 재귀로 만들었더니...제출 후에 .. 런타임 에러... 총 50개의 테스트 케이스중 49개의 테트스 케이스만 맞았습니다.

또한 평소에 배열의 인덱스 문제로 인한 런타임 에러가 많았기 때문에 이번에도 그러겠지하며 코드만 계속보았지만... 그것도 아니였습니다.

여러 질문들을 검색해본 결과 함수를 호출하면서 쌓이게되는 스택이 너무나도 많게 되면 오버플로우가 발생되어 런타임 에러를 발생시키는 문제 였습니다.

그리하여 한칸 한칸 가는 것도 줄여 연속된 0일때는 건너 뛰어 재귀호출을 하는 형식으로도 하였지만,, 소용없었습니다.

결국, 모든 것을 바꾸기로 하였고, 재귀호출 대신 while문을 사용하기로 하였습니다. 

모든 스타팅 포인트를 저장하고 , 그 포인트에서 갈수 있는 방향을 돌며 카운트를 세는 형식으로 위에 재귀로 하였을 때와 방법은 비슷하였습니다. 

처음부터 틀을 너무 재귀로만 잡는 것 같습니다.

실제 시험에서는 맞았는지 안알려주기 때문에 더욱더 조심해야 될것 같습니다....

#코드

#include <iostream>
#include <vector>
#include <cstring>
#include <set>
using namespace std;
 
int N;
int gameMap[102][102];
vector<pair<int, int>> starting;
set<pair<int, int>> blackHole;
vector<pair<int, int>> wormHole[6];
int ans = 0;
 
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
void initGame(){
    for(int i = 0; i < 102; i++){
        for(int j = 0; j < 102; j++){
            gameMap[i][j] = 0;
        }
    }
    starting.clear();
    blackHole.clear();
    for(int i = 0; i <= 5; i++)
        wormHole[i].clear();
    ans = 0;
}
 
int HitTheWall(int dir){
    if(dir == 0) return 1;
    else if(dir == 1) return 0;
    else if(dir == 2) return 3;
    else return 2;
}
 
int HitTheBlock(int kind, int dir){
    if(kind == 1){
        if(dir == 0) return 1;
        else if(dir == 1) return 3;
        else if(dir == 2) return 0;
        else return 2;
    }else if(kind == 2){
        if(dir == 0) return 3;
        else if(dir == 1) return 0;
        else if(dir == 2) return 1;
        else return 2;
    }else if(kind == 3){
        if(dir == 0) return 2;
        else if(dir == 1) return 0;
        else if(dir == 2) return 3;
        else return 1;
    }else if(kind == 4){
        if(dir == 0) return 1;
        else if(dir == 1) return 2;
        else if(dir == 2) return 3;
        else return 0;
    }else{
        if(dir == 0) return 1;
        else if(dir == 1) return 0;
        else if(dir == 2) return 3;
        else return 2;
    }
}
 
pair<int, int> intoTheWormHole(pair<int, int> sp, int num){
    int nr, nc;
    for(int i = 0; i < 2; i++){
        if(wormHole[num][i].first != sp.first || wormHole[num][i].second != sp.second){
            nr = wormHole[num][i].first;
            nc = wormHole[num][i].second;
        }
    }
    return {nr,nc};
}
 
void playTheGame(int cnt, pair<int, int> point, int dir, pair<int, int> sp){
    int nr = point.first;
    int nc = point.second;
    int ndir = dir;
    while(true){
        nr += dr[ndir];
        nc += dc[ndir];
        set<pair<int, int>>::iterator iter = blackHole.find({nr,nc});
        if(iter != blackHole.end()){
            if(ans < cnt) ans = cnt;
            break;
        }
        if(nr == sp.first && nc == sp.second){
            if(ans < cnt) ans = cnt;
            break;
        }
        if(nr < 1 || nr > N || nc < 1 || nc > N){
            //다음 위치가 벽 넘어일 경우 벽에 부딪치고 점수 추가
            int nextdir = HitTheWall(ndir);
            cnt++;
            ndir = nextdir;
        }else{
            if(gameMap[nr][nc] >= 1 && gameMap[nr][nc] <= 5){
                //다음 위치가 블록에 부딪쳤을 때 점수 추가
                int nextdir = HitTheBlock(gameMap[nr][nc], ndir);
                cnt++;
                ndir = nextdir;
            }
            else if(gameMap[nr][nc] >= 6 && gameMap[nr][nc] <= 10){
                //다음 위치가 웜홀일때, 점수 추가 X, 뱡향 변경 X
                pair<int, int> next = intoTheWormHole({nr,nc}, gameMap[nr][nc]-5);
                nr = next.first;
                nc = next.second;
            }
        }
    }
}
 
int main(){
    int tc;
    cin >> tc;
    for(int t = 1; t <= tc; t++){
        initGame();
        cin >> N;
        for(int r = 1; r <= N; r++){
            for(int c = 1; c <= N; c++){
                cin >> gameMap[r][c];
                if(gameMap[r][c] == -1){
                    blackHole.insert({r,c});
                }else if(gameMap[r][c] == 0){
                    starting.push_back({r,c});
                }else if(gameMap[r][c] >= 6 && gameMap[r][c] <= 10){
                    wormHole[gameMap[r][c]-5].push_back({r,c});
                }
            }
        }
        for(int i = 0; i < starting.size(); i++){
            for(int dir = 0; dir < 4; dir++){
                playTheGame(0, starting[i], dir, starting[i]);
            }
        }
        cout << "#" << t << " " << ans << endl;
    }
    return 0;
}