[SWEA] 핀볼게임

[문제]

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

SW Expert Academy

 

[풀이]

 

1) 0 : 빈 공간(구슬의 처음 시작위치가 될 수 있는 공간) / 1~5 : 블록 / 6~10 : 웜홀 / -1 :블랙홀 (종료공간)

 

2) 총 N개의 구슬로 게임을 진행할 수 있고 구슬이 처음 시작위치에 오거나, 블랙홀을 만나면 게임이 종료된다. 

 

3) 시작위치와 방향은 임의로 진행한다. (시간복잡도 : O(n^2*4))

 

4) tip?? 은 벽에 부딪혀도 방향이 반대로 전환되기 때문에

(0,0) ~ (0,n+1) / (n+1 ~0) ~ (n+1, n+1) 을 모두 블록 5로 만들어준다. (블록 5는 구슬이 부딪히면 반대 방향으로 전환된다.)

=> 따로 인덱스 초과 처리를 하지 않아도 된다. 

 

5) 웜홀은 항상 쌍으로 제시된다. 총 5개의 인덱스를 가진 bool flag  배열을 사용하여 flag가 false라면 아직 쌍이 되는 웜홀이 안나왔으므로 true로 값을 바꿔주고 현재의 x,y좌표를 저장한다. 

 

6) 벽에 부딪힌 횟수 최대가 되는 값을 구한다. 

 

* changeDir() 은 나아가야할 방향이 각 블록마다 어느 방향으로 전환되는 지를 반환한다. 

-> (동) 쪽으로 나아가고 있는 중이라면 블록 1,2,5 는 반대방향으로 전환되고 

3은 남쪽으로 / 4는 북쪽으로 전환된다. (나아가고 있는 방향이라는 것을 생각해야한다. .)

 

#include <iostream> #include <vector> #include <cstring> using namespace std; int n; int map[103][103]; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; //상 좌 하 우 typedef struct Warm { int sx, sy, ex, ey; } W; Warm warmH[6]; bool flag[6]; int changeDir(int dir, int block) { switch (dir) { case 0: { if (block == 1 || block == 4 || block == 5) return 2; else if (block == 2) return 3; else return 1; break; } case 1: { //서 if (block == 3 || block == 4 || block == 5) return 3; else if (block == 1) return 0; else return 2; break; } case 2: { //남 if (block == 2 || block == 3 || block == 5) return 0; else if (block == 1) return 3; else return 1; break; } case 3: { //동 if (block == 1 || block == 2 || block == 5) return 1; else if (block == 3) return 2; else return 0; break; } } } int playGame(int sx, int sy, int d) { int x =sx, y = sy; int res= 0; while(1) { x += dx[d]; y += dy[d]; if ((x == sx && y == sy) || map[x][y] == -1) break; if (1<=map[x][y] && map[x][y] <= 5) { //블록과 부딪힘 res++; d = changeDir(d, map[x][y]); } else if (6<= map[x][y] && map[x][y] <= 10) { int tmp = map[x][y]-6; if (warmH[tmp].sx == x && warmH[tmp].sy == y) { x = warmH[tmp].ex; y = warmH[tmp].ey; } else { x = warmH[tmp].sx; y = warmH[tmp].sy; } } } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int tc = 1; tc <= t; tc++) { cin >> n; memset(flag, 0, sizeof(flag)); int ans = 0; //벽을 5와 같은 작용을 하도록 만든다. for (int i = 0; i <= n+1; i++) { map[0][i] = map[i][n + 1] = map[i][0] = map[n + 1][i] = 5; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> map[i][j]; if (6 <= map[i][j] && map[i][j] <= 10) { //웜홀 if (!flag[map[i][j] - 6]) { warmH[map[i][j] - 6].sx = i; warmH[map[i][j] - 6].sy = j; flag[map[i][j] - 6] = true; } else { warmH[map[i][j] - 6].ex = i; warmH[map[i][j] - 6].ey = j; } } } } //임의의 방향, 좌표에 핀을 놓고 시뮬레이션 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (!map[i][j]) { for (int d = 0; d < 4; d++) { int res = playGame(i, j, d); ans = ans > res ? ans : res; } } } } cout << "#" << tc << " " << ans << '\n'; } return 0; }