[백준 19238] 스타트 택시 C언어 문제 풀이
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
문제 요약
N*N 크기의 맵에서 총 M명의 승객을 각 승객이 원하는 도착 지점까지 이동시켜 주어야 합니다.
택시는 상하좌우로 이동할 수 있으며 한 칸을 이동할 때 연료가 1 소비됩니다.
택시는 항상 최단 경로로만 이동합니다.
단, 승객을 무사히 목적지까지 연료가 모두 소비되기 전까지 이동시키는데 성공했다면
승객을 목적지까지 이동시키는 데 사용한 연료의 2배를 충전할 수 있습니다.
모든 연료가 소비되기전에 모든 승객을 원하는 도착 지점까지 이동시킬 수 있다면
현재 남은 연료량을 출력,
모든 연료가 소비될 동안 M명의 승객을 모두 이동시키 못했다면
-1을 출력 합니다.
현재 상태를 나타낸 그림 입니다.
승객은 총 3명, 연료는 15가 남아있는 상태입니다.
승객1은 목적지1로,
승객2는 목적지2로,
승객3은 목적지3으로 이동시켜야 합니다.
택시는 가장 처음에 "어떤 승객을 태울 것인가?"를
먼저 선택해야 합니다.
따라서 가장 가까운 승객인 승객2를 태워야 합니다.
이후 승객2가 가고자 하는 목적지2로 이동시킵니다.
지금까지 사용한 연료는
승객을 태울 때 6, 목적지2로 이동할 때 6으로
총 12입니다.
하지만 목적지까지 승객을 무사히 이동시켰기 때문에
연료가 12 충전되어 남은 연료량은 15가 됩니다.
이런 과정을 M명의 승객을 목적지까지 이동시키는 동안 반복한다면
마지막으로 남는 연료량은 14가 됩니다.
접근 방법
typedef struct node_
{
int h,w;
}node;
typedef struct cost_
{
node move;
int c;
}cost;
int N,M,F;
int goal;
bool map[21][21];
int st_map[21][21];
node en_map[401];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};<전처리 코드>
기본적으로 BFS로 구현됩니다.
BFS를 통해 현재 택시의 위치로부터
가장 가까운 승객을 찾습니다.
찾은 승객의 위치와 필요한 연료량을 return합니다.
다만, 지도의 상태에 따라 승객까지 도달하지 못하는 경우도 있습니다.
이러한 경우에는 {-1,-1,-1}을 return합니다.
main에서는 전달받은 정보를 바탕으로
승객을 발견했는지, 필요 연료량만큼 연료가 남아있는지에 따라
다음 내용을 수행 합니다.
cost search(node s)
{
int vis[21][21] = {};
node queue[401];
int f=-1, r=-1;
queue[++r] = s;
vis[s.h][s.w] = 1;
node G = {-1,-1};
while(f<r)
{
node now = queue[++f];
if(0 < st_map[now.h][now.w])
{
if(G.h==-1 && G.w==-1) G = now;
else if(vis[G.h][G.w] == vis[now.h][now.w])
{
if(now.h<G.h) G = now;
else if(now.h == G.h)
{
if(now.w<G.w) G = now;
}
}
}
for(int i=0;i<4;i++)
{
node move = {now.h+dir[i][0],now.w+dir[i][1]};
if(move.h<1||move.w<1||N<move.h||N<move.w)
continue;
if(vis[move.h][move.w] || map[move.h][move.w])
continue;
queue[++r] = move;
vis[move.h][move.w] = vis[now.h][now.w] + 1;
}
}
cost ret = {G,vis[G.h][G.w]-1};
return ret;
}
승객의 목적지 역시 BFS를 통해 구현됩니다.
하지만 승객마다 원하는 목적지가 다르기 때문에
이번에는 가장 가까운 노드가 아닌,
승객이 원하는 목적지를 찾아야 합니다.
cost go(node s, int g)
{
int vis[21][21] = {};
node queue[401];
int f=-1, r=-1;
queue[++r] = s;
vis[s.h][s.w] = 1;
while(f<r)
{
node now = queue[++f];
if(now.h == en_map[g].h && now.w == en_map[g].w)
{
cost ret = {now, vis[now.h][now.w]-1};
return ret;
}
for(int i=0;i<4;i++)
{
node move = {now.h+dir[i][0],now.w+dir[i][1]};
if(move.h<1||move.w<1||N<move.h||N<move.w)
continue;
if(vis[move.h][move.w] || map[move.h][move.w])
continue;
queue[++r] = move;
vis[move.h][move.w] = vis[now.h][now.w] + 1;
}
}
cost ret = {{-1,-1},-1};
return ret;
}en_map 배열을 통해
승객의 번호 index에 해당 승객이 원하는 목적지의 정보를 저장했습니다.
g번 승객의 목적지는 en_map[g]에 정보가 저장되어 있습니다.
중간에 목적지를 올바로 찾았다면
목적지의 정보와 필요 연료량을 return 합니다.
만일 모든 노드를 방문할 동안 승객이 원하는 목적지를 찾지 못했다면
{-1,-1,-1}를 return 합니다.
main에서는 전달받은 정보를 바탕으로
목적지를 발견했는지, 필요 연료량만큼 연료가 남아있는지에 따라
다음 내용을 수행합니다.
<전체 코드>
#include<stdio.h>
#include<stdbool.h>
typedef struct node_
{
int h,w;
}node; // 위치 정보
typedef struct cost_
{
node move;
int c;
}cost; // return 값
int N,M,F;
int goal;
bool map[21][21]; // 지도 벽 상태
int st_map[21][21]; // 승객 위치
node en_map[401]; // 목적지 정보
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
cost search(node s)
{
int vis[21][21] = {};
node queue[401];
int f=-1, r=-1;
queue[++r] = s;
vis[s.h][s.w] = 1;
node G = {-1,-1};
while(f<r)
{
node now = queue[++f];
if(0 < st_map[now.h][now.w])
{
if(G.h==-1 && G.w==-1) G = now;
else if(vis[G.h][G.w] == vis[now.h][now.w]) // 거리가 같은 경우
{
if(now.h<G.h) G = now;
else if(now.h == G.h)
{
if(now.w<G.w) G = now;
}
}
}
for(int i=0;i<4;i++)
{
node move = {now.h+dir[i][0],now.w+dir[i][1]};
if(move.h<1||move.w<1||N<move.h||N<move.w)
continue;
if(vis[move.h][move.w] || map[move.h][move.w])
continue;
queue[++r] = move;
vis[move.h][move.w] = vis[now.h][now.w] + 1;
}
}
cost ret = {G,vis[G.h][G.w]-1}; // 찾은 승객 위치, 필요 연료량
return ret;
}
cost go(node s, int g)
{
int vis[21][21] = {};
node queue[401];
int f=-1, r=-1;
queue[++r] = s;
vis[s.h][s.w] = 1;
while(f<r)
{
node now = queue[++f];
if(now.h == en_map[g].h && now.w == en_map[g].w) // 목적지를 찾은 경우
{
cost ret = {now, vis[now.h][now.w]-1}; // 목적지 위치, 필요 연료량
return ret;
}
for(int i=0;i<4;i++)
{
node move = {now.h+dir[i][0],now.w+dir[i][1]};
if(move.h<1||move.w<1||N<move.h||N<move.w)
continue;
if(vis[move.h][move.w] || map[move.h][move.w])
continue;
queue[++r] = move;
vis[move.h][move.w] = vis[now.h][now.w] + 1;
}
}
cost ret = {{-1,-1},-1}; // 목적지를 찾지 못했을 경우
return ret;
}
int main()
{
scanf("%d %d %d",&N,&M,&F);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
scanf("%d",&map[i][j]);
node texi;
scanf("%d %d",&(texi.h),&(texi.w));
for(int i=1;i<=M;i++)
{
node st, en;
scanf("%d %d %d %d",&(st.h),&(st.w),&(en.h),&(en.w));
st_map[st.h][st.w] = i;
en_map[i] = en;
}
while(0<F)
{
cost temp = search(texi); // 가장 가까운 승객 찾기
texi = temp.move;
F -= temp.c;
if(texi.h==-1 && texi.w==-1 || F<=0) break; // 승객을 찾지 못했거나 연료가 부족한 경우
temp = go(texi, st_map[texi.h][texi.w]); // 승객의 목적지 찾기
st_map[texi.h][texi.w] = 0; // 지도에서 승객 제거
texi = temp.move;
F -= temp.c;
if(texi.h==-1 && texi.w==-1 || F<0) break; // 목적지를 찾지 못했거나 연료가 부족한 경우
F += temp.c * 2; // 승객을 무사히 이동시켰기 때문에 연료 충전
goal++; // 이동 시킨 총 승객 수
if(M <= goal) break; // 승객이 더 이상 남아있지 않다면 종료
}
if(goal < M) printf("-1"); // 승객을 모두 이동시키지 못했을 경우
else printf("%d",F); // 모든 승객을 이동시킨 경우
}
