[ 백준 ] 28일차

[ 백준 ] 28일차

- 1707번 이분그래프

<풀이>

첨에는 도대체 뭔소리인가 트리 얘기하는 건가 싶은 .. 문제 이해가 안됐다. 검색으로 힌트를 얻어서 구현했다.

초기엔 BFS 구현했는데 자꾸 시간초과나서 DFS로 수정해서 다시 제출했다. 뭔가 막 시간초과 이런거 뜨면 걍 의욕 뚝떨어짐 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

1.DFS/BFS 로 완탐을하면서 1/2 둘 중 하나를 넣어줌

2. 각 노드의 이웃된 노드의 번호가 현 노드의 번호와 같은지 확인해줌 (같으면 이분그래프가 아님.. 그렇대..)

vs code에서 코딩하고 백준에 복붙하는 스타일인데 memset쓰면서 cstring 헤더 선언 맨날!!! 까먹는 바람에 컴파일 에러 발생 횟수 개많다....아오 ~

#include #include #include #include #include #include using namespace std; int k,v,e; vector vec[20001]; int ch[20001]; void DFS(int L, int c){ ch[L] = c; for(int i=0; i>k; while(k--){ memset(ch,0,sizeof(ch)); for(int i=1; i<20001; i++){ vec[i].clear(); } cin>>v>>e; int a,b; for(int i=0; i>a>>b; vec[a].push_back(b); vec[b].push_back(a); } for(int i=1; i<=v; i++){ if(!ch[i]) DFS(i,1); } if(check()) cout<<"YES"<<"

"; else cout<<"NO"<<"

"; } return 0; }

- 9370번 미확인 도착지

<풀이>

며칠 전인가.. 예전에 풀었던 다익스트라를 활용해 특정 지점이 반드시 지나는 최단거리를 구했던 문제와 유사하게 접근했다.

일단 입력받는 요소가 너무 많아서 노트에 정리를 한 후 코드 구현에 들어갔다.

한 번에 테케가 많이 주어지는 문제 경우에는 매 함수나 기능을 재사용할 때 마다 초기화에 꼭 신경을 써야한다는 점..

특정 지점인 s 에서 g,h를 꼭 지나며 후보 목적지 t중에 최단 거리로 지날 수 있는 정점을 저장하고, 여러 개 라면 정렬로 출력 !!

이게 문제의 요약이라

-특정지점 s 출발하여, t 에 도착

- 정점 g,h를 지남

=> 다익스트라 알고리즘 사용

저번과 접근이 그냥 똑같지만 일단 특정 목적지를 제외하고 2가지 이동 방향을 모두 고려 해 주어야한다.

1. s-> g -> h -> T

2. s -> h -> g -> T

이 두가지 접근 방식의 가중치 (거리) 합이 == s부터 T 까지의 최단 거리의 합과 일치한다면 ( = 최단거리로 갈 수 있다면) 목적지 저장 벡터에 넣어준다.

그 후 모든 조건에 대한 탐색이 끝나면, 배열을 오름차순 정렬하여 출력한다.

초기엔 굳이 입력되는 목적지 후보의 개수를 한 번에 다 받고, 한번에 처리하고 싶은 마음에 코드를 구현 + 따로 변수로 다 저장해서 값을 하나하나 비교하는 형태로 구현했더니 계속 33% 에서 오류가 떴었다.

한 5번 틀렸습니다가 나와서 걍 던질까..하다가 목적지 후보를 받는 즉시 처리하고 비교하는 형태도 단순하게 수정하니,, 드디어 성공^^,,

사실 아직도 왜 33퍼에서 틀린건지 모르겠음 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅎㅎ,,,

#include #include #include #include #include using namespace std; struct State{ int pos, dis; State(int p, int d){ pos = p; dis = d; } bool operator<(const State &nn;) const{ return dis >nn.dis; } }; vector > vec[2001]; int Dijkstra(int st, int ed){ vector dist(2001, 214700000); priority_queue que; que.push(State(st,0)); dist[st] =0; while(!que.empty()){ int pos = que.top().pos; int dis = que.top().dis; que.pop(); if(dis> dist[pos])continue; for(int i=0; inxdis){ dist[nxpos] = nxdis; que.push(State(nxpos,nxdis)); } } } return dist[ed]; } int k,n,m,t,s,g,h; int main(void){ cin>>k; while(k--){ for(int i=0; i<2001; i++){ vec[i].clear(); } cin>>n>>m>>t; cin>>s>>g>>h; int a,b,d; for(int i=0; i>a>>b>>d; vec[a].push_back(make_pair(b,d)); vec[b].push_back(make_pair(a,d)); } vector ans; while(t--){ int num; cin>>num; int st = Dijkstra(s,num); if(st == Dijkstra(s,g)+Dijkstra(g,h)+ Dijkstra(h,num)){ ans.push_back(num); } else if(st == Dijkstra(s,h) + Dijkstra(h,g)+Dijkstra(g,num)){ ans.push_back(num); } } sort(ans.begin(),ans.end()); for(int i=0; i

"; } }

from http://nsaay.tistory.com/235 by ccl(A) rewrite - 2021-09-18 23:00:44