[2021.03.30] 코딩테스트 준비

BFS 추가 연습 문제

미로탈출 & 최단거리

• BFS 이용시 queue에 저장할 때, level을 함께 저장하여 최단거리 알아냄

#include <iostream>
#include <queue>

using namespace std;

struct Point {
	int x, y;
	int level;
};

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool isVisit[7][6];

int solution(int n, int m, int(*map)[6])
{
	queue<Point> q;

	q.push({ 1, 1, 1});
	isVisit[1][1] = true;

	while (q.empty() == false) {
		Point p = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = p.x + dx[i];
			int ny = p.y + dy[i];
			if ((map[nx][ny] == 1) && (isVisit[nx][ny] == false)) {
				isVisit[nx][ny] = true;
				q.push({ nx, ny, p.level + 1 });
			}

			if ((nx == n) && (ny == m))
				return p.level + 1;
		}

	}
}

int main()
{
	int n = 5, m = 4;
	int map[7][6] = {
		{0, 0, 0, 0, 0, 0},
		{0, 1, 1, 1, 0, 0},
		{0, 0, 0, 1, 0, 0},
		{0, 1, 1, 1, 1, 0},
		{0, 1, 0, 0, 1, 0},
		{0, 1, 1, 1, 1, 0},
		{0, 0, 0, 0, 0, 0},
	};

	int answer = solution(n, m, map);

	cout << answer << endl;

	return 0;
}

2018 코딩테스트 문제 4 연습

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <stdio.h>

#define _CRT_SECURE_NO_WARNINGS

using namespace std;

int c2i(char c)
{
	return c - '0';
}

int strToMin(string sTime)
{
	int hour = c2i(sTime[0]) * 10 + c2i(sTime[1]);
	int min = c2i(sTime[3]) * 10 + c2i(sTime[4]);

	return min + (hour * 60);
}

void initMinTimeTable(list<int> &minTimeTable, vector<string>& timetable)
{
	for (int i = 0; i < timetable.size(); i++) {
		minTimeTable.push_back(strToMin(timetable[i]));
	}
}

int getCurTime(int idx, int intervalTime)
{
	int baseHour = 9;
	return (baseHour * 60) + (intervalTime * (idx - 1));
}

bool isPossibleTimeToRide(int min, int curTime)
{
	if (curTime >= min) {
		return true;
	}
	return false;
}

void getOnTheBus(int curTime, int limit, list<int>& minTimeTable)
{
	for (int i = 0; i < limit; i++) {
		if (isPossibleTimeToRide(*minTimeTable.begin(), curTime)) {
			minTimeTable.erase(minTimeTable.begin());
		}
		else {
			break;
		}
	}
}

string minToStr(int min)
{
	int hour = min / 60;
	int minumtes = min % 60;
	char str[20];

	sprintf_s(str, 6, "%02d:%02d", hour, minumtes);

	string s = str;

	return s;
}

bool cmp(int a, int b)
{
	return a < b;
}

string solution(int n, int t, int m, vector<string>& timetable)
{
	int numOfBus = n;
	int intervalTime = t;
	int maxLimit = m;
	list<int> minTimeTable;
	int answerMin = 0;

	sort(timetable.begin(), timetable.end());
	initMinTimeTable(minTimeTable, timetable);
	//sort(minTimeTable.begin(), minTimeTable.end(), cmp);

	for (int i = 1; i <= numOfBus; i++) {
		int curTime = getCurTime(i, intervalTime);

		if (i == numOfBus) { // last bus
			getOnTheBus(curTime, maxLimit - 1, minTimeTable);
			if (minTimeTable.size() == 0) {
				answerMin = curTime;
				break;
			}

			if (isPossibleTimeToRide(*minTimeTable.begin(), curTime)) {
				answerMin = *minTimeTable.begin() - 1;
				break;
			}
			else {
				answerMin = curTime;
				break;
			}
		}
		else {
			getOnTheBus(curTime, maxLimit, minTimeTable);
		}
	}

	return minToStr(answerMin);
}

int main()
{
	int n = 10;
	int t = 60;
	int m = 45;
	vector<string> timetable = { "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59",
		"23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59",
		"23:59"};
	string answer = solution(n, t, m, timetable);

	std::cout << answer << endl;

	return 0;
}