SW 역량테스트 - [백준] 스타트 택시 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/19238

해답 코드 : 

 

#include <iostream>
#include <deque>

using namespace std;

typedef struct pos {

	int row;
	int col;
	int num;

} pos;

typedef struct taxi {

	int row;
	int col;
	int fuel;

} taxi;

int map[20][20];
int visit[20][20];

// 1 ~ M * 10
pos guest[401];
pos target[401];
taxi myTaxi;

int dR[4] = {-1, 0, 0, 1};
int dC[4] = {0, -1, 1, 0};

int N, M;

bool isRange(int r, int c) {
	if (r < 0 || r >= N || c < 0 || c >= N) {
		return false;
	} return true;
}


int find_guest() {

	int c_r, c_c, c_dist;
	int n_r, n_c;
	int my_g;
	pos t_pos ,n_pos;

	// if taxi is in the position of the guest already
	if (map[myTaxi.row][myTaxi.col] >= 10) {
		my_g = map[myTaxi.row][myTaxi.col] / 10;
		map[myTaxi.row][myTaxi.col] = 0;
		return my_g;
	}

	// initialize visit
	fill(&visit[0][0], &visit[N - 1][N], -1);

	// use it for bfs search
	deque<pos> myQ;
	deque<pos> cand;

	// in this case, row, col, distance
	myQ.push_back({ myTaxi.row, myTaxi.col, 0 });
	visit[myTaxi.row][myTaxi.col] = 0;

	while (!myQ.empty()) {

		t_pos = myQ[0];
		c_r = t_pos.row;
		c_c = t_pos.col;
		c_dist = t_pos.num;


		for (int dir = 0; dir < 4; dir++) {

			n_r = c_r + dR[dir];
			n_c = c_c + dC[dir];

			if (c_dist + 1 >= myTaxi.fuel) {
				break;
			}

			if (isRange(n_r, n_c) && map[n_r][n_c] != 1 && visit[n_r][n_c] == -1) {

				// empty -> push back
				if (map[n_r][n_c] == 0) {
					n_pos = { n_r, n_c, c_dist + 1 };
					visit[n_r][n_c] = c_dist + 1;
					myQ.push_back(n_pos);
				}

				// guest -> erase guest, update taxi, and compare the fuel
				else if (map[n_r][n_c] >= 10) {

					cand.push_back({n_r, n_c, c_dist+1});
				}

			}

		}

		myQ.pop_front();
	}

	if (!cand.empty()) {
		pos m_cand = cand[0];
		pos n_cand;

		for (int i = 0; i < cand.size(); i++) {
			n_cand = cand[i];
			if (m_cand.num > n_cand.num) {
				m_cand = n_cand;
			} else if (m_cand.num == n_cand.num &&
				m_cand.row > n_cand.row) {
				m_cand = n_cand;
			}
			else if (m_cand.num == n_cand.num &&
				m_cand.row == n_cand.row &&
				m_cand.col > n_cand.col) {
				m_cand = n_cand;
			}

		}

		my_g = map[m_cand.row][m_cand.col] / 10;
		map[m_cand.row][m_cand.col] = 0;
		myTaxi.row = m_cand.row;
		myTaxi.col = m_cand.col;
		myTaxi.fuel -= m_cand.num;

		return my_g;
	}
	else {
		return -1;
	}

}

bool find_target(int tar_r, int tar_c) {

	int c_r, c_c, c_dist;
	int n_r, n_c;
	pos t_pos, n_pos;

	// use it for bfs search
	deque<pos> myQ;

	// taxi is already on the target
	if (myTaxi.row == tar_r && myTaxi.col == tar_c) {
		return true;
	}

	// initialize visit
	fill(&visit[0][0], &visit[N - 1][N], -1);

	// in this case, row, col, distance
	myQ.push_back({ myTaxi.row, myTaxi.col, 0 });
	visit[myTaxi.row][myTaxi.col] = 0;

	while (!myQ.empty()) {

		t_pos = myQ[0];
		c_r = t_pos.row;
		c_c = t_pos.col;
		c_dist = t_pos.num;


		for (int dir = 0; dir < 4; dir++) {

			n_r = c_r + dR[dir];
			n_c = c_c + dC[dir];

			if (myTaxi.fuel < c_dist + 1) {
				break;
			}

			// compare fuel, update taxi's position and fuel
			if (n_r == tar_r && n_c == tar_c) {

				myTaxi.row = n_r;
				myTaxi.col = n_c;
				myTaxi.fuel += (c_dist + 1);
				return true;
				
			}

			if (isRange(n_r, n_c) && map[n_r][n_c] != 1 && visit[n_r][n_c] == -1) {
				n_pos = { n_r, n_c, c_dist + 1 };
				visit[n_r][n_c] = c_dist + 1;
				myQ.push_back(n_pos);
			}
		}

		myQ.pop_front();
	}

	return false;

}



bool simulation() {

	int t_r, t_c;
	int my_g;

	if ((my_g = find_guest()) != -1) {

		t_r = target[my_g].row;
		t_c = target[my_g].col;

		if (find_target(t_r, t_c)) {
			return true;
		}

	}
	
	return false;
}


int main() {

	int t_fuel;
	int t_r, t_c;
	int cnt = 0;
	int ans = 0;
	pos t_g;

	cin >> N >> M >> t_fuel;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	cin >> t_r >> t_c;
	myTaxi = {t_r-1, t_c-1, t_fuel};

	for (int i = 1; i <= M; i++) {

		// guest
		cin >> t_r >> t_c;
		guest[i] = {t_r-1, t_c-1, i*10};

		// target
		cin >> t_r >> t_c;
		target[i] = { t_r - 1, t_c - 1, i*10 };

	}

	for (int i = 1; i <= M; i++) {
		t_g = guest[i];
		map[t_g.row][t_g.col] = t_g.num;
	}

	while (cnt != M) {
		if (!simulation()) break;
		cnt++;
	}

	if (cnt != M) ans = -1;
	else ans = myTaxi.fuel;

	std::cout << ans << endl;

}

 

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제