✅ What I did today
- 백준
- 프로그래머스
⚔️ 백준
9694 무엇을 아느냐가 아니라 누구를 아느냐가 문제다
#include"9694.h"
using namespace std;
void B9694::Solution()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
const int INF = 1000000;
int T, N, M;
int x, y, z;
cin >> T;
int c;
for(int c = 1; c<=T; ++c)
{
// N : 관계 개수, M : 정치인 수
cin >> N >> M;
vector<int> prev_node(M, -1);
vector<int> min_cost_vec(M,0);
for (int i = 1; i < M; ++i) {
min_cost_vec[i] = INF;
}
vector<vector<pair<int,int>>> fam_edge(M);
for (int i = 0; i < N; ++i) {
// 정치인 x, 의 친구 y, 친밀도 z
cin >> x >> y >> z;
fam_edge[x].push_back(make_pair(y,z));
fam_edge[y].push_back(make_pair(x,z));
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,0});
while (!pq.empty()) {
int min_cost_cur = pq.top().first;
int node_cur = pq.top().second;
pq.pop();
if (min_cost_cur > min_cost_vec[node_cur]) { continue; }
for (pair<int, int> edge : fam_edge[node_cur]) {
int node_next = edge.first;
int cost_to_next = edge.second;
int new_cost_next = min_cost_cur + cost_to_next;
if (new_cost_next < min_cost_vec[node_next]) {
prev_node[node_next] = node_cur;
min_cost_vec[node_next] = new_cost_next;
pq.push(make_pair(new_cost_next, node_next));
}
}
}
cout << "Case #" << c << ": ";
if (min_cost_vec[M - 1] == INF) {
cout << -1 << '\n';
}
else {
vector<int> buffer;
for (int idx = M - 1; idx != -1; idx = prev_node[idx]) {
buffer.push_back(idx);
}
for (int i = buffer.size()-1; -1 < i; --i) {
cout << buffer[i] << ' ';
}
cout << '\n';
}
}
}1753 최단경로
#include"1753.h"
using namespace std;
typedef pair<int, int> pii;
void B1753::Solution()
{
ios::sync_with_stdio(false);
cin.tie(0);
const int INF = numeric_limits<int>::max();
// V : 정점 개수, E : 간선 개수, K : 시작 정점
int V, E, K;
cin >> V >> E;
cin >> K;
vector<vector<pair<int, int>>> graph(V+1);
int u, v, w; // u -> v 는 비용 w
for (int i = 0; i < E; ++i) {
cin >> u >> v >> w;
graph[u].push_back(make_pair(v,w));
}
vector<int> min_cost_vec(V+1,INF);
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push(make_pair(0, K));
while (!pq.empty()) {
int cost_cur = pq.top().first;
int node_cur = pq.top().second;
pq.pop();
if (cost_cur > min_cost_vec[node_cur]) { continue; }
for (pii edge : graph[node_cur]) {
int node_next = edge.first;
int cost_next = edge.second;
int newcost = cost_cur + cost_next;
if (newcost < min_cost_vec[node_next]) {
min_cost_vec[node_next] = newcost;
pq.push(make_pair(newcost, node_next));
}
}
}
min_cost_vec[K] = 0;
for (int i = 1; i < V + 1; ++i) {
int min_cost = min_cost_vec[i];
if (min_cost == INF) {
cout << "INF" << '\n';
}
else {
cout << min_cost << '\n';
}
}
}- 요소 인덱스가 0~N인지, 1~N까지인지 헷갈림
- 우선순위 큐에 넣는 pair는 cost가 앞인데, graph는 node가 앞이라 헷갈림
- 시작이 0이 아니라 K인데 0으로 해버렸음
3055 탈출
#include"3055.h"
using namespace std;
void B3055::Solution()
{
pair<int,int> start;
int R, C;
cin >> R >> C;
vector<vector<char>> twmap(R,vector<char>(C));
queue<pair<int,int>> waterq;
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
char e; cin >> e;
twmap[i][j] = e;
if (e == 'S') { start = { i,j }; }
if (e == '*') { waterq.push({ i,j }); }
}
}
vector<int> dx = { 1,-1,0,0 };
vector<int> dy = { 0,0,1,-1 };
queue<pair<int, int>> hghq;
bool found = false;
int day = 0;
hghq.push(start);
while (true)
{
day++;
int qlen = waterq.size();
while (qlen--) {
int x = waterq.front().first;
int y = waterq.front().second;
waterq.pop();
for (int i = 0; i < 4; ++i) {
int newx = x + dx[i];
int newy = y + dy[i];
if (-1 < newx && newx < R && -1 < newy && newy < C
&& twmap[newx][newy] == '.') {
twmap[newx][newy] = '*';
waterq.push({ newx,newy });
}
}
}
qlen = hghq.size();
while (qlen--) {
int x = hghq.front().first;
int y = hghq.front().second;
hghq.pop();
for (int i = 0; i < 4; ++i) {
int newx = x + dx[i];
int newy = y + dy[i];
if (-1 < newx && newx < R && -1 < newy && newy < C) {
if (twmap[newx][newy] == '.') {
twmap[newx][newy] = 'S';
hghq.push({ newx,newy });
}
else if (twmap[newx][newy] == 'D') {
found = true;
break;
}
}
}
}
if (found) {
cout << day;
break;
}
if (waterq.size() == 0 && hghq.size() == 0) {
cout << "KAKTUS";
break;
}
}
}⚔️ 프로그래머스
n + 1 카드게임
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<queue>
using namespace std;
// 룰대로 종료하지 않아서 round 오류
// 코인을 덜 쓸 수 있는 경우를 생각을 못 함.
// 답 틀린 경우 직접 따라가보니 오류 알게 됨.
// 아끼면 나중에 갖고있던 1개를 조합해서 사용할 수도 있는데,
// 조합할 수 있으면 바로 조합해버리니까 낭비가 됨.
// pool을 도입해서 해결.
int solution(int coin, vector<int> cards) {
// card는 중복 없음
// 라운드마다 카드를 2장 뽑는다
// 각 라운드를 주체로 보고, 코인으로 완성시킬 수 있다면 땡겨온다.
// 먼저 갖고 있는 카드를 살펴보고, 완성시킬 수 있다면 완성시킨 뒤 count++
// 각 라운드에 prev가 있는 카드는 무조건 완성시키고 coin 2 감소
// inven에 카드가 prev가 있었다면, inven에서 erase하고 coin 1만 감소
// 각 라운드를 넘어갈 때마다 count-=2
int n = cards.size();
vector<int> prev(n+1, -1); // 인덱스 0의 요소는 무의미
set<int> inven; // 현재 갖고 있는 카드
queue<int> pool; // 코인 2개를 사용하면 완성할 수 있는 카드들
// cards를 순회하면서 prev를 기록해둔다
// prev : 먼저 나타난 짝궁수의 cards 인덱스
for (int i = 0; i < n; ++i) {
int ci = cards[i];
for (int j = 0; j < i; ++j) {
int cj = cards[j];
if (ci + cj == n+1) {
prev[cards[i]] = j;
break;
}
}
}
// 갖고 있는 카드 완성 확인
int count = 0; // 완성된 카드 개수
int idx = 0;
while (idx < n / 3) {
int card_cur = cards[idx];
inven.insert(card_cur);
if (prev[card_cur] != -1) {
inven.erase(card_cur);
inven.erase(cards[prev[card_cur]]);
count+=2;
}
++idx;
}
// 라운드 로직, idx == n/3부터 시작
int round = 0;
bool continueGame = true;
while (true)
{
round++;
if (idx > n - 1) { break; }
// 카드 2개를 살펴보고, 완성할 수 있는지 확인한다.
// 코인은 갖고 있는 만큼만 사용할 수 있다.
// n은 6의 배수라서 마지막 1개 예외 처리 안해도 됨.
for (int i = 0; i < 2; ++i) {
int prev_card_idx = prev[cards[idx + i]];
if (prev_card_idx != -1) {
// 이미 갖고 있었다면 코인 1개 사용해서 완성
if (inven.count(cards[prev_card_idx])) {
if (coin < 1) { continue; }
coin -= 1;
inven.erase(cards[prev_card_idx]);
count += 2;
}
else {
pool.push(cards[idx+i]);
}
}
}
idx += 2;
count -= 2;
// pool에서 하나 꺼내서 완성 시도
if (count < 0) {
if (!pool.empty() && 2 <= coin) {
pool.pop();
coin -= 2;
count += 2;
}
}
if (count < 0) { break; }
}
return round;
}
너 정말 **핵심**을 찔렀어