[ 백준 ] 32일차

[ 백준 ] 32일차

- 1197번 최소 스페닝 트리

<풀이>

최소 스패닝 트리 중 크루스칼 알고리즘 사용 .. 이유는..프림 알고리즘 기억이 안남.. ..ㅋㅋㅋ.ㅋ.ㅋ.ㅋ..ㅋ...

유니온 파인드 알고리즘을 활용. 입력되는 간선 사이의 가중치 를 오름차순으로 정렬

가중치 최소를 우선으로 연결 가능한지 (같은 집합내에 존재하지 않는지) 체크하고, 가능하다면 Union함수로 집합을 연결해준다.

#include #include #include #include using namespace std; int unf[100001]; struct State{ int v1,v2,dis; State(int a, int b, int c){ v1 = a; v2 = b; dis = c; } bool operator<(const State &nn;) const{ return dis < nn.dis; } }; int Find(int v){ if(v==unf[v]) return v; else return unf[v] = Find(unf[v]); } void Union(int a, int b){ a = Find(a); b = Find(b); if(a!=b) unf[a] = b; } int v,e,a,b,c; int main(void){ cin>>v>>e; for(int i=1; i<=v; i++){ unf[i] = i; } vector vec; for(int i=0; i>a>>b>>c; vec.push_back(State(a,b,c)); } long long ans = 0; sort(vec.begin(), vec.end()); for(int i=0; i

"; }

- 1967번 트리의 지름

<풀이>

문제에 주어진 조건대로 무방향 그래프이기 때문에 인접리스트 형식으로 부모노드, 자식노드 , 가중치를 입력받았다.

트리의 지름은 존재하는 모든 경로중에 가장 길이가 긴 것이다.

1. DFS를 사용해 root인 1 부모노드에서 가장 먼 정점 노드를 우선 찾는다.

2. 1로 찾은 정점 노드를 기준으로 재 탐색하며 가장 그 점과 거리가 먼 정점 노드를 찾는다.

3. 2번으로 찾은 정점 사이의 합이 트리의 지름이다.

#include #include #include #include #include using namespace std; int n,ans =0, endpos =0; vector >vec[10002]; int ch[10002]; void DFS(int st, int sum){ if(ch[st]) return; ch[st] = 1; if(ans>n; int a,b,c; for(int i=0; i>a>>b>>c; vec[a].push_back(make_pair(b,c)); vec[b].push_back(make_pair(a,c)); } DFS(1,0); ans = 0; memset(ch,0,sizeof(ch)); DFS(endpos,0); cout<

"; }

- 2665번 미로만들기

<풀이>

며칠 전 풀었떤 1261번 알고스팟 문제랑 로직이 그냥 똑같다.

주어진 시간 제한이나 가장 적은 수로 방의 색을 바꾸는 것 까지.. 그냥 바로 다익스트라를 활용해서 바꾼 방의 개수를 정렬 기준으로 두며 탐색을 진행했다. 다익스트라로 풀지 않는다면 아마 0~ 최대로 바꿀 수 있는 수 까지 모든 경우의 수를 매번 다 탐색하고 초기화해야하기 때문에 시간 초과가 날 거같다...는 생각..?

하지만 나는 최근에 푼 덕분에,, ^^ 오늘은 날로 먹는다,,호호 즐거워라..

#include #include #include #include #include #include #include using namespace std; int dx[4] ={-1,0,1,0}; int dy[4] ={0,1,0,-1}; struct State{ int x,y,dis; State(int a, int b, int c){ x= a; y = b; dis =c; } bool operator<(const State &nn;) const{ return dis>nn.dis; } }; int n; string map[55]; int ch[55][55]; int main(void){ cin>>n; for(int i=0; i>map[i]; } priority_queue que; que.push(State(0,0,0)); ch[0][0] = 1; while(!que.empty()){ int x = que.top().x; int y = que.top().y; int dis = que.top().dis; que.pop(); if(x == n-1 && y== n-1) { cout<

"; break; } for(int i=0; i<4; i++){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx<0 || nx>=n || ny<0 || ny>=n) continue; if(ch[nx][ny]) continue; if(map[nx][ny]=='0'){ que.push(State(nx,ny,dis+1)); } if(map[nx][ny] =='1'){ que.push(State(nx,ny,dis)); } ch[nx][ny] = 1; } } return 0; }

from http://nsaay.tistory.com/239 by ccl(A) rewrite - 2021-09-24 18:26:38