[SWEA] 5650번: 핀볼 게임(C++)/Simulation

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo&categoryId=AWXRF8s6ezEDFAUo&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

처음 코드가 계속 시간 초과가 나서 계속 고민했던 문제

장애물 블럭들에 대해서는 바뀔 방향들에 대해 배열을 만들어주고, 벽은 5번 블록으로 채워줬다
프로그래머스 식으로 전역변수 최대한 안 쓰고 푸는데 왜 계속 시간초과지? 했는데
바로바로 함수의 인자로 벡터를 전달할 때 &(레퍼런스 변수 키워드)를 붙이느냐 안 붙이느냐 였다 ..
&를 붙이게 되면 메모리 주소를 넘기기 때문에 문제가 발생하지 않지만
&를 안 붙이게 되면 C에서는 기본적으로 CallByValue로 값을 넘기기 때문에 벡터(그것도 이중)을 함수 호출 시 마다 복사해주고 있었다
simulation() 호출 시 1번 복사
pinball() 호출 시 최대 N*N번 복사(배열의 길이가 N일 때)
삭제한 코드에서는 심지어 웜홀의 위치를 구하기 위해 또 복사를 해주었으니 시간 초과가 발생하는 것이엇다

이 부분은 간과하기 딱 좋은 부분이니까 앞으로 C++로 문제 풀 때는 꼭 !!!!!!!!!!!!!!!!! 유의하는걸로

#include <iostream> #include <cstdio> #include <vector> #include <map> using namespace std; typedef struct { int x, y; }point; int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }; int block[][6] = { {0,0,0,0},{2,0,3,1},{2,3,1,0},{1,3,0,2},{3,2,0,1},{2,3,0,1} }; int pinball(point cur, int dir, int n, vector<vector<int>>& board) { point start = cur; int score = 0; do { cur.x += dx[dir]; cur.y += dy[dir]; int boardNum = board[cur.y][cur.x]; if (boardNum == 0) { continue; } else if (boardNum == -1) { return score; } else if (boardNum <= 5) { dir = block[boardNum][dir]; score++; } else if (boardNum <= 10) { bool flag = true; for (int i = 1; i <= n; i++) { for (int j = 1; (j <= n)&&flag; j++) if (board[i][j] == boardNum && !(i == cur.y && j == cur.x)) { cur = { j,i }; flag = false; break; } } } } while (!(cur.x == start.x && cur.y == start.y) && board[cur.y][cur.x] != -1); return score; } int simulation(int n, vector<vector<int>>& board) { int answer = -1; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (board[i][j] == 0) { int ret = 0; for (int k = 0; k < 4; k++) { ret = pinball({ j,i }, k, n, board); if (ret > answer) answer = ret; } } } return answer; } int main() { int test_case; int T; cin >> T; for (test_case = 1; test_case <= T; ++test_case) { int n; scanf("%d", &n); vector<vector<int>> board(n + 2); for (int i = 0; i < n + 2; i++) board[i] = vector<int>(n + 2); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &board[i][j]); } } for (int i = 1; i <= n; i++) { board[0][i] = board[n + 1][i] = board[i][0] = board[i][n + 1] = 5; } cout << "#" << test_case << " " << simulation(n, board) << "\n"; } return 0; }