5650.핀볼 게임

이번에 풀어볼 문제는 핀볼게임이다. 정답률은 31%정도인데 나의 체감은 60%정도가 맞지 않나싶다.

오히려 5656번 벽돌깨기가 체감난이도가 더 높았다. 근데 그건.. 정답률이 60%... 여튼 한 번에 풀어서 다행이다.

톱니봐퀴나 핀볼게임이나 공통점은 문제를 풀면서 딱히 큰 예외를 신경쓰지 않아도 될 것같다는 느낌과

정확하게만 구현하면 딱히 큰 예외가 없어서 한 번에 정답이 맞겠다는 느낌이 오는 문제였다는 것이다.

내 코드가 좋다는 것은 아니지만 그냥 하라는대로 하니까 풀린 문제이다.

SW Expert Academy

---

 

설명은 딱히 없다. 풀이 방식은 다음과 같다.

1. 빈 칸에 핀볼이 떨어져서 상, 하, 좌, 우로 움직인다 => 즉, 빈칸에 다 들어가고 4방향으로 탐색하는 경우의 수를 다해봐야한다.

2. 그 다음 부터는 그냥 벽돌모양과 벽에 부딪히는 것에 대해 똑같이 구현만 해주면 된다.

그래서 나는 현재 방향을 변수로 처리해서 방향이 바뀔 때마다 해당 변수 값만 바꿔주면서 문제를 풀었다..

웜홀의 경우는 deque로 짝을 지어줘서 2개가 1쌍이므로 현재 좌표와 다른 웜홀 좌표를 사용했다.

 

---

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <algorithm>
#include <string.h>
 
#define MAX 101 
using namespace std;
 
int T, N;
int map[MAX][MAX];
 
int dx[4] = { 0, -1, 0, 1 }; // 좌, 상, 우 하
int dy[4] = { -1, 0, 1, 0 };
 
deque<int>x_mov;
deque<int>y_mov;
 
deque<pair<int, int>>hole1;
deque<pair<int, int>>hole2;
deque<pair<int, int>>hole3;
deque<pair<int, int>>hole4;
deque<pair<int, int>>hole5;
 
 
void dir_set(){ // 방향 deque 저장
    for (int i = 0; i < 4; i++){
        x_mov.push_back(dx[i]);
        y_mov.push_back(dy[i]);
    }
}
 
void dir_modi(){ // 시작 방향 변경 함수(상하좌우 4방향)
    x_mov.push_back(x_mov.front());
    x_mov.pop_front();
    y_mov.push_back(x_mov.front());
    y_mov.pop_front();
}
 
bool crash_wall(int x, int y){
    if (x < 0 || y < 0 || x >= N || y >= N) // 맵 벽에 부딪히는 경우
        return true;
    return false;
}
 
void hole_change(int num){ // 자기 짝에 맞는 웜홀로 움직이게하는 함수
    switch (num)
    {
    case 6:
        hole1.push_back(hole1.front());
        hole1.pop_front();
        break;
    case 7:
        hole2.push_back(hole2.front());
        hole2.pop_front();
        break;
    case 8:
        hole3.push_back(hole3.front());
        hole3.pop_front();
        break;
    case 9:
        hole4.push_back(hole4.front());
        hole4.pop_front();
        break;
    case 10:
        hole5.push_back(hole5.front());
        hole5.pop_front();
        break;
    }
}
 
int play(int x, int y){
    int num = 0;
    int first_x = x;
    int first_y = y;
    int max_point = 0;
    for (int t = 0; t < 4; t++){ //4방향 탐색을 위한 반복문
        int point = 0;
        int cur_tmp_x = x_mov[t];
        int cur_tmp_y = y_mov[t];
        x = first_x;
        y = first_y;
        while (true){ //방향 하나당 끝날때까지 진행
            int ax = x + cur_tmp_x; // 해당 방향으로 전진
            int ay = y + cur_tmp_y; // 해당 방향으로 전진
            if ((ax == first_x && ay == first_y) || map[ax][ay] == -1){
                // 시작점을 돌아오거나 블랙홀을 만나면 종료
                if (point > max_point) // 최대 포인트 저장
                    max_point = point;
                break;
            }
            if (crash_wall(ax,ay) || map[ax][ay] == 5) // 맵 벽에 부딪히는 경우, 5번에 부딪히거나
            {
                // 부딪힌 방향의 반대로 감
                if (cur_tmp_x == 1 && cur_tmp_y == 0)
                    cur_tmp_x = -1;
                else if (cur_tmp_x == -1 && cur_tmp_y == 0)
                    cur_tmp_x = 1;
                else if (cur_tmp_x == 0 && cur_tmp_y == 1)
                    cur_tmp_y = -1;
                else if (cur_tmp_x == 0 && cur_tmp_y == -1)
                    cur_tmp_y = 1;
                point += 1; // 벽에 부딪혔으니 포인트 +1;
            }
 
            // 웜홀에 들어가는 경우
            else if (map[ax][ay]>5){
                if (map[ax][ay] == 6){
                    if (ax == hole1.front().first && ay == hole1.front().second)
                        hole_change(6);
                    ax = hole1.front().first;
                    ay = hole1.front().second;
                }
                else if (map[ax][ay] == 7){
                    if (ax == hole2.front().first && ay == hole2.front().second)
                        hole_change(7);
                    ax = hole2.front().first;
                    ay = hole2.front().second;
                }
                else if (map[ax][ay] == 8){
                    if (ax == hole3.front().first && ay == hole3.front().second)
                        hole_change(8);
                    ax = hole3.front().first;
                    ay = hole3.front().second;
                }
                else if (map[ax][ay] == 9){
                    if (ax == hole4.front().first && ay == hole4.front().second)
                        hole_change(9);
                    ax = hole4.front().first;
                    ay = hole4.front().second;
                }
                else if (map[ax][ay] == 10){
                    if (ax == hole5.front().first && ay == hole5.front().second)
                        hole_change(10);
                    ax = hole5.front().first;
                    ay = hole5.front().second;
                }
            }
 
            // 세모 모양 중 평면에 부딪히는 경우 
            else if ((map[ax][ay] == 1 || map[ax][ay] == 2) && (cur_tmp_x == 0 && cur_tmp_y == 1)){
                cur_tmp_x = 0;
                cur_tmp_y = -1;
                // 0, -1
                point += 1; // 벽에 부딪혔으니 포인트 +1;
            }
            else if ((map[ax][ay] == 1 || map[ax][ay] == 4) && (cur_tmp_x == -1 && cur_tmp_y == 0)){
                cur_tmp_x = 1;
                cur_tmp_y = 0;
                // 1, 0
                point += 1; // 벽에 부딪혔으니 포인트 +1;
            }
            else if ((map[ax][ay] == 2 || map[ax][ay] == 3) && (cur_tmp_x == 1 && cur_tmp_y == 0)){
                cur_tmp_x = -1;
                cur_tmp_y = 0;
                // -1, 0
                point += 1; // 벽에 부딪혔으니 포인트 +1;
            }
            else if ((map[ax][ay] == 3 || map[ax][ay] == 4) && (cur_tmp_x == 0 && cur_tmp_y == -1)){
                cur_tmp_x = 0;
                cur_tmp_y = 1;
                // 0, 1
                point += 1; // 벽에 부딪혔으니 포인트 +1;
            }
 
 
            // 세모모양 중 대각벽에 부딪히는 경우
            else if ((map[ax][ay] == 1 || map[ax][ay] == 2) && (cur_tmp_x == 1 || cur_tmp_x == -1) && cur_tmp_y == 0){ // 상, 하 => 우
                cur_tmp_x = 0;
                cur_tmp_y = 1;
                // 0, 1
                point += 1; // 벽에 부딪혔으니 포인트 +1;
            }
            else if ((map[ax][ay] == 1 || map[ax][ay] == 4) && cur_tmp_x == 0 && (cur_tmp_y == -1 || cur_tmp_y == 1)){ // 좌, 우 => 상
                cur_tmp_x = -1;
                cur_tmp_y = 0;
                // -1, 0
                point += 1; // 벽에 부딪혔으니 포인트 +1;
 
            }
            else if ((map[ax][ay] == 2 || map[ax][ay] == 3) && cur_tmp_x == 0 && (cur_tmp_y == -1 || cur_tmp_y == 1)){ // 좌, 우 => 하
                cur_tmp_x = 1;
                cur_tmp_y = 0;
                //1, 0
                point += 1; // 벽에 부딪혔으니 포인트 +1;
 
            }
            else if ((map[ax][ay] == 3 || map[ax][ay] == 4) && (cur_tmp_x == 1 || cur_tmp_x == -1) && cur_tmp_y == 0){// 상, 하 => 좌
                cur_tmp_x = 0;
                cur_tmp_y = -1;
                // 0, -1
                point += 1; // 벽에 부딪혔으니 포인트 +1;
            }
            x = ax, y = ay;
        }
    }
    return max_point;
}
 
void reset(){
    memset(map, 0, sizeof(map));
    x_mov.clear();
    y_mov.clear();
    hole1.clear();
    hole2.clear();
    hole3.clear();
    hole4.clear();
    hole5.clear();
}
int main() {
    freopen("5650.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        reset();
        deque<pair<int, int>>start;
        cin >> N;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                cin >> map[i][j];
                if (map[i][j]==0)
                    start.push_back(make_pair(i, j));
                else if (map[i][j] == 6)
                    hole1.push_back(make_pair(i, j));
                else if (map[i][j] == 7)
                    hole2.push_back(make_pair(i, j));
                else if (map[i][j] == 8)
                    hole3.push_back(make_pair(i, j));
                else if (map[i][j] == 9)
                    hole4.push_back(make_pair(i, j));
                else if (map[i][j] == 10)
                    hole5.push_back(make_pair(i, j));
            }
        }
        int start_pos = start.size(); // 공을 놓을 수 있는 위치
        dir_set();
        int answer = -777;
        for (int i = 0; i < start_pos; i++){
            answer = max(answer,play(start.front().first, start.front().second));
            start.pop_front();
        }
        cout << "#" << z << " " << answer << "\n";
    }
    return 0;
}

# 무식하게 푼 것 같지만... 풀긴 풀었으니까.. 조금 더 보완하면 되지 않을까??

  코드는 보다시피 줄일 수 있다. 보완할 점은 줄일 수 있는 코드를 줄이면서 코드를 짤 수 있는 설계능력인 것 같다..

 

---

 

< Code 설명 - 수정 >

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <algorithm>
#include <string.h>
#define MAX 101
 
using namespace std;
 
int T, N, ans;
int map[MAX][MAX];
 
int dx[5] = { 0, -1, 1, 0, 0 }; // 상하좌우
int dy[5] = { 0, 0, 0, -1, 1 };
 
struct holl{
    deque<pair<int, int>>d;
};
 
holl worm[11];
 
int reverse(int dir){ // 벽면을 만났을 때 -> 방향리턴
    if (dir == 1)
        return 2;
    else if (dir == 2)
        return 1;
    else if (dir == 3)
        return 4;
    else if (dir == 4)
        return 3;
}
 
int corner(int block, int dir){ // 대각면을 만났을때 -> 방향리턴
    if (block == 1){
        if (dir == 2)
            return 4;
        else if (dir == 3)
            return 1;
        else if (dir == 4 || dir == 1)
            return reverse(dir);
    }
    else if (block == 2){
        if (dir == 1)
            return 4;
        else if (dir == 3)
            return 2;
        else if (dir == 4 || dir == 2)
            return reverse(dir);
    }
    else if (block == 3){
        if (dir == 1)
            return 3;
        else if (dir == 4)
            return 2;
        else if (dir == 2 || dir == 3)
            return reverse(dir);
    }
    else if (block == 4){
        if (dir == 2)
            return 3;
        else if (dir == 4)
            return 1;
        else if (dir == 1 || dir == 3)
            return reverse(dir);
    }
    else if (block == 5)
        return reverse(dir);
    else
        return dir;
}
 
 
void search(int a, int b, int s_dir){
    int x, y, start_x, start_y, cnt, dir;
    start_x = x = a;
    start_y = y = b;
    dir = s_dir;
    cnt = 0;
    bool flag;
    while (true){
        flag = false;
        int ax = x + dx[dir];
        int ay = y + dy[dir];
        if ((ax == start_x && ay == start_y) || map[ax][ay] == -1){ // 시작좌표거나 블랙홀이면
            ans = max(ans, cnt);
            break;
        }
        if (ax < 0 || ay < 0 || ax >= N || ay >= N){ // 테두리 벽을 만나면
            dir = reverse(dir);
            cnt++;
            
        }
        else if (map[ax][ay] <= 5 && map[ax][ay] >= 1){ // 블록을 만나면
            dir = corner(map[ax][ay], dir);
            cnt++;
        }
 
        else if (map[ax][ay] >= 6){ // 웜홀을 만나면
            for (int i = 0; i < 2; i++){
                if (worm[map[ax][ay]].d[i].first != ax || worm[map[ax][ay]].d[i].second != ay){
                    x = worm[map[ax][ay]].d[i].first;
                    y = worm[map[ax][ay]].d[i].second;
                    flag = true;
                    break;
                }
            }
        }
        if (!flag){
            x = ax;
            y = ay;
        }
    }
}
void init(){
    memset(map, 0, sizeof(map));
    for (int i = 0; i <= 10; i++)
        worm[i].d.clear();
    ans = 0;
}
int main(){
    freopen("5650.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        cin >> N;
        init();
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                cin >> map[i][j];
                if (map[i][j] >= 6)
                    worm[map[i][j]].d.push_back(make_pair(i, j));
            }
        }
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                for (int dir = 1; dir <= 4; dir++){
                    if (map[i][j] == 0){
                        search(i, j, dir);
                    }
                }
            }
        }
        cout << "#" << z << " " << ans << endl;
    }
    return 0;
}