[백준][C++] 1400 화물차

www.acmicpc.net/problem/1400

1400번: 화물차

 

 

 

알고리즘 종류

    - 구현

    - BFS

 

 

 

사고 과정

    - 이동 조건

        * 차량은 이동하거나 제자리에 머물기 가능

        * 교차로에 진입할 때, 이동가능한 방향일 때만 이동 가능

 

    - 신호등

        * 남북 또는 서동 방향으로 주기적으로 신호등이 변함

 

    - 위 조건을 보고 생각한 내용

        * Queue의 사이즈로 while문을 돌려서 시간을 더해가자

        * Queue에는 위치 y, x만 넣자

        * 신호등을 만났을 때 처리할 배열은 states로 하고 이 배열에 현재 시간일 때에 신호등 상태를 저장한다.

 

    - 그림으로 설명하면,

        * 시작 상태

        * 이동 시작

        * 아래 빨간색 화살표는 교차로에 진입할 수 없어서 제자리에 대기한다.

        * 아래 빨간색 화살표는 교차로에 진입하지 못해서 대기한다.

        * 아래 대기하던 파란색 화살표는 신호등이 진입 가능한 상태임으로 이동한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define MAX 987654321
 
using namespace std;
 
struct State{
    char state;
    int time;
};
 
int h, w, k;
int ay, ax, by, bx;
 
char mat[21][21];
int isVisited[21][21];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
vector<pair<char, pair<int, int> > > lights; // 시작 방향, 동서 유지 시간, 남북 유지 시간  
vector<State> states;
 
 
bool is_valid(int y, int x){
    return (y>=0 && y<h) && (x>=0 && x<w);
} 
 
// 신호등 상태 변환  
void change_lights(){
    
    for(int i=0; i<states.size(); i++){
        char state = states[i].state;
        int time = states[i].time -1;
        
        if(time==0){
            if(state=='-'){
                states[i].state = '|';
                states[i].time = lights[i].second.second;
            }else if(state=='|'){
                states[i].state = '-';
                states[i].time = lights[i].second.first;
            }
        }
        else states[i].time = time;
    }
}
 
 
int bfs(){
    
    queue<pair<int, int> > q;
    q.push({ay, ax});
    isVisited[ay][ax] = 1;
    int time=0;
    
    while(!q.empty()){
        
        int size = q.size();
        while(size--){
            int cy = q.front().first;
            int cx = q.front().second;
            q.pop();
            
            for(int d=0; d<4; d++){
                int ny = cy + dir[d][0];
                int nx = cx + dir[d][1];
                
                if(ny==by && nx==bx) return time+1;
                
                if(isVisited[ny][nx]) continue;
                if(!is_valid(ny, nx)) continue;
                if(mat[ny][nx] == '.') continue;
                
                // 일반 도로이면 그냥 전진  
                if(mat[ny][nx] == '#'){
                    isVisited[ny][nx] = 1;
                    q.push({ny, nx});
                }
                // 교차로의 신호등이면 
                else if(mat[ny][nx] >= '0' && mat[ny][nx] <= '9'){
                    int light = mat[ny][nx] - '0';
                    int state = states[light].state;
                    
                    // 모양과 맞는지 확인하고 맞으면 전진, 그렇지 않으면 제자리에서 대기  
                    if(state=='-'){
                        if(d==1 || d==3){
                            isVisited[ny][nx] = 1;
                            q.push({ny, nx});
                        }
                        else q.push({cy, cx});
                    }
                    else if(state=='|'){
                        if(d==0 || d==2){
                            isVisited[ny][nx] = 1;
                            q.push({ny, nx});
                        }
                        else q.push({cy, cx});
                    }
                }
            }
        }
        
        time++;
        change_lights(); // 신호등 변환  
    }
    return MAX;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    while(true){
        lights.clear();
        states.clear();
        memset(isVisited, 0, sizeof(isVisited));
        k=-1;
        
        cin >> h >> w;
        if(h==0 && w==0) break;
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                cin >> mat[i][j];
                if(mat[i][j] >= '0' && mat[i][j] <= '9'){
                    k = max(k, mat[i][j]-'0');
                }
                
                if(mat[i][j] == 'A'){
                    ay = i;
                    ax = j;
                }
                
                if(mat[i][j] == 'B'){
                    by = i;
                    bx = j;
                }
            }
        }
        
        // 신호등이 있으면, 정보를 저장한다. 
        if(k!=-1){
            int a,b,c;
            char d;
            
            for(int i=0; i<=k; i++){
                cin >> a >> d >> b >> c;
                lights.push_back({d, {b, c}}); // 방향, -시간, |시간  
                
                // 초기 신호등 상태 저장  
                State s;
                s.state = d;
                if(d=='-') s.time = b;
                else if(d=='|') s.time = c;
                states.push_back(s);
            }
        }
        
        int res = bfs();
        if(res == MAX) cout << "impossible" << endl;
        else cout << res << endl;
    }
}

 

 

 

시행착오