최근에 SWEA 문제를 차근차근 풀어보고 있는데,
생각지도 못한곳에서 시간초과로 인해 몇시간을 헤맸어서 이에 대해 적어본다.
문제는 5650. [모의 SW 역량테스트] 핀볼 게임 에서 발생했었고, 코드는 이 문제에 대한 솔루션이다.
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제 자체는 굉장히 직관적이고 이해하는데 어렵지 않다.
정말 문제 그대로 반복문으로 구현하기만 하면 된다.
#include <vector>
#include <queue>
#include <iostream>
#define MAX 150
using namespace std;
int N, ans;
/* up left down right */
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, -1, 0, 1};
int MAP[MAX][MAX];
vector <pair <int, int>> list;
vector <vector <pair <int, int>>> white (11);
void init() {
ans = -1;
list.clear();
for (int i = 0; i < white.size(); ++i)
white[i].clear();
for (int r = 0; r < MAX; ++r)
for (int c = 0; c < MAX; ++c)
MAP[r][c] = 5;
}
void solution() {
for (const auto& point : list) {
int row = point.first;
int col = point.second;
for (int startDir = 0; startDir < 4; ++startDir) {
int curDir = startDir;
int score = 0;
pair <int, int> curPtr = pair <int, int> (row, col);
while (1) {
int nr = curPtr.first + dr[curDir];
int nc = curPtr.second + dc[curDir];
if (MAP[nr][nc] == 1) {
/* up left down right */
if (curDir == 0) curDir = 2;
else if (curDir == 1) curDir = 0;
else if (curDir == 2) curDir = 3;
else curDir = 1;
++score;
}
else if (MAP[nr][nc] == 2) {
/* up left down right */
if (curDir == 0) curDir = 3;
else if (curDir == 1) curDir = 2;
else if (curDir == 2) curDir = 0;
else curDir = 1;
++score;
}
else if (MAP[nr][nc] == 3) {
/* up left down right */
if (curDir == 0) curDir = 1;
else if (curDir == 1) curDir = 3;
else if (curDir == 2) curDir = 0;
else curDir = 2;
++score;
}
else if (MAP[nr][nc] == 4) {
/* up left down right */
if (curDir == 0) curDir = 2;
else if (curDir == 1) curDir = 3;
else if (curDir == 2) curDir = 1;
else curDir = 0;
++score;
}
else if (MAP[nr][nc] == 5) {
/* up left down right */
if (curDir == 0) curDir = 2;
else if (curDir == 1) curDir = 3;
else if (curDir == 2) curDir = 0;
else curDir = 1;
++score;
}
else if (MAP[nr][nc] >= 6) {
int tmpr, tmpc;
for (int i = 0; i < white[MAP[nr][nc]].size(); ++i) {
if (!(white[MAP[nr][nc]][i].first == nr && white[MAP[nr][nc]][i].second == nc)){
tmpr = white[MAP[nr][nc]][i].first;
tmpc = white[MAP[nr][nc]][i].second;
break;
}
}
nr = tmpr;
nc = tmpc;
}
else if (MAP[nr][nc] == -1 || (nr == row && nc == col))
break;
curPtr = pair <int, int> (nr, nc);
}
if (score > ans) ans = score;
}
}
}
int main(int argc, char** argv) {
int T;
cin >> T;
for (int i = 1; i <= T; ++i) {
init();
cin >> N;
for (int r = 1; r < N + 1; ++r)
for (int c = 1; c < N + 1; ++c){
cin >> MAP[r][c];
if (MAP[r][c] == 0) list.push_back(pair <int, int>(r, c));
if (MAP[r][c] >= 6) white[MAP[r][c]].push_back(pair <int, int>(r, c));
}
solution();
cout << "#" << i << " " << ans << "\n";
}
}
처음 문제를 보면서 바로 작성했던 코드이다.
간단한 코드에 대한 설명을 하자면, 일단 입력을 받고 MAP이 0일때, list 벡터에 해당 좌표 값을 pair로 집어넣는다.
이는 시뮬레이션을 돌릴때 굳이 다시 MAP의 2차원 배열 처음 부터 끝까지 훑어 보면서 0 값을 찾는 의미없는 시간낭비를 방지하기 위해서다.
시뮬레이션에서는 list 벡터에 들어있는 좌표들을 하나씩 꺼내보면서 위 아래 왼쪽 오른쪽 4방향에 대해서 모든 경우의 수를 찾는 간단한 알고리즘이다.
디버깅 없이도 수월하게 샘플 테스트 케이스를 통과했기에 쉽사리 통과를 할 줄 알고 제출을 했지만,,
이상하게도 테스트 케이스 48번에서 계속해서 시간초과가 났다.
아무리봐도 알고리즘적으로는 틀린게 없었기에,
처음엔 단순히 if문이 중첩이 돼서 그런건가 하고, 방향전환을 할때 아래와 같이 배열 값을 통해 전환이 이루어지도록 수정했다.
int type1[4] = {2, 0, 3, 1};
int type2[4] = {3, 2, 0, 1};
int type3[4] = {1, 3, 0, 2};
int type4[4] = {2, 3, 1, 0};
int type5[4] = {2, 3, 0, 1};
...
while (1) {
int nr = curPtr.first + dr[curDir];
int nc = curPtr.second + dc[curDir];
if (MAP[nr][nc] == 1) {
/* up left down right */
curDir = type1[curDir];
++score;
}
else if (MAP[nr][nc] == 2) {
/* up left down right */
curDir = type2[curDir];
++score;
}
else if (MAP[nr][nc] == 3) {
/* up left down right */
curDir = type3[curDir];
++score;
}
else if (MAP[nr][nc] == 4) {
/* up left down right */
curDir = type4[curDir];
++score;
}
else if (MAP[nr][nc] == 5) {
/* up left down right */
curDir = type5[curDir];
++score;
}
...
}
...
하지만 여전히 테스트 케이스 48번에서 시간초과로 통과하지 못하였고, 문제를 통과하는 데 많은 시간이 걸렸다..
결론부터 말하자면, 문제는 pair가 원인이었고 해당 부분을 struct로 바꿔주니 통과하였다.
원인을 발견한건, 혹시나하고 list배열에 있는 좌표만 참조하는 부분을 그냥 MAP 2차원 배열의 처음 부터 끝까지 훑어보면서 0을 찾는걸로 바꿔서 테스트 해봤는데 통과되는걸 보고 알아 차렸다..
이렇게 차이가 나는거는 pair가 객체이기 때문에 나타나는 현상이라고 하는데,
이와 관련해서 몇가지 찾아본 링크는 다음과 같다.
[C++] struct, pair 비교
활용 문제 : www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운
latter2005.tistory.com
직접적으로 std::sort 함수를 이용하여 struct 와 pair의 속도를 비교한 포스팅인데, pair가 struct에 비해 거의 1.5배 정도 더 느린것을 확인할 수 있다.
구조체가 클래스 보다 속도가 빠른가요? - GpgStudy 포럼
프로그래밍 일반에 관한 포럼입니다. Moderator: 류광 비회원 Post by 비회원 » 2008-04-21 16:33 전 팀장이 짠걸 보니, 속도 때문이라면서, 일부러 구조체를 많이 썼더라구요. 물론 구조체에 상속이나 priv
www.gpgstudy.com
조금 오래된 글이긴 한데, 이런 pair를 쓰냐 그냥 구조체를 쓰냐하는 문제는 예전부터 있었던 것 같다.
뭐 자세히는 모르겠지만, 앞으로 코딩문제를 풀때는 pair 보다는 구조체를 사용해서 풀어야 겠다라고 느끼게된 문제였다.
수정한 코드는 다음과 같이 pair 대신 node라는 구조체를 선언해서 pair를 모두 node로 바꾸었다.
#include <vector>
#include <queue>
#include <iostream>
#define MAX 150
using namespace std;
int N, ans;
/* up left down right */
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, -1, 0, 1};
int MAP[MAX][MAX];
int type1[4] = {2, 0, 3, 1};
int type2[4] = {3, 2, 0, 1};
int type3[4] = {1, 3, 0, 2};
int type4[4] = {2, 3, 1, 0};
int type5[4] = {2, 3, 0, 1};
typedef struct st {
int first, second;
} node;
vector <node> list;
vector <vector <node>> white (11);
void init() {
ans = -1;
list.clear();
for (int i = 0; i < white.size(); ++i)
white[i].clear();
for (int r = 0; r < N+2; ++r)
for (int c = 0; c < N+2; ++c)
MAP[r][c] = 5;
}
void solution() {
for (const auto& points : list) {
int row = points.first;
int col = points.second;
for (int startDir = 0; startDir < 4; ++startDir) {
int curDir = startDir;
int score = 0;
node curPtr;
curPtr.first = row;
curPtr.second = col;
while (1) {
int nr = curPtr.first + dr[curDir];
int nc = curPtr.second + dc[curDir];
if (MAP[nr][nc] == 1) {
/* up left down right */
curDir = type1[curDir];
++score;
}
else if (MAP[nr][nc] == 2) {
/* up left down right */
curDir = type2[curDir];
++score;
}
else if (MAP[nr][nc] == 3) {
/* up left down right */
curDir = type3[curDir];
++score;
}
else if (MAP[nr][nc] == 4) {
/* up left down right */
curDir = type4[curDir];
++score;
}
else if (MAP[nr][nc] == 5) {
/* up left down right */
curDir = type5[curDir];
++score;
}
else if (MAP[nr][nc] >= 6) {
int tmpr, tmpc;
for (int i = 0; i < white[MAP[nr][nc]].size(); ++i) {
if (!(white[MAP[nr][nc]][i].first == nr && white[MAP[nr][nc]][i].second == nc)){
tmpr = white[MAP[nr][nc]][i].first;
tmpc = white[MAP[nr][nc]][i].second;
break;
}
}
nr = tmpr;
nc = tmpc;
}
else if (MAP[nr][nc] == -1 || (nr == row && nc == col))
break;
curPtr.first = nr;
curPtr.second = nc;
}
if (score > ans) ans = score;
}
}
}
int main(int argc, char** argv) {
int T;
cin >> T;
for (int i = 1; i <= T; ++i) {
cin >> N;
init();
for (int r = 1; r < N + 1; ++r)
for (int c = 1; c < N + 1; ++c){
node nn;
cin >> MAP[r][c];
nn.first = r;
nn.second = c;
if (MAP[r][c] == 0) list.push_back(nn);
if (MAP[r][c] >= 6) white[MAP[r][c]].push_back(nn);
}
solution();
cout << "#" << i << " " << ans << "\n";
}
}
