[이코테] 그래프 이론
1. 팀 결성
- 0번~N번까지 총 N+1명의 학생이 있다.
- 처음에는 모든 학생이 서로 다른 팀으로 구분되어 총 N+1 팀이 존재.
- 이 때 팀을 합치는 연산과, 같은팀인지 확인하는 연산을 한다.
- 첫째 줄에 N,M 이 입력됨. M은 총 연산 횟수.
- 다음 M개 줄에는 각각의 연산이 주어짐.(a, b는 N이하의 양의 정수)
- 0 a b : 학생 a가 속한 팀과 학생 b가 속한 팀을 합치는 연산
- 1 a b : 학생 a가 학생 b와 같은 팀에 속하는지 확인하는 연산
출력조건) 같은 팀 여부를 확인하는 연산에 대항 한 줄에 하나씩 YES혹은 NO로 출력
1.1 내 답안
n, m = map(int, input().split())
parent = [0]*(n+1)
for i in range(1,n+1):
parent[i] = i
def find_root(parent, x):
if parent[x] != x:
parent[x] = find_root(parent, parent[x])
return parent[x]
def union(a, b, parent):
a = find_root(parent, a)
b = find_root(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
result = []
for i in range(m):
cal_type, x, y = map(int, input().split())
if cal_type == 0:
union(x,y,parent)
else:
if find_root(parent, x) != find_root(parent, y):
result.append('NO')
else:
result.append('YES')
for i in result:
print(i)
1.2 책 답안
def find_parent(parent,x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(x)
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
n,m = map(int, input().split())
parent = [0]*(n+1)
# 부모테이블에서 부모를 자기 자신으로 초기화
for i in range(0, n+1):
parent[i] = i
for i in range(0, m):
oper, a, b = map(int, input().split())
#합집합(union) 연산인경우
if oper == 0:
union_parent(parent, a, b)
#찾기(find) 연산인경우
elif oper == 1:
if find_parent(parent, a) == find_parent(parent, b):
print('YES')
else:
print('NO')
- 0번~N번까지 총 N+1명의 학생이 있다.
- 처음에는 모든 학생이 서로 다른 팀으로 구분되어 총 N+1 팀이 존재.
- 이 때 팀을 합치는 연산과, 같은팀인지 확인하는 연산을 한다.
- 첫째 줄에 N,M 이 입력됨. M은 총 연산 횟수.
- 다음 M개 줄에는 각각의 연산이 주어짐.(a, b는 N이하의 양의 정수)
-0 a b: 학생 a가 속한 팀과 학생 b가 속한 팀을 합치는 연산
-1 a b: 학생 a가 학생 b와 같은 팀에 속하는지 확인하는 연산
출력조건) 같은 팀 여부를 확인하는 연산에 대항 한 줄에 하나씩 YES혹은 NO로 출력
n, m = map(int, input().split())
parent = [0]*(n+1)
for i in range(1,n+1):
parent[i] = i
def find_root(parent, x):
if parent[x] != x:
parent[x] = find_root(parent, parent[x])
return parent[x]
def union(a, b, parent):
a = find_root(parent, a)
b = find_root(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
result = []
for i in range(m):
cal_type, x, y = map(int, input().split())
if cal_type == 0:
union(x,y,parent)
else:
if find_root(parent, x) != find_root(parent, y):
result.append('NO')
else:
result.append('YES')
for i in result:
print(i)
def find_parent(parent,x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(x)
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
n,m = map(int, input().split())
parent = [0]*(n+1)
# 부모테이블에서 부모를 자기 자신으로 초기화
for i in range(0, n+1):
parent[i] = i
for i in range(0, m):
oper, a, b = map(int, input().split())
#합집합(union) 연산인경우
if oper == 0:
union_parent(parent, a, b)
#찾기(find) 연산인경우
elif oper == 1:
if find_parent(parent, a) == find_parent(parent, b):
print('YES')
else:
print('NO')
2. 도시 분할 계획
- 첫째줄에 집 개수(N), 길의 개수(M) 입력됨. (N은 2 이상 100,000 이하인 정수), (M은 1이상 1,000,000 이하인 정수)
- 그 다음줄부터 M줄에 걸쳐 길의 정보 입력됨.
- (A,B,C) : A번 집과 B번 집을 연결하는 길의 유지비가 C (1<=C<=1,000)
- 전체 집을 2개의 도시로 분할한다. 각 도시 안에서는 임의의 두 집 사이에 경로가 항상 존재하도록 한다. 분리된 두 도시 사이에는 길이 없어도 됨.
- 도시 분할 기준 : 최소 유지비
2.1 내 답안
- 처음생각 : 1) 도시를 일단 분리하고, 2) 각 도시에서 최소 신장 트리 알고리즘(그 중 크루스칼)으로 풀자
- 근데 도시 분리하는 기준을 못정함
- 그럼 일단 모든 노드를 최소 비용으로 연결하는 경로 찾고, 그 중 최대 비용인 간선에서 자르면 도시 분리된다고 생각.
- 근데 애초에 서로소 집합으로 도시가 분리될 수도 있음. 이땐 어떻게 해야하는지 모르겠음
- 크루스칼 알고리즘 쓸 때 실수한거 : 간선 정보 입력할 때부터 union 씀
n, m = map(int, input().split())
parent = [0]*(n+1)
graph = []
for i in range(1,n+1):
parent[i] = i
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(a,b,parent):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
for i in range(m):
a, b, cost = map(int, input().split())
graph.append((cost, a, b))
graph.sort() # cost 기준으로 오름차순 정렬
print(graph)
# 실수 : 모든 간선으로 union 확인 먼저 했음
# 최단 비용 간선부터 차례대로, 사이클 만들지 않으면서 간선 선택
result = []
for j in graph:
cost , a, b = j
if find_parent(parent, a) != find_parent(parent, b):
union_parent(a,b, parent)
result.append(cost)
# 최소 비용으로 전체 노드 연결하는 경로 구하고 최대 비용인 간선에서 자르기
print(sum(result)-max(result))
2.2 책 답안
- 전체 그래프에서 2개의 최소 신장 트리를 만들어야하는게 핵심.
- 최소 비용으로 2개의 신장 트리로 분할하려면?
- 가장 간단한 방법은 크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거하는 것.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split()) #v:노드개수, e:간선개수
parent = [0]*(v+1) # 부모테이블 초기화
edges = []
result = 0
#부모테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
for _ in range(e):
a, b, cost = map(int, input().split())
edges.apend((cost, a, b))
# 간선을 비용순으로 정렬
cost.sort()
last = 0 # 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선
for edge in edge:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
last = cost # cost로 정렬되어있기 때문에 마지막 cost 값이 가장 클 것
result += cost
print(result - last)
- 첫째줄에 집 개수(N), 길의 개수(M) 입력됨. (N은 2 이상 100,000 이하인 정수), (M은 1이상 1,000,000 이하인 정수)
- 그 다음줄부터 M줄에 걸쳐 길의 정보 입력됨.
- (A,B,C) : A번 집과 B번 집을 연결하는 길의 유지비가 C (1<=C<=1,000) - 전체 집을 2개의 도시로 분할한다. 각 도시 안에서는 임의의 두 집 사이에 경로가 항상 존재하도록 한다. 분리된 두 도시 사이에는 길이 없어도 됨.
- 도시 분할 기준 : 최소 유지비
n, m = map(int, input().split())
parent = [0]*(n+1)
graph = []
for i in range(1,n+1):
parent[i] = i
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(a,b,parent):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
for i in range(m):
a, b, cost = map(int, input().split())
graph.append((cost, a, b))
graph.sort() # cost 기준으로 오름차순 정렬
print(graph)
# 실수 : 모든 간선으로 union 확인 먼저 했음
# 최단 비용 간선부터 차례대로, 사이클 만들지 않으면서 간선 선택
result = []
for j in graph:
cost , a, b = j
if find_parent(parent, a) != find_parent(parent, b):
union_parent(a,b, parent)
result.append(cost)
# 최소 비용으로 전체 노드 연결하는 경로 구하고 최대 비용인 간선에서 자르기
print(sum(result)-max(result))
- 가장 간단한 방법은 크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거하는 것.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split()) #v:노드개수, e:간선개수
parent = [0]*(v+1) # 부모테이블 초기화
edges = []
result = 0
#부모테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
for _ in range(e):
a, b, cost = map(int, input().split())
edges.apend((cost, a, b))
# 간선을 비용순으로 정렬
cost.sort()
last = 0 # 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선
for edge in edge:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
last = cost # cost로 정렬되어있기 때문에 마지막 cost 값이 가장 클 것
result += cost
print(result - last)
3. 커리큘럼
- 첫째 줄에는 강의 수 N을 입력 (1<=N<=500)
- 다음 N개 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 선수과목 강의들의 번호가 자연수로 주어짐. (강의 시간은 100,000 이하의 자연수)
- 동시에 여러 강의 듣을 수 있음.
- 예를들어 1번(30시간), 2번(20시간), 3번(40시간)이고 3번의 선수과목이 1번과 2번일 때, 3번 강의를 수강하기까지의 최소 시간은 70시간이다.
- 각 강의 번호는 1부터 N까지 구성됨. 각 줄은 -1로 끝남.
출력 조건 ) N개의 강의에 대하여 수강하기 까지 걸리는 최소 시간을 한 줄에 하나씩 출력
3.1 내 답안
- 위상정렬문제임은 알겠는데 time 계산하는게 어려웠다.
- 처음 생각 : 과목 수강 순서가 [1,2,3,4,5]라면 단계를 나눠서 각 단계별로 최대 시간을 구할까
- 대신에 위상정렬을 하면서 각 노드의 진입차수가 1씩 줄어들 때마다 그 노드에 도달하는 최대 시간을 갱신해보자.
n = int(input())
time = [0]*(n+1)
pre = [[] for i in range(n+1)]
indegree = [0]*(n+1) #모든 노드에 대한 진입차수는 0으로 초기화
for i in range(1,n+1):
info = list(map(int, input().split()))
time[i] = info[0]
for p in info[1:-1]:
pre[p].append(i)
indegree[i] += 1
from collections import deque
import copy
result = []
time_result = copy.deepcopy(time) #각 노드에 도달하는 모든 경우에 수 중 최장 시간을 모은 리스트
q = deque()
for i in range(1,n+1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
for j in pre[now]:
indegree[j] -= 1
time_result[j] = max(time_result[j], time_result[now] + time[j])
if indegree[j] == 0:
q.append(j)
for i in range(1, n+1):
print(time_result[i])
3.2 책 답안
- 각 노드에 대하여 인접한 노드를 확인할 때, 인접한 노드에 대하여 현재보다 강의 시간이 더 긴 경우를 찾는다면, 더 오랜 시간이 걸리는 경우의 시간값을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구할 수 있다.
from collections import deque
import copy
n = int(input())
# 모든 노드에 대한 진입차수를 0으로 초기화
indegree = [0]*(n+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(n+1)]
# 각 강의 시간을 0으로 초기화
time = [0]*(n+1)
# 방향 그래프의 모든 간선 정보 입력받기
for i in range(1, n+1):
data = list(map(int, input().split()))
time[i] = data[0]
for x in data[1:-1]:
indegree[i] += 1
graph[x].append(i)
# 위상 정렬 함수
def topology_sort():
result = copy.deepcopy(time) #알고리즘 수행결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, n+1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft()
# 해당 원소와 연결된 노드들의 진입차수에서 1뺴기
for i in graph[now]:
result[i] = max(result[i], result[now]+time[i])
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
# 위상정렬을 수행한 결과 출력
for i in range(1,n+1):
print(result[i])
topology_sort()
Author And Source
이 문제에 관하여([이코테] 그래프 이론), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@hong_journey/이코테-그래프-이론
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 첫째 줄에는 강의 수 N을 입력 (1<=N<=500)
- 다음 N개 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 선수과목 강의들의 번호가 자연수로 주어짐. (강의 시간은 100,000 이하의 자연수)
- 동시에 여러 강의 듣을 수 있음.
- 예를들어 1번(30시간), 2번(20시간), 3번(40시간)이고 3번의 선수과목이 1번과 2번일 때, 3번 강의를 수강하기까지의 최소 시간은 70시간이다. - 각 강의 번호는 1부터 N까지 구성됨. 각 줄은 -1로 끝남.
출력 조건 ) N개의 강의에 대하여 수강하기 까지 걸리는 최소 시간을 한 줄에 하나씩 출력
n = int(input())
time = [0]*(n+1)
pre = [[] for i in range(n+1)]
indegree = [0]*(n+1) #모든 노드에 대한 진입차수는 0으로 초기화
for i in range(1,n+1):
info = list(map(int, input().split()))
time[i] = info[0]
for p in info[1:-1]:
pre[p].append(i)
indegree[i] += 1
from collections import deque
import copy
result = []
time_result = copy.deepcopy(time) #각 노드에 도달하는 모든 경우에 수 중 최장 시간을 모은 리스트
q = deque()
for i in range(1,n+1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
for j in pre[now]:
indegree[j] -= 1
time_result[j] = max(time_result[j], time_result[now] + time[j])
if indegree[j] == 0:
q.append(j)
for i in range(1, n+1):
print(time_result[i])
from collections import deque
import copy
n = int(input())
# 모든 노드에 대한 진입차수를 0으로 초기화
indegree = [0]*(n+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(n+1)]
# 각 강의 시간을 0으로 초기화
time = [0]*(n+1)
# 방향 그래프의 모든 간선 정보 입력받기
for i in range(1, n+1):
data = list(map(int, input().split()))
time[i] = data[0]
for x in data[1:-1]:
indegree[i] += 1
graph[x].append(i)
# 위상 정렬 함수
def topology_sort():
result = copy.deepcopy(time) #알고리즘 수행결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, n+1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft()
# 해당 원소와 연결된 노드들의 진입차수에서 1뺴기
for i in graph[now]:
result[i] = max(result[i], result[now]+time[i])
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
# 위상정렬을 수행한 결과 출력
for i in range(1,n+1):
print(result[i])
topology_sort()
Author And Source
이 문제에 관하여([이코테] 그래프 이론), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hong_journey/이코테-그래프-이론저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
