본문 바로가기

CodeReview

백준 2325 개코전쟁 (진짜 전쟁중)

반응형

먼저 이 문제에 대해 AC를 못받았다

하지만 풀이를 생각해 냈고, 그게 올바른 풀이라는 것도 2주에 거쳐 확인했다(기간만 1달...)

심지어 나와 같은 풀이방법으로 구현해낸 다른 사람의 코드로 AC를 받았는데 내 코드만은 MLE가 나오는 상황이다

 

그러니까 정리하자면

1. 올바르게 문제를 푼 줄 알았는데 틀렸다

2. 잘 못 푼줄알고 2주가까이 검증했다

3. 그런데 다른사람의 풀이를 결국 봤는데 나랑 같았다

4. 그래서 그 분도 잘못풀었겠지 싶어 복붙해서 서밋했는데 AC가 나왔다

5. 멘붕와서 어제부터 잠못자고 유령상태다.... 왜 맞은걸까? 나는 왜 틀린걸까? 무한 반복....

 

무한 반복중인 상황을 나름 정리해보자면

1. 메모리 초과를 받았으니 배열 선언부분을 확인해보자! -> 올바르네ㅎㅎ, 똑같음을 확인

2. 다익스트라 구현에서 어디 미스를 낸건가? 배열 인덱싱에서 미스내면 MLE가 나오나? -> 인덱싱 미스는 런타임에러

3. 문제에 제시된 메모리 용량이 너무 작은건가? -> 평범함 256mb

4. 너무 많은 인클루드문과 매크로문을 적어놨나? -> 싹지워도 MLE 뚜들겨 맞음

5. 나와 같은 문제를 겪는 질문글을 찾아보자 -> 구글링해도 한개가 안나옴....

6. 나를 도와줄 사람을 찾자 -> 질문글에 대한 썰렁한 반응

7. AC받은 코드와 A to Z 비교를 해보자 -> 차이가 없음 풀이는 완전 같고, 구현도 같은 자료구조, 같은 로직으로 돌아감

8. 내가 모르는 cin, cout 등에서 잡아먹는 메모리가 있는건가? -> print문으로 바꿔도 MLE....

 

돌아버리겠는데 이렇게 블로그에 글로 남기면 언젠가 미래의 나가 해결 해주리라 굳게 믿고 있다

언제나 그렇듯 공부 계속 하다보면 잘해지고, 그때 다시보면 쉬워지고

이 문제도 같은 싸이클안에 포함일거라 믿는다😭

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
typedef long long ll;
using namespace std;

#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define vt vector
#define pb push_back
#define X first
#define Y second

#define rep(i, n) for (int i = 0; i < (n); i++)

//int INF = numeric_limits<int>::max();
#define INF 987654321
//const int num=1001;
vt<pii> adj[1001];
int par[1001];
int n,m;
void dij() {
vector<int> dist(n+1, INF);
fill(par, par+n+1, -1);dist[1]=0;
priority_queue<pii> pq;
pq.push({0, 1});
while (!pq.empty()) {
int now = pq.top().Y;
int cost = -pq.top().X;
pq.pop();
for (auto i: adj[now]) {
int nxt = i.Y;
int nxtcost = i.X+cost;
if (nxtcost > dist[nxt]) continue;
dist[nxt] = nxtcost;
par[nxt]=now;
pq.push({-nxtcost, nxt});
}
}
}

int dij2(int a, int b) {
vector<int> dist(n+1, INF);

priority_queue<pii> pq;
pq.push({0, 1});dist[1]=0;
while (!pq.empty()) {
int now = pq.top().Y;
int cost = -pq.top().X;
pq.pop();
for (auto i: adj[now]) {
int nxt = i.Y;
if ((now==a&&nxt==b)||(now==b&&nxt==a)) continue;
int nxtcost = i.X+cost;
if (nxtcost > dist[nxt]) continue;
dist[nxt] = nxtcost;
pq.push({-nxtcost, nxt});
}
}
return dist[n];
}

int main(void) {
fast_cin();
cin >> n >> m;

rep(i, m) {
int u,v,w;
cin >> u >> v >> w;
adj[u].pb({w, v});
adj[v].pb({w, u});
}

dij();
int ans=0;
for(int i=n;;i=par[i]) {
ans=max(ans, dij2(par[i], i));
if (par[i]==1) break;
}
cout << ans;
return 0;
}

반응형

'CodeReview' 카테고리의 다른 글

BOJ 1202 보석도둑  (0) 2021.01.02
개코 전쟁 (승리!)  (0) 2020.12.24
백준 개코전쟁(진짜 전쟁중, 치열함)  (0) 2020.12.23
templates for cp  (0) 2020.09.01
2020 GoogleKickStart Round E CodeReview  (0) 2020.08.25