Algorithm/그래프

[틀림] 백준 1167 트리의 지름 // 거리는? bfs, 트리개념

https://www.acmicpc.net/problem/1167* 풀이(최단) 거리는? 무조건 bfs어느한곳에서 최장거리노드 -> 지름의 노드 중1개증명 : 귀류법찾은 노드에서 시작해서 가장먼곳을 찾으면 지름의 두쌍을 찾은것임. 주의1-idx임에주의vis를 n+1까지 돌리고찾을때도 n+1까지 찾아야함bfs2번주의vis[node1]=1로 시작해야함vis[1]=1 아님.#includeusing namespace std; typedef long long ll;int v,ret;int vis[100000+4];vector> adj[100000+4]; // int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>v; for..

[알고리즘] 리트코드 course schedule // dfs cycle 감지

https://leetcode.com/problems/course-schedule/description/* 풀이선행조건을 방향 그래프로 바꿔서 표현뒤의원소의 인접리스트에 앞의 원소 추가vis의 상태를 구분해야함1: 방문중2: 방문완료vector adj[2004];int vis[2004]; // 1: 방문중, 2: 방문완료class Solution {public: int dfs(int cur){ if(vis[cur]==1) return 0; // 사이클! if(vis[cur]==2) return 1; vis[cur]=1; for(auto nxt : adj[cur]){ int res = dfs(nxt); if(re..

[알고리즘] 백준 13244 Tree // tree의 조건 암기

https://www.acmicpc.net/problem/13244* Tree의 조건노드수 == 간선수+1 이어야함모두 연결되어 있어야함 // connected component 는 int dfs 결과가 n과 같아야함 * 전체코드#include using namespace std; int t,n,m, vis[1004];vector adj[1004];int dfs(int here) { vis[here]=1; int ret=1; for(auto nxt : adj[here]) { if(vis[nxt]) continue; ret += dfs(nxt); } return ret; }int main(){ ios_base::sync_with_stdio(0); cin.t..

리트코드 133 그래프 클론 c++ // 그래프 복사하는방법

https://leetcode.com/problems/clone-graph/description/ 1. 의사코드1. map에 를 담는다.2. 엣지케이스 : 원래널인경우 return nullroot에 이웃이없는경우, 그거 new로 생성해서 리턴3. dfs초기화 : cur(원본)배열의 값으로 노드를 만들어주고, 이웃만 채워주면 된다!!이웃에대해, 이미 클론되었다면(맵에 존재한다면 == 유사 visited) 이웃에 담아준다.아니라면, 거기로 들어간다.4. 아래그림에서 1에서 시작하는 dfs를 돌려보면 이해가 될것이다.class Solution {public: Node* dfs(Node* cur, unordered_map& mp) { vector neighbour; Node* c..

프로그래머스 도넛과막대그래프 c++ // 그래프 차수 특징발견, 사이클검사방법, 최대번호노드 찾는방법

https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 그래프 차수 특징발견각 그래프마다 대표정점의 특징(고유한 degree값)이 존재한다.해당정점의 갯수가 그 그래프의 갯수이다!0. 모든그래프의 갯수 == 시작점에서 뻗어나가는 간선갯수와 같다.4에서 위로가는 집합 : a모양좌로가는 집합 : b모양우로가는 집합 : c모양이 된다.즉, 3개의 집합이 도넛인지, 뭔지 찾으면 된다.1. 도넛그래프out, indegree가 같다, but 대표정점이 없다. ..

백준 1717 집합의표현 c++ // 유니온 파인드 구현방법

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. 의사코드 *파인드 : 자기자신이 부모임 == 루트노드 아님 : 부모의 조상을 찾아서 리턴 *유니언 : 조상이다를때, 작은쪽으로 합침 rootA의 부모 = rootB // parent[rootA]=rootB ※ A의 부모 = rootB 가 아님에 주의! // parent[A]=rootB (X) #include using namespace std; int n..