문제 해결/SWEA
[SWEA] 5650. 핀볼 게임
자잘
2020. 1. 17. 17:42
문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
푸는데 3일이나 걸렸네요. 물론 이 문제를 푸는데 모든 시간을 쓴 것은 아니지만 BFS, DFS, 반복문 모두 시도해본 문제입니다. 이 문제를 풀다보니 어떨때 어떤 기법을 써야하는지 감이 잡혔습니다. DFS로 풀면 스택 메모리 제한에 걸려서 런타임 오류가 납니다. 그래서 저는 반복문으로 해결했습니다. 조건을 정확히 달지 않으면 무조건 틀립니다.
그리고 가장 중요한 포인트는 벽이나 블록의 경사면이 아닌 부분과 만나는 순간 왔던 길을 그대로 돌아가게 됩니다. 따라서 벽이나 블록의 경사면이 아닌 부분과 만나기 전까지의 점수에 2배를 해준 다음 1을 더해주면 됩니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include<vector> | |
using namespace std; | |
int n, tc,startX,startY,ans; | |
int map[100][100]; | |
int dy[4] = { -1,1,0,0 }; | |
int dx[4] = { 0,0,-1,1 }; | |
struct HOLE | |
{ | |
int y, x, num; | |
}; | |
vector<HOLE> vt; | |
bool InRange(int y, int x) | |
{ | |
return 0 <= x && x < n && 0 <= y && y < n; | |
} | |
int change_dir(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 (dir == 0) return 1; | |
if (dir == 1) return 0; | |
if (dir == 2) return 3; | |
if (dir == 3) return 2; | |
} | |
} | |
bool check_block(int block, int dir) | |
{ | |
if (block == 1) | |
if (dir == 1 || dir == 2) | |
return true; | |
else | |
return false; | |
else if (block == 2) | |
if (dir == 0 || dir == 2) | |
return true; | |
else | |
return false; | |
else if (block == 3) | |
if (dir == 0 || dir == 3) | |
return true; | |
else | |
return false; | |
else if (block == 4) | |
if (dir == 1 || dir == 3) | |
return true; | |
else | |
return false; | |
else | |
return true; | |
} | |
int dfs(int y, int x, int dir, int c) | |
{ | |
int nx = x; | |
int ny = y; | |
int ndir = dir; | |
int nc = c; | |
while (1) | |
{ | |
nx += dx[ndir]; | |
ny += dy[ndir]; | |
if (!InRange(ny, nx)) | |
return nc * 2 + 1; | |
else if (map[ny][nx] == -1||(nx == startX && ny == startY)) | |
return nc; | |
else if (1 <= map[ny][nx] && map[ny][nx] <= 5) | |
{ | |
ndir = change_dir(map[ny][nx], ndir); | |
if (check_block(map[ny][nx], ndir)) | |
return 2 * nc + 1; | |
nc++; | |
} | |
else if (map[ny][nx] > 5) | |
{ | |
for (int i = 0; i < vt.size(); i++) | |
{ | |
if (vt[i].num == map[ny][nx] && (nx != vt[i].x || ny != vt[i].y)) | |
{ | |
ny = vt[i].y; | |
nx = vt[i].x; | |
break; | |
} | |
} | |
} | |
} | |
} | |
int main(void) | |
{ | |
cin >> tc; | |
for (int t = 1; t <= tc; t++) | |
{ | |
cin >> n; | |
vt.clear(); | |
ans = 0; | |
for(int i = 0; i<n; i++) | |
for (int j = 0; j < n; j++) | |
{ | |
cin >> map[i][j]; | |
if (map[i][j] > 5) | |
vt.push_back({ i,j,map[i][j] }); | |
} | |
for(int i = 0; i<n; i++) | |
for (int j = 0; j < n; j++) | |
{ | |
if (map[i][j] == 0) | |
{ | |
for (int k = 0; k < 4; k++) | |
{ | |
startX = j, startY = i; | |
int num = dfs(i, j, k, 0); | |
ans = ans < num ? num : ans; | |
} | |
} | |
} | |
cout <<'#'<<t<<' '<< ans << '\n'; | |
} | |
} |