그래프 탐색 기본
BFS/DFS
위상정렬 </aside>
5639번 이진 검색 트리
이 문제를 통해 트리의 검색방법을 알게 되었다. 전위 순회, 중위 순회, 후위 순회로 3가지 방법이 있었다. 예제 문제를 보며 아 그렇구나 했는데 이렇게 살짝만 꼬아도 어떻게 해야할지 막막했다.
핵심은 루트의 왼쪽 부분과 오른쪽 부분은 각각 루트의 왼쪽자식이 루트인 또 다른 이진 트리, 오른쪽 자식이 루트인 또 다른 이진 트리라는 것이다.
import sys
sys.setrecursionlimit(10**6)
def pre_post(start,end):
if start > end:
return
root = pre_order[start]
idx = start +1
while idx <= end:
if pre_order[idx] > root: #idx에서의 값이 루트보다 크면 그것은 오른쪽 트리의 시작이다.
break
idx += 1
pre_post(start+1,idx-1) #루트를 제외한 왼쪽 부분의 트리
pre_post(idx,end) #루트를 제외한 오른쪽 부분의 트리
sys.stdout.write(str(root)+"\\n")
pre_order = []
while True:
try:
pre_order.append(int(sys.stdin.readline()))
except:
break
pre_post(0,len(pre_order)-1)
이와 비슷한 문제를 시험으로 보았는데 뭔가 비슷하면서도 달라서 풀지 못했다. 위와같이 바로 출력해도 되지만 아래와 같이 노드 클래스를 만들고 후에 원하는 순회를 실시해도 된다는 것을 알았다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
class TreeNode:
def __init__(self,val,leftchild=None,rightchild = None):
self.val = val
self.leftchild = leftchild
self.rightchild = rightchild
def generate_tree(pre_order,in_order):
if len(pre_order) == 0 :
return
elif len(pre_order) == 1:
return TreeNode(pre_order[0])
root = TreeNode(pre_order[0]) #전위순회에서 가장 앞의 값이 루트이다.
idx = in_order.index(root.val) #중위순회에서 루트를 기준으로 서브트리가 나뉜다.
left_subtree = generate_tree(pre_order[1:idx+1],in_order[:idx])
right_subtree = generate_tree(pre_order[idx+1:],in_order[idx+1:])
root.rightchild = right_subtree
root.leftchild = left_subtree
return root
def post_order(tree):
if tree.leftchild: #왼쪽 자식 출력
post_order(tree.leftchild)
if tree.rightchild: #오른쪽 자식 출력
post_order(tree.rightchild)
print(tree.val,end=" ") #부모 출력
for _ in range(int(input())):
n = int(input())
pre_order = list(map(int,input().split()))
in_order = list(map(int,input().split()))
tree = generate_tree(pre_order,in_order)
post_order(tree)
print()
위 내용은 아래 블로그를 참고하였습니다.
1197번 최소 스패닝 트리
이 문제는 find union parent를 활용하는 크루스칼 알고리즘의 대표적인 문제이다. 생각보다 쉬운방법으로 부모를 찾아나가는 것이 신기했다. 매순간 가장 작은 가중치의 간선을 택하는 부분은 그리디 방법을 활용한 것이다. find union parent를 통해 자신의 루트를 찾거나 사이클 여부를 판단할 수 있다.
import sys
input = sys.stdin.readline
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())
parent = [0] * (v+1)
for i in range(1,v+1):
parent[i] = i
infos = []
for i in range(e):
a , b ,cost = map(int,input().split())
infos.append((cost,a,b))
infos.sort()
result = 0
for cost, a, b in infos:
if find_parent(parent,a) != find_parent(parent,b): # 부모가 같다는 것은 이미 연결이 되어있는 것이다.
result += cost
union_parent(parent,a,b)
print(result)
1916번 최소비용 구하기
위 문제는 다익스트라 알고리즘의 대표적인 문제이다. 다익스트라 알고리즘이 떠오르면 쉽게 푸는데 그게 아니라면 어떻게 풀어야할지 막막할것 같다. 반복횟수가 많아서 시간을 단축하고자 우선순위 큐와 조건을 추가해준다. 조건이 빠지면 바로 시간초과가 발생했다.
import sys
from heapq import heappop,heappush
input = sys.stdin.readline
inf = int(1e9)
n = int(input())
m = int(input())
visited = [inf] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
a , b ,cost = map(int,input().split())
graph[a].append((cost,b))
start,end = map(int,input().split())
def dijkstra(start):
q = []
visited[start] = 0
heappush(q,(0,start))
while q:
current_cost, now = heappop(q)
if current_cost > visited[now]: #이전에 갱신한 값보다 현재 비용이 높다면 탐색을 할필요가 없다.
continue
for i in graph[now]:
sum_cost = current_cost + i[0]
if sum_cost < visited[i[1]]: #now 에서 i로 가는 것이 i로 바로가는 것보다 저렴하다면 갱신한다.
visited[i[1]] = sum_cost
heappush(q,(sum_cost,i[1])) #우선순위 큐를 사용하면 적은 비용의 노선부터 탐색한다.
dijkstra(start)
ans = visited[end]
print(ans)
1939번 중량제한
위 문제는 시험때 보았던 문제였다. bfs나 다익스트라로 풀이가 될 것 같았는데 조건 설정하는 것이 쉽지 않았다. 다른 동기의 풀이를 보게 되었는데 이분탐색을 활용하였다. 지난주에 배웠던 내용을 활용했으면 생각보다 쉽게 풀릴 문제 였는데 아쉬웠다. 이번주 주제가 정해져 있다보니 자꾸 그 안에서만 생각하려고 하는것 같다. 이전에 배웠던것들을 활용할 수 있을지 생각해보는 습관을 가져야겠다고 생각했다.
import sys
input = sys.stdin.readline
from collections import deque
inf = int(1e9)
def bfs(mid):
q= deque([])
visited = set() #set가 리스트보다 연산속도가 빠르다고함
visited.add(s)
q.append(s)
while q:
now = q.popleft()
for w , i in graph[now]:
if i not in visited and w >= mid: #방문한 적이 없고 허용중량보다 mid가 작다면
q.append(i)
visited.add(i) # 방문처리
if e in visited:
return True
else:
return False
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
a ,b, c = map(int,input().split())
graph[a].append([c,b])
graph[b].append([c,a])
s,e = map(int,input().split())
start = 1 #중량의 최소값
end = 1000000000 #중량의 최대값
result = 1
while start <= end:
mid = (start + end)//2 #중간값의 중량으로 도로 순회 시작
if bfs(mid): #중간값으로 지정경로를 통과했다면
start = mid + 1 #중간값을 증가시킴
result = mid
else: #중간값으로 지정경로를 통과하지 못했다면
end = mid-1 #중간값을 감소시킴
print(result)
위와 같이 이분탐색을 활용하는 문제는 아래와 같다.
import sys
from bisect import bisect_left,bisect_right
M,N,L = list(map(int,sys.stdin.readline().split())) # M: 사대의 수 N: 동물의 수 L: 사정거리
gun_location = list(map(int,sys.stdin.readline().split()))
animal_location = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
gun_location.sort()
animal_cnt = 0
for animal in animal_location:
if animal[1] >L: #y축 길이가 사정거리 보다 길면 탐색할 필요가 없다.
continue
min_gun = animal[0]-(L - animal[1]) #animal을 잡을수 있는 가장 왼쪽의 사대 위치
max_gun = animal[0]+(L - animal[1]) #animal을 잡을수 있는 가장 오른쪽의 사대 위치
if min_gun < 0:
min_gun = 1
if bisect_left(gun_location,min_gun) != bisect_right(gun_location,max_gun):
animal_cnt += 1
#min_gun 과 max_gun사이에 사대가 하나라도 있으면 사냥 가능하므로 animal_cnt 갱신
print(animal_cnt)
2617번 구슬찾기
이 문제는 플로이드 와샬 알고리즘을 활용하면 쉽게 풀 수 있다. 하지만 경로가 아닌데 플로이드 와샬을 떠올리기 쉽지 않은것 같다. 생각해보니 3단논법과 유사한것 같다. i < k and k<j 이면 i<j라는 것을 통해 대소비교를 쉽게 할 수 있다. 다만 시간복잡도가 O(N^3)이므로 N 이 500 이하일때 사용하는 것이 좋다.
import sys
input = sys.stdin.readline
n , m = map(int,input().split())
marbles = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
big , small = map(int,input().split())
marbles[big][small] = 1
for a in range(1,n+1):
marbles[a][a] = 0
for k in range(1,n+1):
for j in range(1,n+1):
for i in range(1,n+1):
if marbles[j][k] == 1 and marbles[k][i] == 1:
marbles[j][i] = 1
ans = 0
for j in range(1,n+1):
bigger_marbles = 0
smaller_marbles = 0
for i in range(1,n+1):
if i==j:
continue
elif marbles[j][i] == 1:
bigger_marbles +=1
elif marbles[i][j] == 1:
smaller_marbles += 1
if bigger_marbles > n//2 or smaller_marbles > n//2:
ans += 1
print(ans)
위 내용은 아래 블로그를 참고하였습니다.
1432번 그래프 수정
이번주 푼 문제중에 가장 이해하기 힘들었던 문제였다. 처음에 문제가 잘 이해가 안되서 노트에 입력예제를 그려가며 이해했다. 입력 예제처럼 한줄로 쓰는 것보다 그래프로 그리면 이해가 더 잘되었다.
그래프 수정 문제의 예시 입력을 트리로 나타내 보면 위의 그림과 같다. 원래 알던 이진 트리와 화살표 방향이 반대이다. 그 이유는 나는 outdegree 기준으로 문제를 해석했기 때문이다. 화살표 출발에 있는 수가 도착하는 수보다 작아야한다. 예를 들면 입력 그래프에서 3←5는 위의 문제의 조건에 맞지 않는다. 그래서 3과 5을 교체한것이 중간에 위치한 그래프이다. 그런데 교체하고 보니 3과 4가 조건에 맞지않는다. 그래서 3과 4를 교체한 것이 결과 그래프이다. 결과 그래프는 모든 노드가 조건을 만족한다. 입력과 결과를 비교하면 3 이 5가 되었고, 5가 4가 되었으며 4가 3이 되었다. 이를 순서대로 출력한것이 1 2 5 3 4 이다.
이 방법은 코드로 구현하기 어려워 아래의 방법으로 다시 생각해 보았다.
큰 개념은 루트 노드에 가장 큰 값(N)을 할당하는 것이다. 루트노드는 outdegree값이 0이기 때문에 outdegree가 0인 노드에 N을 할당하고 해당 노드와 연결된 간선을 제거한다. 이 과정을 반복한다. 자세한 과정을 설명하면 다음과 같다.
위 그림에서 outdegree가 0인 노드에 가장 큰수를 할당하고 outdegree가 0인 노드와 연결되어있는 노드와의 간선을 제거한다.(outdegree 1감소) 단 outdegree가 0인 노드가 여러개이면 노드의 값이 큰 노드부터 수를 할당한다. 예를 들면 2번째 그래프에서 노드의 값이 5인 노드를 제거 하면서 1과 4의 outdgree가 0이된다. 하지만 4가 1보다 크기때문에 3(N)을 4(노드)에 할당한다. 그 이유는 문제에서 여러 경우 중에 오름차순인것을 출력하라고 했기 때문이다. 이것은 우선순위 큐(최대힙)를 활용하여 구현했다. 이를 구현한 코드는 아래와 같다.
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
def topology_sort():
q = []
for i in range(1,n+1):
if outdegree[i] == 0: #outdgree가 0이면
heappush(q,-i) #q에 최대힙으로 삽입
N = n
while q:
now = -heappop(q) #outdgree가 0인 노드 중 값이 가장 큰 노드
result[now] = N #선정한 노드에게 N 부여
for k in graph[now]: #현재 노드와 연결된 노드들에 대하여
outdegree[k] -= 1 #간선 제거
if outdegree[k] == 0: #outdgree가 0이면
heappush(q,-k) #q에 최대힙으로 삽입
N -= 1
n = int(input())
outdegree = [0]*(n+1)
result = [0]*(n+1)
graph = [[] for _ in range(n+1)]
for i in range(1,n+1):
x = list(map(int,input().strip()))
for j,k in enumerate(x):
if k==1:
graph[j+1].append(i)
outdegree[i] +=1
topology_sort()
if result.count(0) > 1:
print(-1)
else:
print(*result[1:])
위 코드는 아래 블로그를 참고하여 작성했습니다.
이 문제 와 비슷한 문제는 3665번 최종 순위였다. 위상 정렬을 통해 대소 비교를 결정할 수 있다는 사실도 깨달았다.
import sys
input = sys.stdin.readline
from collections import deque
for _ in range(int(input())):
n = int(input())
rank_list = list(map(int,input().split()))
m = int(input())
graph = [[] for a in range(n+1)]
indegree = [0] * (n+1)
for i in range(n-1):
for j in range(i+1,n):
graph[rank_list[i]].append(rank_list[j])
indegree[rank_list[j]] += 1
for k in range(m):
a , b = map(int,input().split())
chk = True
for x in graph[a]:
if x == b:
graph[a].remove(b)
indegree[a] += 1
graph[b].append(a)
indegree[b] -= 1
chk = False
if chk:
graph[b].remove(a)
indegree[b] += 1
graph[a].append(b)
indegree[a] -= 1
q = deque([])
for l in range(1,n+1):
if indegree[l] == 0:
q.append(l)
chk1 = True
result = []
if not q:
chk1 = False
while q:
if len(q) >1:
chk1 = False
break
now = q.popleft()
result.append(now)
for z in graph[now]:
indegree[z] -= 1
if indegree[z] <0:
chk1 = False
break
elif indegree[z] == 0:
q.append(z)
if not chk1 or len(result) < n:
print("IMPOSSIBLE")
else:
print(*result)
위 코드는 아래 블로그를 참고하여 작성했습니다.
느낀점 및 더 보아야 할것