graph7 BOJ3830 교수님은 기다리지 않는다 3830번 교수님은 기다리지 않는다 1번부터 N번까지의 샘플에 대해 두 샘플의 무게 차이 정보가 주어질 때 교수님이 요구한 두 샘플의 무게 차를 구할 수 있으면 출력하고 구할 수 없으면 UNKNOWN을 출력한다 Disjoint Set Union & Find를 이용하는 문제인데 edge에 cost가 있다. 분리집합 문제는 여러 개 풀었었는데 가중치가 있는 건 처음 풀어봐서 꽤 헷갈리고 오래 걸렸다. scanf,printf보다 cin,cout이 훨씬 빠르고 편했다. par[N] N개 샘플의 부모 (set number) w[N] N개 샘플의 set 내 무게 (부모 무게를 0으로 했을 때의 무게) ! a b c : b가 a보다 c그램 무겁다. a와 b를 union한다. 1. a,b의 부모 para,parb를 구.. 2021. 6. 19. 그래프 (2) 문제들 2593 Elevator BFS DP N층짜리 건물에서 주어진 수열의 층에서만 멈추는 엘레베이터가 M대 있을 때 A층에서 B층까지 가기 위해 최소한으로 갈아타는 엘레베이터의 수 & 내렸던 층을 구한다. 트래킹때문에 좀 복잡했던 문제같음.. 더보기 현재 층 curf에서 탈 수 있는 엘레베이터 cure cure에서 내릴 수 있는 다음 층 nxtf nxtf가 B와 같다면 종료 다르다면 nxtf를 큐에 넣고 다음 엘레베이터 nxte로 갈아타며 dp를 업데이트 // Initiate for (int e : f[A]) dp[A][e] = { 1,0 }; Q.push(A); // BFS and Get Ans bool arrived_at_B = false; while (!Q.empty()) { arrived_at_B =.. 2021. 4. 26. BOJ3716 도로 네트워크 3716번 도로 네트워크 1부터 N까지의 도시를 연결하는 N-1개의 도로가 주어지고 서로 다른 두 도시 D, E가 주어지면 D와 E를 연결하는 도로 중 가장 짧은 것의 길이와 긴 것의 길이를 구한다. 이때 모든 서로 다른 두 도시간 경로는 한 개만 존재한다. ⇒ 주어진 그래프가 트리이다. LCA문제임은 빠르게 파악할 수 있었다. 다만 공통조상뿐 아니라 공통조상까지의 도로의 길이 중 최댓값/최솟값도 알아야 했고 여기저기 헷갈린 탓인지 여러 차례 틀려서 힘들었다ㅠ 1. Get P 먼저 각 도시의 1, 2, 4, 8, ...번째 조상을 조사한다. 1을 root로 하여 BFS로 탐색하고, 조상을 탐색하며 도로 길이의 최소/최대를 구한다. P[ i ][ k ] r = 도시 i의 $2^{\mathrm{k}}$번째 .. 2021. 4. 23. SCC SCC : 강한 연결 요소 strongly connected components 그래프 내 vertex 중 서로 간의 경로가 양방향 모두 존재하는 vertex들의 집합 X⊂G s.t. ∀a, b∈X, ∃ paths both a→b, b→a DFS와 스택이 핵심이다. 방문 지점의 order(몇 번째로 방문했는지)를 이용한다. DFS함수의 리턴 값은 현재 노드에서 도달할 수 있는 지점 중 가장 먼저 방문한 지점의 방문 순서이다. DFS(cur) = par = cur에서 도달할 수 있는 지점의 ord 중 최솟값 ord[v] v 방문 순서 fin[v] v 방문 완료 여부 = v가 속하는 SCC를 찾았는지? 현재 방문한 지점을 cur, 다음에 방문할 지점을 nxt라 하자. nxt는 다음 세 가지 경우 중 하나에 .. 2021. 4. 13. BOJ13141 Ignition BOJ13141 Ignition 그래프가 주어지고, vertex 중 한 개에 불을 질렀을 때 그래프가 모두 타는 최소 시간을 출력 불은 1초에 1만큼 태울 수 있고 어디에 불을 붙여도 그래프가 반드시 전체 다 탈 수 있는 경우만 주어지며 시점과 종점이 같은 edge도 주어지고, 같은 시점과 같은 종점 사이 여러 개의 edge가 존재할 수 있다. 두 가지가 필요하다. 1. 한 vertex에 불이 도달할 수 있는 최소 시간 2. 두 vertex 간 edge가 모두 타는 시간 1의 경우 같은 vertex라도 불을 어디에 붙이느냐에 따라 값이 다르다. 결국엔 all vertex → all vertex의 최단거리를 구해야 하므로 floyd-warshall로 구한다. 2의 경우 두 vertex 간 가장 긴 edge.. 2021. 3. 17. 그래프 (1) 최근 푼 문제 아니,,블로그 정리를 어떻게 해야할지 모르겠다. 15559 내 선물을 받아줘 15886 내 선물을 받아줘2 2536 버스 갈아타기 5214 환승 15559 내 선물을 받아줘 → union find (Disjoint Set) 15886 내 선물을 받아줘2 → 문자열 내 EW의 개수 2536 버스 갈아타기 → BFS 가로/세로로 움직이는 버스를 나누어 갈아탈 수 있는 버스를 찾아내는 방법을 생각해낼 것 bfs 더보기 ver[N] ver[ i ] = x=i에서 세로로 움직이는 버스들 저장 hor[N] hor[ i ] = y=i에서 가로로 움직이는 버스들 저장 vis[N] vis[ i ] = i번째 버스를 타기까지 갈아탄 최소 횟수 int bfs() { // STEP 1. 시작점을 포함하는 버스 for (inf.. 2021. 3. 15. 구현 (1) 18809번 Gaaaaaaaaaarden BFS BF 그래프 구현 시뮬레이션 14865번 곡선 자르기 구현 3954번 Brainf**k 인터프리터 자료구조 구현 스택 3678번 카탄의 개척자 구현 시뮬레이션 17472번 다리 만들기 2 BFS BF 그래프 구현 MST 16637번 괄호 추가하기 BF 17135번 캐슬 디펜스 BFS BF 그래프 구현 시뮬레이션 17406번 배열 돌리기 4 BF 구현 진짜 나는 좌표가 너무 헷갈린다. 공간지각능력이 좋은 사람은 아니라... 시각화가 너무나 중요하다. 과연 이 필기를 다시 꺼내볼 일이 있을 것인지,, 2021. 1. 29. 이전 1 다음
