문제

스타트링크가 “스타트 택시”라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

입력

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

풀이

단순 BFS와 시뮬레이션이 결합된 문제로 그리 까다롭지 않음에도 불구하고 백준에서 정답률이 20%를 넘지 못하는 이유는 바로 문제의 모호함에 있다. 문제에서 다음과 같은 조건이 주어졌다.

모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

여기서 “각 손님의 출발지와 목적지는 다르다” 의 의미는 다음과 같다.

~~목적지가 겹치는 손님 쌍은 없다~~
한 손님에 대하여 출발지와 목적지가 같은 손님은 없다

즉, 손님마다 출발지는 서로 다르지만 목적지는 같을 수 있다는 것이다.

문제에서 조건으로 주어진 문장의 표현이 굉장히 모호하여 발생한 문제이다. 아마 문제에서 주어진 테스트 케이스를 모두 통과했음에도 불구하고 제출하자마자 틀렸습니다가 떴다면 위 문장을 잘못 해석해서 틀린 것이리라.

그리고 또 하나 특이 케이스는 벽으로 인해 아예 목적지 또는 손님에게 도달할 수 없는 경우이다. 이런 경우를 처리하기 위해 필자는 BFS 과정에서 초기 연료 소모량을 매우 큰 값으로 둠으로써 아무런 손님 또는 목직지를 탐색하지 못했을 경우 남은 연료가 무조건 음수가 되게끔 하는 방식으로 간단하게 처리했다.

그 외의 구현은 코드가 조금 길어질 수 있다는 것 빼고는 크게 어려운 점이 없다.

전체 코드

#include <iostream>
#include <cstring>
#include <queue>
#include <set>
#define y first
#define x second
using namespace std;

typedef pair<int,int> point;

int N,M,F;
int Y,X;
int field[21][21];
int dist[21][21];
set<int> dest[21][21];
int dy[]={-1,0,1,0};
int dx[]={0,-1,0,1};

bool inRange(int y, int x) {
    return 1<=y && y<=N && 1<=x && x<=N;
}

int gotoNearest() {
    int r,c;
    int nearest = 1e9;
    queue<point> q;
    dist[Y][X]=0;
    q.push({Y,X});

    while(!q.empty()) {
        point cur = q.front(); q.pop();
        int curDist = dist[cur.y][cur.x];

        if(field[cur.y][cur.x] > 1) {
            if(dist[cur.y][cur.x] < nearest) {
                r = cur.y; c = cur.x;
                nearest = dist[cur.y][cur.x];
            }
            else if(dist[cur.y][cur.x] == nearest) {
                if(cur.y < r) {
                    r = cur.y; c = cur.x;
                    nearest = dist[cur.y][cur.x];
                }
                else if(cur.y == r && cur.x < c) {
                    r = cur.y; c = cur.x;
                    nearest = dist[cur.y][cur.x];
                }
            }
        }

        for(int i=0;i<4;i++) {
            int ny = cur.y+dy[i];
            int nx = cur.x+dx[i];
            if(!inRange(ny,nx) || dist[ny][nx]!=-1 || field[ny][nx]==1) continue;
            dist[ny][nx] = curDist+1;
            q.push({ny,nx});
        }
    }

    F-=nearest;
    Y=r; X=c;
    
    if(F < 0) return -1;
    return field[r][c];
}

int takeTaxi(int n) {
    queue<point> q;
    dist[Y][X]=0;
    q.push({Y,X});

    while(!q.empty()) {
        point cur = q.front(); q.pop();
        int curDist = dist[cur.y][cur.x];

        if(dest[cur.y][cur.x].find(n) != dest[cur.y][cur.x].end()) {
            Y=cur.y; X=cur.x;
            return curDist;
        }

        for(int i=0;i<4;i++) {
            int ny = cur.y+dy[i];
            int nx = cur.x+dx[i];
            if(!inRange(ny,nx) || dist[ny][nx]!=-1 || field[ny][nx]==1) continue;
            dist[ny][nx] = curDist+1;
            q.push({ny,nx});
        }
    }

    return 1e9; // cannot reach to destination
}

void removePerson(int p) {
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(field[i][j] == p) {
                field[i][j] = 0;
                return;
            }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N>>M>>F;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin>>field[i][j];
    
    cin>>Y>>X;

    for(int i=2;i<M+2;i++) {
        int y1,x1,y2,x2;
        cin>>y1>>x1>>y2>>x2;
        field[y1][x1]=i;
        dest[y2][x2].insert(i);
    }

    while(M--) {
        memset(dist,-1,sizeof(dist));
        int p = gotoNearest();
        if(p == -1) {
            cout<<-1;
            return 0;
        }

        memset(dist,-1,sizeof(dist));
        int cost = takeTaxi(p);
        if(cost > F) {
            cout<<-1;
            return 0;
        }
        
        removePerson(p);

        F += cost;
    }

    cout<<F;
    return 0;
}

Post author: Yeojun Yoon
Post link: https://blog.yjyoon.dev/boj/2022/01/09/boj-19238/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

Android Developer

[삼성 기출] 백준 19238번 스타트 택시 풀이

문제

입력

출력

풀이

전체 코드