-
[BOJ] 19238 스타트 택시 / C++공부/PS (백준) 2022. 4. 28. 23:49
https://www.acmicpc.net/problem/19238
#include <stdio.h> #include <queue> #include <vector> #include <algorithm> #define MAX_N 21 #define MAX_M 401 using namespace std; int N, M, fuel; int MAP[MAX_N][MAX_N]; // -2: EMPTY, -1: int dist[MAX_N][MAX_N]; struct DRIVER { int r, c, t; }; DRIVER driver; struct INFO { int sr, sc, er, ec; }; INFO info[MAX_M]; struct PASSENGER { int r, c; }; PASSENGER passenger[MAX_M]; vector <DRIVER> passengerList; int dr[] = { -1,0,1,0 }; int dc[] = { 0,-1,0,1 }; bool flag = true; // 모든 승객이 목적지까지 도달할 수 있음 void input() { scanf("%d %d %d", &N, &M, &fuel); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { scanf("%d", &MAP[i][j]); MAP[i][j] -= 2; } } scanf("%d %d", &driver.r, &driver.c); for (int i = 1; i <= M; i++) { int sr, sc, er, ec; scanf("%d %d %d %d", &sr, &sc, &er, &ec); info[i] = { sr,sc,er,ec}; passenger[i] = { sr,sc}; MAP[sr][sc] = i; // MAP에 승객의 번호를 저장 } } void initialize_dist() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { dist[i][j] = -1; } } } void print_dist() { printf("\n>> print_dist()\n"); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { printf("%2d ", dist[i][j]); } printf("\n"); } } void print_passengerList() { printf("\n>> print_passengerList()\n"); for (int i = 0; i < passengerList.size(); i++) { printf("[%d] r = %d, c = %d, t = %d\n", i, passengerList[i].r, passengerList[i].c, passengerList[i].t); } } bool cmp(const DRIVER &p1, const DRIVER &p2) { if (p1.t < p2.t) return true; else if (p1.t == p2.t) { if (p1.r < p2.r) return true; else if (p1.r == p2.r) { return p1.c < p2.c; } } return false; } void getShortestDist() { initialize_dist(); // dist 배열을 -1로 초기화 passengerList.clear(); // 승객 리스트 초기화 queue <DRIVER> q; driver.t = 0; // 택시기사의 거리 초기화 dist[driver.r][driver.c] = 0; q.push(driver); while (!q.empty()) { int cur_r = q.front().r; int cur_c = q.front().c; int cur_t = q.front().t; q.pop(); for (int k = 0; k < 4; k++) { int nr = cur_r + dr[k]; int nc = cur_c + dc[k]; if (nr <= 0 || nr > N || nc <= 0 || nc > N || MAP[nr][nc] == -1 || dist[nr][nc] != -1) continue; q.push({ nr,nc,cur_t + 1 }); dist[nr][nc] = cur_t + 1; } } //print_dist(); for (int i = 1; i <= M; i++) { int r = passenger[i].r; int c = passenger[i].c; if (MAP[r][c] > 0) { if (dist[r][c] == -1) // 벽에 둘러싸인 승객이 존재 { flag = false; return; } else if (fuel > dist[r][c]) // 승객을 데려다줄 수 있으면 { passengerList.push_back({ r,c,dist[r][c] }); } } } if (passengerList.size() > 0) { sort(passengerList.begin(), passengerList.end(), cmp); } else { flag = false; return; } //print_passengerList(); } int choose_passenger() { // passengerList가 존재함 int r = passengerList[0].r; int c = passengerList[0].c; int passengerNum = MAP[r][c]; // 승객 번호 return passengerNum; } int drive(int passengerNum) { // 승객을 태우러 감 int pr = passenger[passengerNum].r; int pc = passenger[passengerNum].c; //printf("승객 태우기 전... fuel = %d\n", fuel); fuel -= dist[pr][pc]; //printf("승객 태우러 왔음... fuel = %d\n", fuel); if (fuel < 0) { return -1; } else { int er = info[passengerNum].er; int ec = info[passengerNum].ec; queue <DRIVER> q; driver.r = pr; driver.c = pc; driver.t = 0; initialize_dist(); dist[driver.r][driver.c] = 0; q.push(driver); while (!q.empty()) { int cur_r = q.front().r; int cur_c = q.front().c; int cur_t = q.front().t; q.pop(); if (cur_r == er && cur_c == ec) { //printf("승객 데려다줌~~!\n"); MAP[pr][pc] = -2; // 승객을 벽으로 바꿔줌 driver.r = er; driver.c = ec; // 택시 기사 위치 업데이트 fuel -= cur_t; //printf("fuel = %d\n", fuel); if (fuel < 0) return -1; else { fuel += (2 * cur_t); return fuel; } } for (int k = 0; k < 4; k++) { int nr = cur_r + dr[k]; int nc = cur_c + dc[k]; if (nr <= 0 || nr > N || nc <= 0 || nc > N || MAP[nr][nc] == -1 || dist[nr][nc] != -1) continue; q.push({ nr,nc,cur_t + 1 }); dist[nr][nc] = cur_t + 1; } } } return -1; } int solve() { int ret = -1; for (int i = 1; i <= M; i++) { flag = true; // 1. 현재 택시기사의 위치에서 승객간의 최단거리를 구한다 getShortestDist(); if (flag == false) return -1; // 벽에 둘러싸인 승객이 있을때 -> 실패 // 2. 태우러 갈 승객의 번호를 정한다 int passengerNum = choose_passenger(); // 3. 승객을 목적지까지 데려다준다. ret = drive(passengerNum); if (ret == -1) return -1; } return ret; } int main(void) { input(); int answer = solve(); printf("%d\n", answer); return 0; }
이 문제도 주어진 테스트 케이스는 다 통과하는데 계속 틀렸습니다를 받았던 문제다.
알고보니 INFO info[MAX_M]으로 선언해야하는데 INFO info[MAX_N]으로 선언해서 버퍼 크기가 터져버렸던것..ㅎㅎ
제발 다시는 이런 실수 하지말자
'공부 > PS (백준)' 카테고리의 다른 글
[BOJ] 10845 큐 / C++ (0) 2023.01.03 [BOJ] 1966 프린터 큐 / C++ (0) 2022.05.18 [BOJ] 23288 주사위 굴리기 2 (0) 2022.04.24 [BOJ] 16235 나무 재테크 (0) 2022.04.19 [BOJ] 16236 아기 상어 / C++ (0) 2022.04.16