[백준 19238][C++] 스타트 택시

문제

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

풀이 과정

1. 입력받은 모든 정보를 저장

2. 입력받은 좌표를 기준으로 입력받은 위치에서의 각 칸의 최단거리를 구하는 함수를 구현 (BFS 알고리즘 이용)

3. 문제 조건에 맞게 가장 짧은 승객을 태우고, 운행하는 함수를 작성한다.

4. 3번 함수를 수행하고 택시를 이용한 승객이 입력받은 승객의 수보다 적다면 -1을 출력하고, 모두 이용했다면 현재 연료를 출력한다.

 

 

세부 풀이

(1) Input 함수

주어지는 좌표 값이 1부터 시작하는 것을 고려하여 배열에 정보를 입력한다.

 

문제의 조건 중 "백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다."을 만족시키기 위해 매번 승객의 좌표를 기준으로 탐색하는 방법 대신 승객을 행, 열을 기준으로 정렬하는 방식을 생각했다.

 

입력받은 승객의 출발지 도착지 정보에 대한 값을 행, 열을 기준으로 정렬한다. BFS를 이용하여 각 칸의 최단거리를 구한 뒤, 저장되어 있는 순서대로 승객의 출발지 좌표의 값을 비교하며 작은 경우에만 최솟값을 업데이트하도록 구현했다.

 

만약 최단거리가 같은 경우가 여러 개 있다고 하더라도 행과 열을 기준으로 이미 정렬된 순서로 탐색했기 때문에 최솟값으로 기록되었던 값은 같은 최단거리들 중 제일 빠른 행 열의 값을 가지게 된다.

 

(2) BFS 함수

BFS 알고리즘을 적용하여 각 칸의 벽을 고려하여 인접한 칸을 탐색하며 최단 거리를 저장한다.

이때 방문되지 않은 칸은 0의 값으로 남아있게 된다.

 

(3) search 함수 / solve 함수

해당 함수 구현에서 제일 중요하다고 생각하는 내용은 최단 거리 탐색 후 최단 거리가 0인 경우는 2가지가 존재할 수 있다는 점이다.

최단 거리를 탐색하였을 때, 각 좌표의 값이 0이라는 것은 1) 탐색을 시작한 지점이거나 2) 탐색될 수 없는 지점 두 가지 경우를 포함하고 있다. 따라서 Line 105에서 설명한 것처럼 두 가지 경우 중 탐색될 수 없는 지점인 경우 함수를 종료하며 운행을 멈추어야 한다.

 

탐색을 시작한 지점일 때는 처음 위치가 도착 위치라는 의미이고, 짧은 거리가 0인 상황을 그대로 유지하여 다음 과정을 진행하면 된다. 이후 출발지에 택시가 갈 수 있을 조건을 만족하면 출발지에서 다시 BFS를 통해 도착지에 도달하는 거리를 구한다. 도착지에 도달하는 거리 역시 위에서 설명한 것 같이 0인 경우 두 가지 경우가 발생하며 각 경우에 맞게 조건문을 처리했다.

 

함수에 의해 택시의 이동이 출발지부터 도착지까지 운행이 완료되었다면 재귀적으로 다시 함수를 수행하여 연속하여 탐색 및 운행을 진행하도록 구현했다. 만약 모든 M명의 승객이 모두 택시를 이용했다면 num_using_taxi 값이 M과 같을 것이고, 중간에 한 번이라도 운행을 할 수 없는 경우가 발생했다면 M에 도달하기 전에 해당 함수가 종료되었을 것이기 때문에 M보다 작게 된다. 따라서 M인 경우 현재 연료를 출력하고 그렇지 않은 경우는 -1을 출력하는 함수를 구현하여 마무리했다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int max_n = 23;

int taxi_x, taxi_y;
int N,M,fuel;
int map[max_n][max_n];
int BFS_map[max_n][max_n];

int num_using_taxi=0;

/*
 * 승객의 처음 위치 x, y 가고자 하는 위치 x, y 를 입력한다.
 * 마지막 인자는 이용했는지 여부 기록을 위한 값이다.
 * 
 * 자세히 설명하면 아래와 같다.
 * start_end[0][1] : 0번 승객의 출발지 x 좌표
 * start_end[0][2] : 0번 승객의 출발지 y 좌표
 * start_end[0][3] : 0번 승객의 도착지 x 좌표
 * start_end[0][4] : 0번 승객의 도착지 y 좌표
 * start_end[0][5] : 0번 승객의 택시 이용 여부
 */
vector<vector<int>> start_end;

int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

bool cmp(vector<int> a, vector<int> b){
    if(a[0]==b[0]) return a[1] < b[1];
    return a[0]<b[0];
}   

void Input(){
    cin >> N >> M >> fuel;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin >> map[i][j];
        }
    }

    cin >> taxi_x >> taxi_y;

    for(int i=0;i<M;i++){
        vector<int> temp_v;
        int temp;
        for(int j=0;j<4;j++){
            cin >> temp;
            temp_v.push_back(temp);
        }
        temp_v.push_back(0);
        start_end.push_back(temp_v);
    }

    sort(start_end.begin(), start_end.end(), cmp);
}

void BFS(int ix, int iy){
    //BFS 를 통해 1씩 증가시키며 BFS_map에 거리를 저장할 것이므로 벽을 -1로 표시
    bool visited[max_n][max_n];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            BFS_map[i][j] = map[i][j]*(-1);
            visited[i][j] = false;
        }
    }
    queue <pair<int,int>> q;
    visited[ix][iy]=true;
    q.push({ix,iy});

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int newX= x+dir[i][0];
            int newY= y+dir[i][1];
            if(newX<1 || newX>N || newY<1 || newY>N) continue;
            if(BFS_map[newX][newY]==-1) continue;
            if(visited[newX][newY]==false){
                visited[newX][newY]=true;
                BFS_map[newX][newY]=BFS_map[x][y]+1;
                q.push({newX,newY});
            }
        }
    }
}

void search(){
    //현재 택시 위치에서 각 승객까지의 거리를 구하기 위해 BFS를 수행하여 거리를 구한다.
    BFS(taxi_x, taxi_y);
    int short_idx=0;
    int short_path=500;
    for(int i=0;i<M;i++){
        if(start_end[i][4]==1) continue;
        if(short_path > BFS_map[start_end[i][0]][start_end[i][1]]){
            short_path = BFS_map[start_end[i][0]][start_end[i][1]];
            short_idx = i;
        }
    }

    //출발지로 이동할 거리가 0 일때 (2가지 경우 발생)
    //1. 현재 택시 위치에서 갈 수 없는 출발지 인 경우 (BFS 탐색시 방문되지 않아 0이다.) -> 종료
    //2. 현재 택시 위치가 출발지인 경우 -> 통과
    if(short_path==0) {
        //벽에 막혀 이동할 수 없는 출발지일 경우
        if(!(start_end[short_idx][0]==taxi_x &&
             start_end[short_idx][1]==taxi_y)) return;
    }

    //그 승객을 데리러갈 연료가 없을 때
    if(short_path>fuel) return;

    //승객을 태운 지점에서 BFS를 통해 거리를 구한다.
    BFS(start_end[short_idx][0],start_end[short_idx][1]);
    int delivery_distance = BFS_map[start_end[short_idx][2]][start_end[short_idx][3]];

    //도착지로 이동할 거리가 0 일때 (2가지 경우 발생)
    //1. 현재 택시 위치에서 갈 수 없는 도착지 인 경우 (BFS 탐색시 방문되지 않아 0이다.) -> 종료
    //2. 현재 택시 위치가 도착지인 경우 -> 통과
    if(delivery_distance==0) {
        //벽에 막혀 이동할 수 없는 도착지 일 경우
        if(!(start_end[short_idx][0]==start_end[short_idx][2] &&
             start_end[short_idx][1]==start_end[short_idx][3])) return;
    }

    //이동할 연료가 충분한 경우
    if(fuel >= short_path + delivery_distance){
        //택시의 현재 좌표를 도착지로 업데이트
        taxi_x = start_end[short_idx][2];
        taxi_y = start_end[short_idx][3];

        //연료 업데이트
        fuel = fuel-short_path-delivery_distance + delivery_distance*2;

        //택시 사용자 정보 업데이트
        num_using_taxi++;
        start_end[short_idx][4]=1;

        //택시 사용자가 M보다 작을 경우 새로운 search 진행
        if(num_using_taxi<M) search();
    }

    return;
}

void solve(){
    search();
    if(num_using_taxi==M) cout << fuel;
    else cout << -1;
}



int main(){
    Input();
    solve();
    return 0;
}

 

 

결과 및 후기

초기 구현 시 BFS 탐색 후 최단 거리를 구하는 과정에서 0의 값이 입력되었을 때, 이동할 수 없는 위치에 대한 경우를 고려하지 않아서 틀렸었다. 해당 조건을 고려하여 다시 search 함수를 구현하여 맞출 수 있었다. 아래는 문제 풀이에 도움이 되는 테스트 케이스와 질문들을 정리한 링크들이다.

[예외 사항 링크]  [테스트 케이스 1]  [테스트 케이스 2]

 

추가적으로 파이썬 문법에 대한 설명 중 우선순위 큐에 대한 문제풀이 팁을 보았는데 queue 모듈은 동기를 지원해서 느리다는 내용이었다. 따라서 queue 대신 heapq를 사용해야 한다. 해당 글을 읽기 전까지 heapq라는 것을 알지 못했다. 현재는 주로 C++로 구현하고 있지만 이후에 파이썬 구현에 참고가 될 수 있을 것 같아 적어보았다. 

[우선순위 큐 링크]