문제만 읽어보면 쉬운 문제 같은데 생각보다 함정이 많은 문제였다.
[함정1]. BFS로 위쪽, 왼쪽, 오른쪽, 아래쪽 순으로 돌리면 가장 행이 적은 순, 가장 열이 적은 순이 보장되지 않는다. (예시: 왼왼왼, 오오위의 경우 후자가 우선순위이지만 왼왼왼을 먼저 찾게 된다)
[함정2]. 어떤 사람의 도착점이 다른 사람의 출발점이 될 수 있다. 혹은 택시의 시작점이 사람이 있는 지점이 될 수 있다.
이 외에도 함정이 좀 있었던 것 같은데 나는 이 2가지를 처리하고 보니 AC를 받게되었다.
코드를 짤 때 로직을 아래와 같이 짰다.
- BFS_1(현재위치) - 조건에 따라 택시에서 가장 가까운 곳을 찾아서 좌표를 리턴해준다.
- BFS_2(현재위치, 승객위치) - 현재위치에서 승객 위치까지의 거리를 BFS로 찾아서 넘겨준다.
- 현재위치를 승객위치로 바꾸고 현재 남은 연료에서 위치만큼 연료를 뺀다.
- map[승객위치] 를 통해서 도착위치를 찾아낸다.
- BFS_2(승객위치, 도착위치) - 승객위치에서 도착 위치까지의 거리를 BFS로 찾아서 넘겨준다.
- 거리까지 연료량을 확인한다. 연료량이 충분한지 체크하고 연료를 추가하거나 break시킨다.
- 승객의 수(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번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
'Problem Solving > 백준' 카테고리의 다른 글
[백준/C++/KOI] 2470번 두 용액 이분탐색 풀이 (0) | 2023.03.23 |
---|---|
[백준/C++/KOI] 2467번 용액 투포인터 풀이 (0) | 2023.03.23 |
[백준/C++] 17138번 캐슬 디펜스 풀이 (2) | 2023.03.08 |
[백준/C++] 1043번 거짓말 BFS 풀이 (0) | 2023.03.02 |
[백준 / C++] 2295번 세 수의 합 풀이 (0) | 2023.02.14 |