Gidhub BE Developer

[SW Expert Academy] 5650. 핀볼 게임

2018-10-14
goodGid

Problem

Problem URL : 핀볼 게임


[1] Answer Code (18. 10. 20)

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
#define p pair<int,int>
using namespace std;

// 동 서 남 북
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

/*
 (1,1)에서 동쪽(= 0)방향을 보고 있는데
 (1,2)가 1번 모양이다.
 
 그러면 (1,2)에서 진행해야하는 방향은 이제 서쪽(= 1)이 되야한다.
 이걸 코드로 표현하면
 changeDir[ i번 모양 ][ 현재 진행중 방향 ] // i번 모양 = 다음 위치에 있는 모양의 번호
 changeDir[ 1 ][ 0 ] = 1;
 */
int changeDir[6][4] = {
    {0,0,0,0}, // 빈 칸
    {1,3,0,2}, // 1번 모양
    {1,2,3,0}, // 2번 모양
    {2,0,3,1}, // 3번 모양
    {3,0,1,2}, // 4번 모양
    {1,0,3,2} // 5번 모양
};

int maze[100][100];
int n;
int ans;

map<int,p> m;

bool inRange(int x, int y){
    if(x < 0 || x >=n || y < 0 || y >= n)
        return false;
    return true;
}

int solve(int x, int y, int dir){
    int cnt = 0;
    
    int st_x = x;
    int st_y = y;
    
    int nx = x;
    int ny = y;
    
    while (1) {
        nx += dx[dir];
        ny += dy[dir];
        
        if(! inRange(nx, ny)) { // Map을 벗어났다 = 방향 전환
            cnt++;
            /*
             if ~ else if 구조가 아니면
             if(dir == 0)에서 dir가 1로 바뀌고
             if(dir == 1)에서 dir가 다시 0으로 바뀌는 대참사가 발생한다.
             */
            if(dir == 0) dir = 1;
            else if(dir == 1) dir = 0;
            else if(dir == 2) dir = 3;
            else if(dir == 3) dir = 2;
            
            /*
             만약 (-1,0)이 됐는데
             continue가 없으면
             그 아래 if 문에서
             maze[-1][0]이 되는 대참사가 발생한다.
             그렇기 때문에 반드시 continue가 필요하다.
             */
            continue;
        }
        
        // 종료 : 블랙홀 or 시작점
        if( maze[nx][ny] == -1 || (nx == st_x && ny == st_y) ){
            break;
        }
        
        // 블록을 만날 경우
        if( maze[nx][ny] >= 1 && maze[nx][ny] <=5 ){
            cnt++;
            dir = changeDir[ maze[nx][ny] ][dir];
        }
        
        // 웜홀을 만날 경우
        if( maze[nx][ny] >= 6 && maze[nx][ny] <= 10){
            int tmp_x;
            int tmp_y;
            /*
             ## 주의
             [1] : nx = m[ maze[nx][ny] * 2].first;
             [2] : ny = m[ maze[nx][ny] * 2].second;
             이렇게 하면
             nx = 1
             ny = 1 이라고하면
             [1]은 정상적인 값이 불러 오지만
             [2]에 들어가는 nx 값은 1이 아니라 다른 값이 들어갈 수 있다.
             
             그래서 tmp_x, tmp_y에 값을 저장하고
             nx = tmp_x
             ny = tmp_y 작업을 해준다.
             */
            if( m[ maze[nx][ny] ].first == nx && m[ maze[nx][ny] ].second == ny){
                tmp_x = m[ maze[nx][ny] * 2].first;
                tmp_y = m[ maze[nx][ny] * 2].second;
            }
            else{
                tmp_x = m[ maze[nx][ny] ].first;
                tmp_y = m[ maze[nx][ny] ].second;
            }
            nx = tmp_x;
            ny = tmp_y;
        }
    }
    return cnt;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(maze,0,sizeof(maze));
        m.clear();
        ans = -1;
        cin >> n;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> maze[i][j];
                if(maze[i][j] >= 6 && maze[i][j] <= 10){
                    if(m.find(maze[i][j]) != m.end()){ // 이미 있는 경우
                        m[ maze[i][j] * 2 ] = m[ maze[i][j] ];
                        m[ maze[i][j] ] = p(i,j);
                    }
                    else{
                        m[ maze[i][j] ] = p(i,j);
                    }
                }
            }
        }
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(maze[i][j] == 0){
                    for(int k=0; k<4; k++){
                        int _ans = solve(i,j,k);
                        ans = ans < _ans ? _ans : ans;
                    } // end of for k
                } // end of if
            } // end of for j
        } // end of for i
        
        
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}

Reivew

  • 55분 소요

  • 다시 푸는 문제였지만 후다닥 코딩은 실패했다.

  • 그래도 큰 문제없이 해결했다.

  • 신기한점은 예전에 풀었을 때 실수했던 부분을 똑같이 실수했다.


[2] Answer Code (18. 10. 14)

#include<iostream>
#include<map>
#define p pair<int,int>
using namespace std;

// 동서남북 순서
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int changeDir[6][4] ={
    {0,0,0,0}, // 빈칸
    {1,3,0,2},
    {1,2,3,0},
    {2,0,3,1},
    {3,0,1,2},
    {1,0,3,2}
};
int maze[100][100];
int n;

map<int,p> m;

bool inRange(int x, int y){
    if( x < 0 || x >= n || y < 0 || y >= n)
        return false;
    return true;
}

int dfs(int x, int y, int dir){
    int st_x = x;
    int st_y = y;
    int cnt = 0;
    
    while (1) {
        x = x + dx[dir];
        y = y + dy[dir];
        
        if(! inRange(x,y)){ // 범위 밖
            dir = changeDir[5][dir];
            cnt++;
        }
        else if(maze[x][y] == -1 || (x == st_x && y == st_y)){ // 블랙홀 or 시작점
            return cnt;
        }
        else if(maze[x][y] == 0){ // 빈 공간
            continue;
        }
        else if(maze[x][y] >= 1 && maze[x][y] <= 5){ // 벽일 경우
            dir = changeDir[ maze[x][y] ][ dir ];
            cnt++;
        }
        else{ // 웜홀일 경우
            int tmp_x;
            int tmp_y;
            if( m[ maze[x][y] ] == p(x,y) ){
                tmp_x = m[ maze[x][y] * 2 ].first;
                tmp_y = m[ maze[x][y] * 2 ].second;
            }
            else{
                tmp_x = m[ maze[x][y] ].first;
                tmp_y = m[ maze[x][y] ].second;
            }
            x = tmp_x;
            y = tmp_y;
        }
    } // end of while
    return cnt;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        int ans = -1;
        cin >> n;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> maze[i][j];
                if( maze[i][j] >= 6 && maze[i][j] <= 10){
                    if(m.find(maze[i][j]) != m.end()){ // 이미 웜홀 짝이 존재하는 경우
                        p pair_pos = m[ maze[i][j] ];
                        m[ maze[i][j] * 2 ] = pair_pos;
                        m[ maze[i][j] ] = p(i,j);
                    }
                    else{
                        m[ maze[i][j] ] = p(i,j);
                    }
                }
            }
        }
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(maze[i][j] == 0){
                    for(int k=0; k<4; k++){ // 동서남북 방향 순서로 탐색
                        cout << i << " " << j << " " << k << endl;
                        int res = dfs(i,j,k);
                        ans = ans < res ? res : ans;
                    }
                }
            }
        }
        
        cout << "#" << tc << " " << ans << '\n';
    }
    
    return 0;
}

Review

  • 어려웠다.

  • 대칭으로 저장하는 작업이 생각보다 오래 걸렸다.

  • 혼자서 해결하지 못하고 AC 코드를 보고 다시 풀었다.

  • 내가 처음에 생각했던 구현보다 깔끔하고 명료해서 좋았다.

  • 특히 방향에 대해서 한번에 표현하는 스킬이 신선했다.

int changeDir[6][4] ={
    {0,0,0,0}, // 빈칸
    {1,3,0,2},
    {1,2,3,0},
    {2,0,3,1},
    {3,0,1,2},
    {1,0,3,2}
};
  • 처음에 생각했던 구현 방식에서 벽을 만나면 바로 좌표를 이동시켰는데 문제가 발생했다.
/*
    ## dir
    0 : Right
    1 : Bottom
    2 : Left
    3 : Top
    */
if(arr[nx][ny] == 1){
    if(dir == 1)
        return Node(nx,ny+1,0);
    else if(dir == 2)
        return Node(nx-1,ny,3);
    else
        return Node(nx,ny,changeDir[dir]);
}
111
000
000
  • 위 처럼 있다면 (1,0)에서 시작하여 위로 가면 좌표를 바로 (0,2) 이동시키며 방향 또한 오른쪾으로 전환시킨다.

  • 그러면 (0,2)에서 오른쪽으로 진행하는 경우로 인식하여 틀리게 되었다.

  • 원래대로라면 (1,0) -> (0,0) -> (0,1) -> (0,0)으로 이동해야 하기 때문이다.

  • 또다른 실수로는 웜홀에 빠져 다른 웜홀로 나오는 작업 부분에서 다음과 같이 코딩을 하였다.

if( m[ maze[x][y] ] == p(x,y) ){
    x = m[ maze[x][y] * 2 ].first;
    y = m[ maze[x][y] * 2 ].second;
}
  • 이 때 내가 시작한 좌표가 (1,1)이라면 x와 y에는 각각 1이 들어가야한다.

  • 하지만 위처럼 했을 경우에 x는 m[ maze[x][y] * 2 ].first 값에 따라 바뀌게 되고
    그로인해 m[ maze[x][y] * 2 ].second 에서 x는 1이 아닌 이상한 값이 들어가게 된다.

  • 정상적으로 구현하기 위해선 다음과 같이 하면 된다.

int tmp_x;
int tmp_y;
if( m[ maze[x][y] ] == p(x,y) ){
    tmp_x = m[ maze[x][y] * 2 ].first;
    tmp_y = m[ maze[x][y] * 2 ].second;
}
else{
    tmp_x = m[ maze[x][y] ].first;
    tmp_y = m[ maze[x][y] ].second;
}
x = tmp_x;
y = tmp_y;

Comments

Content