[백준][C++] 16137 견우와 직녀

www.acmicpc.net/problem/16137

16137번: 견우와 직녀

 

 

 

알고리즘 종류

    - 구현

    - BFS

 

 

 

사고 과정

    - 조건을 다음과 같다.

        * 오작교 조건

            1. 1분 동안 유지

            2. 주기대로 생성

            3. 교차 절벽에 생성 금지

            4. 이미 생성된 절벽에 오작교 겹쳐서 생성 금지

 

        * 다리 건너는 조건

            1. 오작교가 M주기로 생성될 때, 견우는 오작교 주변에서  M-1시간이어야 한다. (본인은 이 조건이 이해가 안되서 고생했다. 마치, 건너기 전에 다리가 생성되었는지 모르고 있다가 건너기 위해서 발을 놓는 순간 다리가 생성되는 느낌...? 으로 상상해봤다.)

            2. 2번 연속 오작교를 건널 수 없다.

            3. 다리가 생성될 때까지 제자리에서 기다릴 수 있다.

 

    - 위 조건들을 생각해보면, 본인은 아래와 같은 생각을 했다.

        * 보통 isVisited로 재방문 금지하고, 첫 방문이면 바로 체크해왔지만, 여기에서는 제자리에서 대기하는 경우가 있기 때문에 isVisited를 바로 체크하지 않는다.

        * Queue에 넣을 변수들은 현재 위치, 시간, 다리 건넌 여부가 될 것이다.

 

 

 

구현(C++)

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define MAX 987654321
 
using namespace std;
 
int n, m;
int ans = MAX;
 
int mat[11][11];
int isVisited[11][11];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
vector<pair<int, int> > bridges;
 
 
bool is_valid(int y, int x){
    return (y>=0 && y<n) && (x>=0 && x<n);
}
 
// 교차 절벽인지 확인  
bool is_avail(int y, int x){
    if(is_valid(y+1, x) && is_valid(y, x+1) && mat[y+1][x]==0 && mat[y][x+1]==0) return false;
    if(is_valid(y, x+1) && is_valid(y-1, x) && mat[y][x+1]==0 && mat[y-1][x]==0) return false;
    if(is_valid(y-1, x) && is_valid(y, x-1) && mat[y-1][x]==0 && mat[y][x-1]==0) return false;
    if(is_valid(y, x-1) && is_valid(y+1, x) && mat[y][x-1]==0 && mat[y+1][x]==0) return false;
    return true;
}
 
 
void bfs(){
    memset(isVisited, 0, sizeof(isVisited));
    queue<pair<pair<int, int>, pair<int, int> > > q; // y, x, time, crossed
    q.push({{0,0}, {0,0}});
    isVisited[0][0] = 1;
    
    while(!q.empty()){
        int cy = q.front().first.first;
        int cx = q.front().first.second;
        int ct = q.front().second.first;
        int flag = q.front().second.second;
        q.pop();
        
        for(int d=0; d<4; d++){
            int ny = cy + dir[d][0];
            int nx = cx + dir[d][1];
            
            // 종 료  
            if(ny==n-1 && nx==n-1){
                ans = min(ans, ct+1);
                return;
            }
            
            if(!is_valid(ny, nx)) continue;
            if(isVisited[ny][nx]) continue;
            
            // 절벽이면 무시한다. 
            if(mat[ny][nx]==0) continue;
            // 일반 땅이면 그냥 간다. 
            else if(mat[ny][nx]==1){
                isVisited[ny][nx] = 1;
                q.push({{ny, nx}, {ct+1, 0}});
            }
            // 오작교가 만들어질 곳이면 이전에 오작교를 건넜는지 확인한다. 
            else if(mat[ny][nx]>=2 && !flag){
                if((ct+1) % mat[ny][nx] == 0){ // 지금 시간이 오작교 생성시간이라면 건넌다. 
                    isVisited[ny][nx] = 1;
                    q.push({{ny, nx}, {ct+1, 1}});
                }
                else{// 오작교 생성시간이 아니라면 기다려본다. 더 빠르게 갈 수도 있다. 
                    q.push({{cy, cx}, {ct+1, 0}});
                }
            }
        }
        
        
    }
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> mat[i][j];
        }
    }
    
    // 교차되는 절벽을 제외한 절벽들 찾기  
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(mat[i][j] == 0 && is_avail(i, j)) 
                bridges.push_back({i, j}); 
        }
    }
    
    // 절벽 하나 하나에 오작교 놓아보기  
    for(int i=0; i<bridges.size(); i++){
        mat[bridges[i].first][bridges[i].second] = m;
        bfs();
        mat[bridges[i].first][bridges[i].second] = 0;
    }
    
    cout << ans << endl;
}

 

 

 

시행착오

    - 절벽 교차되는 지점을 찾기 위한 방법을 최대한 간단하게 구현하려고 온갖 방법을 생각해 보았다. 시간 많이 잡아먹었다. 역시나 직관적으로 해석이 가능한 구현하는 것이 가장 먼저인 것 같다.

    - 시간 문제를 때때로 곤혹스럽다. 이번에도 그랬다. 오작교 생성이 5분마다 된다고 하면, 주변에 4분에는 와 있어야 한다. 이렇게 한글로 예시를 들어 설명하면 자명한 것 같지만, 본인은 문제 풀이에서 난해함을 느꼈다... (나만 그런가...?) 오작교가 놓일 곳에 발을 놓기 위한 인식 단계에는 오작교가 없어도 되지만, 발을 놓는 순간에 오작교는 있어야 한다. 라고 해석했다. 각설하고, 문제 내에서는 M-1에 주변에 있어야 한다는 것이다.