BOJ 1400

22 Apr 2020 • ProblemSolving

화물차

문제출처

문제 해석

  • 출발지에서 배송지까지 가는데 걸리는 최소 시간을 구하는 문제입니다.
  • 2차원 배열에 있는 0~9숫자는 신호등에 의해 제어되는 교차로를 나타냅니다.
  • 차량은 다음 조건에 따라 이동합니다.
    1. 화물차가 진입하려는 방향으로 파란불이 켜져 있을 때만 교차로로 들어갈 수 있습니다. 그러나 교차로에 들어간 차량은 언제든지 임의의 방향으로 나갈 수 있습니다
    2. 교차로의 신호등은 동서, 남북 방향 두개의 신호가 주기적으로 켜집니다.
      • 초기에 켜지는 방향은 정해지며, a와 b시간만큼 주기적으로 반복됩니다.

설계(20)

  • 뻘짓을 아주 많이 한 문제입니다.
  • 처음 생각했던 방식은 완전탐색 방식입니다.
  • 교차로의 신호등의 주기에 따라서 갈지 그대로 멈춰있을지 정해줍니다.
  • 남북방향이 먼저 시작하는 주기와 동서방향이 먼저 시작하는 주기를 나누어서 구현하였습니다.
  • 또한, 위의 조건안에서 같은 방향으로 보고있는지 체크한 후 아니면 그대로 멈춰있습니다.
  • 위의 방식으로 구현하니 시간초과가 났습니다..
  • 그 후 든 생각은 구현이 잘못되었다기보다는 완전탐색으로 구현을 할 수 없는 문제라고 생각했습니다.
  • 이후, 뻘짓은 시작되었습니다.. 다익스트라 알고리즘으로 변경하였습니다.
  • 만약 교차로가 나오면, 해당 교차로를 건널 수 있는 최단시간을 계산해주어 더해주는 방식으로 진행하였습니다.
  • 그러나, 배열 체크를 boolean 형태로 해서 잘못된 답을 도출했습니다.
  • 그러다가, 처음 작성했던 코드를 다시 보니 교차로 건널 때 방문체크를 안해준 것을 확인하였습니다.
  • 결국, 구현이 잘못되어서 발생한 오류였습니다.
  • 추가로, 다익스트라 알고리즘을 사용할 때 dist배열로 변경해서 최소값을 갱신시키는 방식으로 구현하면 답을 도출할 수 있을 것 같습니다.

구현(60)

코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 21

char map[MAXN][MAXN];
int N,M;

int sx,sy,ex,ey;
struct node{
    int flag,a,b;
};
queue<pair<int,int> > q;
node num[10];
int len;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int bfs(){
    while (!q.empty()) q.pop();
    bool visited[MAXN][MAXN]={false,};
    q.push({sx,sy});
    visited[sx][sy] = true;
    int time = 0 ;
    while (!q.empty()){
        int q_size = q.size();
        while (q_size--){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (x == ex && y == ey) return time;
            for (int k =0 ; k<4 ; k++){
                int nx = x +dx[k];
                int ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx>=N || ny>=M || visited[nx][ny] || map[nx][ny]=='.') continue;
                if (map[nx][ny]>='0'&& map[nx][ny]<='9'){
                    int idx = map[nx][ny]-'0';
                    int next_time = time+1;
                    if (next_time%(num[idx].a+num[idx].b)) next_time %=(num[idx].a+num[idx].b);
                    // 남북부터 시작하는 주기
                    if (num[idx].flag){
                        // 남북 신호등 켜지는 주기
                        if (next_time <= num[idx].b && k>=2){
                            visited[nx][ny] = true;
                            q.push({nx,ny});
                        }
                        // 동서 신호등 켜지는 주기
                        else if (next_time>num[idx].b && k < 2){
                            visited[nx][ny] = true;
                            q.push({nx,ny});

                        }
                        else q.push({x,y});
                    }
                    // 동서부터 시작하는 주기
                    else{
                        if ((next_time <= num[idx].a && k<2) || (next_time>num[idx].a&& k>=2)) {
                            visited[nx][ny] = true;
                            q.push({nx,ny});
                        }
                        else q.push({x,y});
                    }
                }
                else{
                    visited[nx][ny]=true;
                    q.push({nx,ny});
                }
            }
        }
        time++;
    }
    return -1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (1){
        len = 0;
        cin >> N >> M;
        if (N ==0 && M ==0) break;
        for (int i = 0 ;i<N; i++){
            cin >> map[i];
            for (int j = 0;j<M;j++){
                if (map[i][j] == 'A') {
                    sx =i, sy= j;
                    map[i][j] ='#';
                }
                else if (map[i][j] == 'B') {
                    ex= i , ey= j;
                    map[i][j] ='#';
                }
                else if (map[i][j] >='0' && map[i][j]<='9') len++;
            }
        }
        for (int i = 0; i< len; i++){
            char tmp;
            int tmp_num,a,b;
            cin >> tmp_num >> tmp >> a >> b;
            if (tmp =='-') num[i] = {0,a,b};
            else num[i] = {1,a,b};
        }
        int ans = bfs();
        if (ans != -1)cout << ans <<"\n";
        else cout <<"impossible\n";
    }
    return 0;
}
디버깅
제출결과
  • 0 ms

마무리

  • 간단한 문제였는데 너무 돌아가서 꼬여버린 문제였습니다.
  • 신호등이 어떤 방향부터 시작하는지에 따라서 주기의 범위가 달라지기 때문에, 이를 주의해서 구현해야합니다.
 BOJ

Related Posts