[백준/C++] 19238번 스타트 택시 풀이

---

문제만 읽어보면 쉬운 문제 같은데 생각보다 함정이 많은 문제였다.

 

[함정1]. BFS로 위쪽, 왼쪽, 오른쪽, 아래쪽 순으로 돌리면 가장 행이 적은 순, 가장 열이 적은 순이 보장되지 않는다. (예시: 왼왼왼, 오오위의 경우 후자가 우선순위이지만 왼왼왼을 먼저 찾게 된다)

 

[함정2]. 어떤 사람의 도착점이 다른 사람의 출발점이 될 수 있다. 혹은 택시의 시작점이 사람이 있는 지점이 될 수 있다.

 

이 외에도 함정이 좀 있었던 것 같은데 나는 이 2가지를 처리하고 보니 AC를 받게되었다.

코드를 짤 때 로직을 아래와 같이 짰다.

1. BFS_1(현재위치) - 조건에 따라 택시에서 가장 가까운 곳을 찾아서 좌표를 리턴해준다.
2. BFS_2(현재위치, 승객위치) - 현재위치에서 승객 위치까지의 거리를 BFS로 찾아서 넘겨준다.
3. 현재위치를 승객위치로 바꾸고 현재 남은 연료에서 위치만큼 연료를 뺀다.
4. map[승객위치] 를 통해서 도착위치를 찾아낸다.
5. BFS_2(승객위치, 도착위치) - 승객위치에서 도착 위치까지의 거리를 BFS로 찾아서 넘겨준다.
6. 거리까지 연료량을 확인한다. 연료량이 충분한지 체크하고 연료를 추가하거나 break시킨다.
7. 승객의 수(M)만큼 반복한다.

 

---

#include<bits/stdc++.h>
using namespace std;

int map_taxi[21][21], N, M, flue;
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };
pair<int, int> mp; //mp: my position
map< pair<int, int>, pair<int, int> > pessanger;

pair<int, int> FindPessanger(pair<int, int> sp) //starting position sp
{
   queue< pair<int, int> > que;
   que.push(sp);

   bool visited[21][21];
   memset(visited, 0, sizeof(visited));
   visited[sp.first][sp.second] = 1;
   if (map_taxi[sp.first][sp.second] == 2) return sp;
   pair<int, int> gotcha = make_pair(0x3f3f3f3f, 0x3f3f3f3f);

   while (!que.empty())
   {
      int q_sz = que.size();
      for (int i = 0; i < q_sz; i++)
      {
         pair<int, int> now = que.front();
         que.pop();
         for (int i = 0; i < 4; i++)
         {
            pair<int, int> np; //new position np
            np.first = now.first + dx[i];
            np.second = now.second + dy[i];
            if (np.first < 1 || np.first > N || np.second < 1 || np.second > N) continue;
            if (!visited[np.first][np.second] && map_taxi[np.first][np.second] != 1)
            {
               visited[np.first][np.second] = 1;
               que.push(np);
               if (map_taxi[np.first][np.second] == 2)
               {
                  if (np.first < gotcha.first)
                  {
                     gotcha = np;
                  }
                  else if (np.first == gotcha.first && np.second < gotcha.second)
                  {
                     gotcha = np;
                  }
               }
            }
         }
      }
      if (gotcha.first != 0x3f3f3f3f) return gotcha;
   }

   flue = -1;
   return sp;
}

int FindDist(pair<int, int> sp, pair<int, int> dp) //starting position sp dest position dp
{
   queue< pair<int, int> > que;
   que.push(sp);

   int visited[21][21];
   memset(visited, 0, sizeof(visited));
   visited[sp.first][sp.second] = 1;
   if (map_taxi[sp.first][sp.second] == 2) return 1;

   while (!que.empty())
   {
      pair<int, int> now = que.front();
      que.pop();
      for (int i = 0; i < 4; i++)
      {
         pair<int, int> np; //new position np
         np.first = now.first + dx[i];
         np.second = now.second + dy[i];
         if (np.first < 1 || np.first > N || np.second < 1 || np.second > N) continue;
         if (!visited[np.first][np.second] && map_taxi[np.first][np.second] != 1)
         {
            visited[np.first][np.second] = visited[now.first][now.second] + 1;
            que.push(np);
            if (visited[dp.first][dp.second] != 0) return visited[dp.first][dp.second];
         }
      }
   }
   flue = -1;
   return visited[sp.first][sp.second];
}

void GuessFlue()
{
   for (int cnt = 0; cnt < M; cnt++)
   {
      pair<int, int> fp = FindPessanger(mp); //finded pessenger
      int pd = FindDist(mp, fp) - 1;

      flue -= pd;
      map_taxi[fp.first][fp.second] = 0;
      if (flue < 0) break;

      pair<int, int> fd = pessanger[fp]; //find destination
      mp = fp;

      pd = FindDist(mp, fd) - 1;
      mp = fd;
      if (pd > flue)
      {
         flue = -1; break;
      }
      else
      {
         flue -= pd;
         flue += pd * 2;
      }
   }

   cout << flue << "\n";
}

int main()
{
   ios::sync_with_stdio(0), cin.tie(0);
   cin >> N >> M >> flue;

   for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++)
      {
         cin >> map_taxi[i][j];
      }
   cin >> mp.first >> mp.second;

   for (int i = 0; i < M; i++)
   {
      pair<int, int> tmp_source, tmp_dest;
      cin >> tmp_source.first >> tmp_source.second >> tmp_dest.first >> tmp_dest.second;
      pessanger[tmp_source] = tmp_dest;
      map_taxi[tmp_source.first][tmp_source.second] = 2;
   }

   GuessFlue();
}

---

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

느낀점: 문제 쉽게 봤는데 겁나 어려워서 시간도 오래걸렸고 구현도 빡셌다.

19238번: 스타트 택시