그래프 (63) 썸네일형 리스트형 임계경로 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 1. 모두가 만나는 시간 "도착점에 가장 늦게 도착했을 때, 걸리는 경로의 시간" 2. 1분도 쉬지 않고 달려야 하는 도로 "도착점에 가장 늦게 도착하는 경로"를 의미 그대로 대입해보면, "도착점에 가장 늦게 도착하는 경로로 움직일 때, 지나는 도로의 수" 1번은 '게임 개발'과 똑같다. 단지 시작점이 결정되어 있을 뿐. 2번은 역방향 그래프를 이용해서 도시의 개수를 증.. 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75.. 파이프 옮기기 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다. 이므로! 대각선에는 조건이 하나 더 추가되야한다. BFS 버전 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 .. 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다. 동시에 지을 수 있다. "특정 건물을 짓기 위해서 걸리는 최소 시간은, 해당 건물을 짓기 위해 우선적으로 지어야 하는 건물들 중에서 가장 오래 걸리는 시간 + 특정 건물을 짓기 위해서 걸리는 시간" MAX(현재 건물의 최대 시간, 이전 건물에 저장된 최대 시간 + 현재 건물의 생산 시간) 각 건물을 노드라고 생각하면 그래.. 위상 정렬 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 위상 정렬은 항상 유일한 값으로 정렬되지 않음! 사이클이 없어야함! 진입 차수 = 자기 자신을 가리키는 에지의 개수 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 정렬 배열에 저장 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수 1씩 뺌 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 학생들을 노드로 생각하고, 키 순서를.. 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 이 구절이 유니온 파인드를 쓰게 만든다! 파티를 모두 union 해버리자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 .. 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net find 연산의 작동 원리 1. parent 배열에 index 값과 value 값이 동일한지 확인 2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동 3. 재귀로 반복 return parent[a] = find(parent[a]); 3. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경 이 문제는 유니온 파인드 문제다. 인접 행렬을 for문.. 유니온 파인드 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작www.acmicpc.net유니온 파인드 3가지외워야 한다!! 이 두 함수를 커스텀하는 것이다.1. int find(int a)2. void unionfunc(int a, int b)3. for (int i = 0; i = n; i++) parent[i] = i; find 연산 재귀 이유?대표 노드(조상)에 도달하면재귀를 빠져나오며 거치는 모든 값들을대표 노드값으로 변경한다. 123456.. 이전 1 2 3 4 5 6 7 8 다음