Gidhub BE Developer

[SW Expert Academy] 2105. 디저트 카페

2018-09-06
goodGid
Algorithm

Problem

Problem URL : 디저트 카페

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

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

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

int map[20][20];
int value[101];

int n;
int ans;

int st_x;
int st_y;

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

/*
 북동 북서 남서 남동 방향으로 순회
 북동방향으로 진행 a++
 남서방향으로 진행 a--
 
 북서방향으로 진행 b++
 남동방향으로 진행 b--
 */
void dfs(int x, int y, int a, int b, int cnt, int dir_idx){
    if( a == 0 && b == 0){
        ans = ans < cnt ? cnt : ans;
        return ;
    }
    
    // Same Direction
    value[ map[x][y] ] = 1;
    int nx = x + dx[dir_idx];
    int ny = y + dy[dir_idx];
    if( st_x == nx && st_y == ny){
        dfs(nx,ny,a,b-1,cnt+1,dir_idx);
    }
    else if( inRange(nx, ny) && value[ map[nx][ny] ] == 0){
        if(dir_idx == 0) dfs(nx,ny,a+1,b,cnt+1,dir_idx);
        else if(dir_idx == 1) dfs(nx,ny,a,b+1,cnt+1,dir_idx);
        else if(dir_idx == 2) dfs(nx,ny,a-1,b,cnt+1,dir_idx);
        else if(dir_idx == 3) dfs(nx,ny,a,b-1,cnt+1,dir_idx);
        
    }
    
    // [1]
    value[map[x][y]] = 0;
    if (dir_idx == 3) return;
    value[map[x][y]] = 1;
    
    // Turn Direction
    dir_idx = ( dir_idx + 1 ) % 4;
    nx = x + dx[dir_idx];
    ny = y + dy[dir_idx];
    if( st_x == nx && st_y == ny){
        dfs(nx,ny,a,b-1,cnt+1,dir_idx);
    }
    else if( inRange(nx, ny) && value[ map[nx][ny] ] == 0){
        if(dir_idx == 0) dfs(nx,ny,a+1,b,cnt+1,dir_idx);
        else if(dir_idx == 1) dfs(nx,ny,a,b+1,cnt+1,dir_idx);
        else if(dir_idx == 2) dfs(nx,ny,a-1,b,cnt+1,dir_idx);
        else if(dir_idx == 3) dfs(nx,ny,a,b-1,cnt+1,dir_idx);
    }
    
    value[ map[x][y] ] = 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        ans = -1;
        cin >> n;
        
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin >> map[i][j];
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                value[ map[i][j] ] = 1;
                int nx = i + dx[0];
                int ny = j + dy[0];
                if( inRange(nx, ny) && value[ map[nx][ny] ] == 0){
                    st_x = i;
                    st_y = j;
                    dfs(nx,ny,1,0,1,0);
                }
                value[ map[i][j] ] = 0;
            }
        }

        cout << "#" << tc << " " << ans << endl;
    }
    return 0;
}

Review

  • 쉬워보이는데 생각보다 까다로운 문제다.

  • [1]코드없이 테스트를 해보니 TC 9,10번째가 틀렸다.

  • 만약 [1]코드가 없다면 다음과 같은 경우에 이상한 값을 출력할 가능성이 생긴다.

5
9  9  9  1  9
9  9  2  9  3
9  4  9 *9* 9
9  9  6  9  7
9  9  9  8  9

  • 맵의 인덱스를 (1,1) ~ (5,5)라고 볼 때
    (3,4)의 값 9에서 시작하면 9 -> 7 -> 8 -> 6 -> 4 -> 2 -> 1 -> 3로 순회가 가능하다.

  • 그런데 이런식의 순회는 답이 될 수 없다.

  • 그래서 이런 상황을 방지해야한다.

  • 해결방법은 다음과 같다.

  • (3,4)에서 시작했고 순회를 하면서 방향이 남서(=3)가 될 때는 Turn Direction을 할 필요가 없다.

  • Why? 남서 방향은 탐색한다는건 최종적으로 체크를 위한 방향이다. 그렇기 때문에 Trun을 한다는건 말이 안된다.

  • 그래서 [1]코드를 추가해줘야 9 -> 7 -> 8 -> 6 -> 4 -> 2 -> 1 -> 3같은 경우를 방지 할 수 있다.

  • 즉 9 -> 7 -> 8 -> 6 -> 4 에서 2를 탐색하지 않고 Return 시킨다.

  • 전체적으로 코드가 깔끔한 느낌이 들지 않는다.

[2] Answer Code (18. 09. 06)

#include<iostream>
#include<cstring>
using namespace std;

int dx[] = {1,1,-1,-1};
int dy[] = {1,-1,-1,1};

int n,ans;
int map[20][20];
int visit[20][20];
int st_x,st_y;

int value_use[101];
int dept_cnt[4];

bool chk(){
    for(int i=0; i<4; i++)
        if(! dept_cnt[i] )
            return false;
    return true;
}

void dfs(int x, int y, int dir_idx, int dept){
    if( x == -1 || x == n || y == -1 || y == n )
        return ;
    if(visit[x][y] == 1 ){
        if( chk() && st_x == x && st_y == y)
            ans = ans > dept - 1 ? ans : dept - 1;
        return ;
    }
    if( value_use[ map[x][y] ] == 1)
        return ;
    
    
    value_use[ map[x][y] ] = 1;
    visit[x][y] = 1;
    for(int i=dir_idx; i<4; i++){
        dept_cnt[i] ++;
        int nx = x + dx[i];
        int ny = y + dy[i];
        dfs(nx,ny,i,dept+1);
        dept_cnt[i] --;
    }
    value_use[ map[x][y] ] = 0;
    visit[x][y] = 0;
}

int main(){
    int TC;
    cin >> TC;
    for (int tc=1; tc<=TC; tc++) {
        ans = -1;
        memset(map,0,sizeof(map));
        memset(visit,0,sizeof(visit));
        cin >> n;
        
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&map[i][j]);
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                st_x = i;
                st_y = j;
                dfs(i,j,0,1);
            }
        }
    
        printf("#%d %d\n",tc, ans);
    } // end of for tc
    return 0;
}

Review

  • 2시간이 걸렸다. 화가난다.

  • 처음엔 로직을 잘못구현했고 그 다음엔 방향성 체크하는데 시간이 많이 소요됐다.

  • 그리고 방향성 제어를 0부터 3까지 순서로 고정하였기 때문에
    ( 즉 0방향 -> 1방향 -> 2방향 -> 3방향으로 탐색하기 때문에 같은 방향에 대해 재탐색 할 수 있는 경우를 처리해줄 필요가 X )
    dir_idx == 3일 때 종료가 되겠구나 생각했는데
    그렇게 되면 [0,1] -> [1,0] -> [0,1]로 돌아왔을 경우 ans를 초기화하는 문제가 발생하였다.
    원래는 불가능한 상황이지만, 코드상 visit을 하였고 시작점 좌표랑 같기 때문에 일어나는 문제였다.
    그 문제를 해결하기 위해 dept_cnt라는 배열을 선언하여 각각 방향으로의 움직임을 카운팅하여
    최종적으로 ans를 초기화해주기전에 모든 방향에 대해 적어도 1번씩은 움직였는지 체크하여 위 문제를 해결하였다.

  • 방향 전환 부분은 아래 코드와 같이
    i=dir_idx를 넣고 다음 dfs에 i값을 넘겨줌으로써 방향성 체크를 하였다.
    그렇게 되면 0 -> 3 순서를 유지한 상태로 현재 방향이 i=1이였다면 2번 방향으로 움직이게 된다.
    즉, 기존에 움직였던 방향에 대해서는 신경쓰지 않아도 된다.

for(int i=dir_idx; i<4; i++){
        dept_cnt[i] ++;
        int nx = x + dx[i];
        int ny = y + dy[i];
        dfs(nx,ny,i,dept+1);
        dept_cnt[i] --;
    }

[3] Answer Code (18. 04. 02)


#include<iostream>
#include<cstring>
using namespace std;

struct Node{
    int x;
    int y;
};

int n;
int ans;
int map[21][21];
int visit[21][21];
int num[101];
int dx[] = {0,1,1,-1,-1};
int dy[] = {0,1,-1,-1,1};
Node stNode;

void dfs(int x, int y, int depth, int dir){ // dir is direction
    if(depth != 0 && stNode.x == x){
        if(stNode.y == y){
            ans = ans < depth ? depth : ans;
            return ;
        }
        else{
            return ;
        }
    }
    if(! (x > 0 && x <= n && y > 0 && y <=n))
        return ;
    if(visit[x][y]) return ;
    
    visit[x][y] = 1;
    num[ map[x][y] ] = 1 ;
    
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    
    for(int i=dir; i<=4; i++){
        // if( (dir == 1 && i == 3) || (dir == 2 && i == 4) )
        if( (dir == 1 && i == 3) || (dir == 2 && i == 4)
           || (dir == 3 && i == 1) || (dir == 4 && i == 2) )
            continue;
        nx = x + dx[i];
        ny = y + dy[i];
        if( (!num[ map[nx][ny] ]) || (nx == stNode.x && ny == stNode.y))
            dfs(nx, ny, depth + 1, i);
    }
    num[ map[x][y] ] = 0 ;
    visit[x][y] = 0;
    
}

int main(){
    int t;
    cin >> t;
    
    for(int i=1; i<=t; i++){
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        ans = -1;
        cin >> n;
        
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d",&map[i][j]);
 
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                stNode.x = i;
                stNode.y = j;
                dfs(i, j, 0, 1);
            }
        } // End of for Loop

        printf("#%d %d\n",i,ans);
    } // End of 't' for Loop
    return 0;
}

Review

  • 문제를 읽자마자 DFS가 생각났다.

  • 북동과 남서의 Depth값이 같아야하며,
    북서와 남동의 Depth값이 같게 해야하는데
    이런 방향성에 대한 로직을 고민하는데 많은 시간이 들었다.

Index