[SWEA_모의SW테스트] 5650번 - 핀볼 게임

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

SW Expert Academy

[최종수정]

이틀이 걸린 문제다.

이 문제를 풀면서 짜증도 많이 나고 이해가 안되는 문제들을 많이 접했지만

반대로 많이 성장한 계기가 되었다.

 

[성장]

1. 이 문제는 지역변수를 담는 스택의 메모리 초과 문제를 생각할 수 있게 해주었고,

2. 생각지 못한 2차원 벡터의 인덱싱 문제를 알게 해주었다.

 

[성장] 1번의 경우 최대한 지역변수를 적게 쓰는 방법으로 코딩하는 것이 더욱 메모리측면에서 중요하다는 점을 깨닫게 해주었는데, 자세한 사항은 아래의 예시와 같다.

e.g., 웜홀의 번호가 6번~10번이라면 기존에는 (웜홀번호, (행좌표, 열좌표))로 저장하는

vector<pair<int, pair<int, int> > > wormhole;로 선언했겠지만, 이렇게 하지 말고

vector<pair<int, int> > wormhole[11];로 선언해서 wormhole[웜홀번호]의 pair<int, int>를 조사하는 식으로 구현하는 것이 3개 -> 2개의 지역변수를 사용해서 메모리를 덜 잡아먹도록 구현하는 방법이다.

 

[성장] 1번의 경우 나에게 해당사항이 없다.

저 이유때문에 아래의 1번 코드덩어리에서 문제가 발생해 하나의 테스트케이스가 통과하지 못한것으로 착각하였으나, 스택메모리가 터진게 아니고 조건문을 잘못 넣어두었던 것이었다..

( r != wormhole[i].second.first && c != wormhole[i].second.second 에서

 (r != wormhole[i].second.first  || c != wormhole[i].second.second) 으로 바꿔주니 모든 테케를 통과했다.)

그러므로.. 지역 변수의 과도한 생성때문에 스택이 터진것으로 오해한 것은 나의 불찰이었다. 스택 메모리 초과문제라고 생각한 이유는 이 문제의 SWEA 댓글창에 49/50개 통과한 사람들이 주로 불만을 토로하는 이유가 스택 메모리 초과였기 때문이었다.. 아무튼 이건 내 경우 문제가 아니라는 것!

 

따라서 그냥 조건문이 잘못된 것 때문에 삽질했던 해프닝의 결과다. 결론은 스택은 문제 없음!

 

결과적으로 아래 문제가 런타임 에러를 발생시키고 실패를 유발한 이유였다. 일반적인 배열의 인덱스로 어떤 배열값이 들어가도 괜찮았지만 벡터의 경우 좀 다른것 같다. (코드 (2번), (3번) 참조!)

 

[성장] 2번의 경우 .. 인덱싱에서 처음 알게된 문제점이었다.

기존에 내가 많은 코딩 테스트 문제를 풀면서 이렇게 해오지 않았나 싶었던 사항이었는데, 런타임 에러를 발생시키는 문제임을 알게되었다.

 

가령, vector<pair<int, int> > wormhole[11];로 선언한 벡터에서 6번 웜홀의 2번째 요소를 불러오려면

wormhole[6][1]을 호출하면 된다. 이 문제의 경우, 지도의 요소값을 웜홀의 번호로 쓰기 때문에, 기존에 런타임에러가 난 코드에서는 wormhole[m[r][c]][1] 이런식으로 호출했는데, 인덱스의 m[r][c]가 문제를 일으키는 원인이었다....!!!

 

아니, m[r][c]가 6~10값이어서 그대로 넣고 두 번째꺼 불러오려고 wormhole[m[r][c]][1]이렇게 했는데 자꾸 런타임 에러가 나는 것이었다. 심지어 로직은 다 맞는거 몇 번이나 확인했는데 말이다.

 

그래서 진짜 매너리즘에 빠진사람처럼 좀비처럼 이것저것 해보다가 int idx = m[r][c]; 이렇게 선언하고

wormhole[idx][1]... 이런식으로 비교연산을 하며 돌려봤더니.... 이제서야 된다.

 

아니 이게 문제가 되던 사항이었나..? 싶었다.

결과적으로 문제는 pass했지만 상처가 많이 남은 문제다.

대신 이 덕에 시험장에서 '아니 로직이 맞는데 대체 뭐가 문젠대??' 하면서 머리를 쥐어뜯는 상황을 일부 예방할 수 있게 되었다.

 

[1번 - 성공]
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 102
 
using namespace std;
 
int N, T, m[MAX][MAX];
typedef pair<int, int> pii;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 }; // 동, 서, 남, 북
int changeDir[6][4];
vector<pair<int, int> > wormhole[11];
 
void initWorm(){
    for (int i = 0; i < 11; i++){
        wormhole[i].clear();
        wormhole[i].push_back(make_pair(-1, -1));
        wormhole[i].push_back(make_pair(-1, -1));
    }
}
int simulation(int sr, int sc, int dir){
    int r = sr, c = sc, d = dir;
    int ret = 0;
    while (1){
        r += dr[d];
        c += dc[d];
        if (m[r][c] == -1 || (r == sr && c == sc)) return ret;
        else if (1 <= m[r][c] && m[r][c] <= 5){
            ret++;
            d = changeDir[m[r][c]][d];
        }
        else if (6 <= m[r][c] && m[r][c] <= 10){
            int idx = m[r][c];
            if (r != wormhole[idx][0].first || c != wormhole[idx][0].second){
                r = wormhole[idx][0].first;
                c = wormhole[idx][0].second;
            }
            else{
                r = wormhole[idx][1].first;
                c = wormhole[idx][1].second;
            }
        }
    }
    return -1;
}
 
int main(){
    cin >> T;
    for (int tc = 1; tc <= T; tc++){
        int answer = 0;
        cin >> N;
        initWorm();
        for (int i = 0; i <= N + 1; i++){
            for (int j = 0; j <= N + 1; j++){
                if (i == 0 || i == N + 1 || j == 0 || j == N + 1) m[i][j] = 5;
                else m[i][j] = 0;
            }
        }
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                cin >> m[i][j];
                if (6 <= m[i][j] && m[i][j] <= 10) {
                    if (wormhole[m[i][j]][0] == make_pair(-1, -1)){
                        wormhole[m[i][j]][0] = make_pair(i, j);
                    }
                    else
                        wormhole[m[i][j]][1] = make_pair(i, j);
                }
            }
        }
        changeDir[1][0] = 1; changeDir[1][1] = 3; changeDir[1][2] = 0; changeDir[1][3] = 2;
        changeDir[2][0] = 1; changeDir[2][1] = 2; changeDir[2][2] = 3; changeDir[2][3] = 0;
        changeDir[3][0] = 2; changeDir[3][1] = 0; changeDir[3][2] = 3; changeDir[3][3] = 1;
        changeDir[4][0] = 3; changeDir[4][1] = 0; changeDir[4][2] = 1; changeDir[4][3] = 2;
        changeDir[5][0] = 1; changeDir[5][1] = 0; changeDir[5][2] = 3; changeDir[5][3] = 2;
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                if (m[i][j] == 0){
                    for (int k = 0; k < 4; k++){
                        answer = max(answer, simulation(i, j, k));
                    }
                }
            }
        }
        cout << "#" << tc << " " << answer << '\n';
    }
    return 0;
}
 
 
 
[2번 - 벡터 내 인덱스 때문에 런타임 에러] (성공 코드)
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 102
using namespace std;
 
int N, T, m[MAX][MAX];
 
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 }; // 동, 서, 남, 북
vector<pair<int, pair<int, int> > > wormhole[11];
int changeDir[6][4];
int simulation(int sr, int sc, int dir){
   int r = sr, c = sc, d = dir;
   int ret = 0;
   while (1){
      r += dr[d];
      c += dc[d];
      if (m[r][c] == -1 || (r == sr && c == sc)) return ret;
      else if (1 <= m[r][c] && m[r][c] <= 5){
         ret++;
         d = changeDir[m[r][c]][d];
      }
      else if (6 <= m[r][c] && m[r][c] <= 10){
          int idx = m[r][c];
         for (int i = 0; i < 2; i++){
            if (wormhole[idx][i].first == m[r][c] && (r != wormhole[idx][i].second.first || c != wormhole[idx][i].second.second)){
               r = wormhole[idx][i].second.first;
               c = wormhole[idx][i].second.second;
               break;
           } // 인덱스 m[r][c]를 idx로 사용하니 된다. !!!!!!!!!!!!!!!!!!!!
         }
      }
   }
   return -1;
}
 
int main(){
   cin >> T;
   for (int tc = 1; tc <= T; tc++){
      int answer = 0;
      cin >> N;
       for(int i=0; i<11; i++)
         wormhole[i].clear();
      for (int i = 0; i <= N + 1; i++){
         for (int j = 0; j <= N + 1; j++){
            if (i == 0 || i == N + 1 || j == 0 || j == N + 1) m[i][j] = 5;
            else m[i][j] = 0;
         }
      }
      for (int i = 1; i <= N; i++){
         for (int j = 1; j <= N; j++){
            cin >> m[i][j];
            if (6 <= m[i][j] && m[i][j] <= 10) wormhole[m[i][j]].push_back(make_pair(m[i][j], make_pair(i, j)));
         }
      }
      changeDir[1][0] = 1; changeDir[1][1] = 3; changeDir[1][2] = 0; changeDir[1][3] = 2;
      changeDir[2][0] = 1; changeDir[2][1] = 2; changeDir[2][2] = 3; changeDir[2][3] = 0;
      changeDir[3][0] = 2; changeDir[3][1] = 0; changeDir[3][2] = 3; changeDir[3][3] = 1;
      changeDir[4][0] = 3; changeDir[4][1] = 0; changeDir[4][2] = 1; changeDir[4][3] = 2;
      changeDir[5][0] = 1; changeDir[5][1] = 0; changeDir[5][2] = 3; changeDir[5][3] = 2;
      for (int i = 1; i <= N; i++){
         for (int j = 1; j <= N; j++){
            if (m[i][j] == 0){
               for (int k = 0; k < 4; k++){
                  answer = max(answer, simulation(i, j, k));
               }
            }
         }
      }
      cout << "#" << tc << " " << answer << '\n';
      
   }
   return 0;
}
 
 
 
 
[3번 - 벡터 내 인덱스 때문에 런타임 에러] (실패코드)
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 102
using namespace std;
 
int N, T, m[MAX][MAX];
 
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 }; // 동, 서, 남, 북
vector<pair<int, pair<int, int> > > wormhole[11];
int changeDir[6][4];
int simulation(int sr, int sc, int dir){
   int r = sr, c = sc, d = dir;
   int ret = 0;
   while (1){
      r += dr[d];
      c += dc[d];
      if (m[r][c] == -1 || (r == sr && c == sc)) return ret;
      else if (1 <= m[r][c] && m[r][c] <= 5){
         ret++;
         d = changeDir[m[r][c]][d];
      }
      else if (6 <= m[r][c] && m[r][c] <= 10){
          //int idx = m[r][c];
         for (int i = 0; i < 2; i++){
            if (wormhole[m[r][c]][i].first == m[r][c] && (r != wormhole[m[r][c]][i].second.first || c != wormhole[m[r][c]][i].second.second)){
               r = wormhole[m[r][c]][i].second.first;
               c = wormhole[m[r][c]][i].second.second;
               break;
           } // 이 위의 인덱스로 사용된 m[r][c]가 문제!!!!!!!
         }
      }
   }
   return -1;
}
 
int main(){
   cin >> T;
   for (int tc = 1; tc <= T; tc++){
      int answer = 0;
      cin >> N;
       for(int i=0; i<11; i++)
         wormhole[i].clear();
      for (int i = 0; i <= N + 1; i++){
         for (int j = 0; j <= N + 1; j++){
            if (i == 0 || i == N + 1 || j == 0 || j == N + 1) m[i][j] = 5;
            else m[i][j] = 0;
         }
      }
      for (int i = 1; i <= N; i++){
         for (int j = 1; j <= N; j++){
            cin >> m[i][j];
            if (6 <= m[i][j] && m[i][j] <= 10) wormhole[m[i][j]].push_back(make_pair(m[i][j], make_pair(i, j)));
         }
      }
      changeDir[1][0] = 1; changeDir[1][1] = 3; changeDir[1][2] = 0; changeDir[1][3] = 2;
      changeDir[2][0] = 1; changeDir[2][1] = 2; changeDir[2][2] = 3; changeDir[2][3] = 0;
      changeDir[3][0] = 2; changeDir[3][1] = 0; changeDir[3][2] = 3; changeDir[3][3] = 1;
      changeDir[4][0] = 3; changeDir[4][1] = 0; changeDir[4][2] = 1; changeDir[4][3] = 2;
      changeDir[5][0] = 1; changeDir[5][1] = 0; changeDir[5][2] = 3; changeDir[5][3] = 2;
      for (int i = 1; i <= N; i++){
         for (int j = 1; j <= N; j++){
            if (m[i][j] == 0){
               for (int k = 0; k < 4; k++){
                  answer = max(answer, simulation(i, j, k));
               }
            }
         }
      }
      cout << "#" << tc << " " << answer << '\n';
      
   }
   return 0;
}