1.개발 진행 및 완료상황
- 3주차 python algorithm 그래프 탐색 기본 개념 공부
- 3주차 python algorithm 그래프 탐색 기본 문제 풀이
-
업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용
- 백준 1991
1991번: 트리 순회
1991번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 트리 순회 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 43388 28410 21707 66.502% 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 …
www.acmicpc.net
풀이 방식 : 딕셔너리를 이용하였다. 각 딕셔너리의 key는 root로 하였고 value는 left(왼쪽 자식), right(오른쪽 자식)으로 하였다. 재귀함수를 이용하였는데, 각 순회에 맞추어 함수 자신을 호출하는 순서를 변경해주었다.
정답코드
import sys N = int(sys.stdin.readline().strip()) tree = {} for n in range(N): root, left, right = sys.stdin.readline().strip().split() tree[root] = [left, right] def preorder(root): if root != ‘.’: print(root, end=’’) # root preorder(tree[root][0]) # left preorder(tree[root][1]) # right def inorder(root): if root != ‘.’: inorder(tree[root][0]) # left print(root, end=’’) # root inorder(tree[root][1]) # right def postorder(root): if root != ‘.’: postorder(tree[root][0]) # left postorder(tree[root][1]) # right print(root, end=’’) # root preorder(‘A’) print() inorder(‘A’) print() postorder(‘A’)
- 백준 5639
5639번: 이진 검색 트리
문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 …
www.acmicpc.net
풀이 방식 : 우선 기존의 방식으로는 정해지지 않은 입력값을 처리하는 것이 어려웠다. try, except문을 통해 해결하였다. 이진 검색트리의 경우 a라는 노드의 왼쪽 서브트리에 있는 모든 노드의 키값은 a의 키값보다 작다. 반대로 오른쪽 서브트리에 있는 모든 노드의 키값은 a의 키값보다 크다. dfs는 깊이를 우선으로 하기 때문에 root의 키값보다 큰 키값을 가진 노드가 나왔을 경우, 그 이후는 모두 root보다 큰 키값을 가지고 있다. 왜냐하면, root의 오른쪽 서브트리를 방문하기 시작했다는 뜻이기 때문이다. root의 오른쪽 서브트리에 있는 모든 노드는 root보다 큰 키값을 가진다. 따라서 root보다 큰 키값을 가진 노드가 나올 때를 기준으로 왼쪽, 오른쪽 트리로 나누었다. 재귀함수를 통해 반복하면 왼쪽자식, 오른쪽자식, 루트 순서로 출력할 수 있다. 루트보다 큰 값이 존재하지 않는 경우 또한 설정하였다.
정답 코드
import sys sys.setrecursionlimit(10**6) num_list = [] while True: try: num = int(sys.stdin.readline().rstrip()) num_list.append(num) except: break def postorder(first,end): if first > end: #루트가 가장 크면 이 조건으로 인해 함수 종료 return mid = end+1 # 루트보다 큰 값이 존재하지 않을 경우를 대비 for i in range(first+1,end+1): if num_list[first] < num_list[i]: mid = i break postorder(first+1, mid-1) postorder(mid, end) print(num_list[first]) postorder(0,len(num_list)-1)
- 백준 1197
1197번: 최소 스패닝 트리
1197번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 최소 스패닝 트리 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 63515 27114 15278 40.638% 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가…
www.acmicpc.net
크루스칼 알고리즘을 통해 풀었다. 해당 알고리즘에 대한 설명은 다음 항목에 썼다. 서로소 집합 자료의 연산 2개 union(합집합 연산)과 find(찾기 연산)를 정의하였다. 다음 항목에서 개념에 대한 설명을 읽으면 쉽게 이해할 수 있다.
정답코드
import sys
v, e = map(int, sys.stdin.readline().split()) parent = [0] *(v+1) # 부모 테이블 초기화 for i in range(1, v+1): parent[i] = i
def find_parent(parent, x): #find연산 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x]
def union_parent(parent, a, b): #union 연산 a = find_parent(parent,a) b = find_parent(parent,b) if a < b: parent[b] = a else: parent[a] = b
#간선 정보 담을 리스트와 최소 신장 트리 계산 변수 정의 edges = [] total_cost = 0
#간선 정보 주어지고 비용을 기준으로 정렬 for _ in range(e): a, b, cost = map(int, sys.stdin.readline().split()) edges.append((cost,a,b))
#간선 정보 비용 기준으로 오름차순 정렬 edges.sort()
#간선 정보 하나씩 확인하면서 크루스칼 알고리즘 수행 for i in range(e): cost, a, b = edges[i] #find 연산 후, 부모노드 다르면 사이클 발생 안하므로 union 연산 수행 -> 최소 신장 트리에 포함 if find_parent(parent, a) != find_parent(parent, b): union_parent(parent, a, b) total_cost += cost
print(total_cost)
- 백준 1206
1260번: DFS와 BFS
문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다….
www.acmicpc.net
풀이 방식: 각각 bfs함수는 queue를 이용해, dfs함수는 재귀를 이용하여 정의하였다. 또한 그래프에서 간선을 양방향으로 만들기 위한 코드도 설정했다. 단 위는 True와 False로 구현하는 방법이고, 아래는 정점만 저장하여 해결하였다.
정답코드
from collections import deque import sys #True, False로 구현 N, M, V = map(int, sys.stdin.readline().split()) graph = [[False] _ (N + 1) for * in range(N + 1)] for * in range(M): a, b = map(int, sys.stdin.readline().split()) graph[a][b] = True graph[b][a] = True visited1 = [False] _ (N + 1) # dfs의 방문기록 visited2 = [False] * (N + 1) # bfs의 방문기록 def bfs(V): q = deque([V]) # pop메서드의 시간복잡도가 낮은 덱 내장 메서드를 이용한다 visited2[V] = True # 해당 V 값을 방문처리 while q: # q가 빌때까지 돈다. V = q.popleft() # 큐에 있는 첫번째 값 꺼낸다. print(V, end=” “) # 해당 값 출력 for i in range(1, N + 1): # 1부터 N까지 돈다 if not visited2[i] and graph[V][i]: # 만약 해당 i값을 방문하지 않았고 V와 연결이 되어 있다면 q.append(i) # 그 i 값을 추가 visited2[i] = True # i 값을 방문처리 def dfs(V): visited1[V] = True # 해당 V값 방문처리 print(V, end=” “) for i in range(1, N + 1): if not visited1[i] and graph[V][i]: # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면 dfs(i) # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색) dfs(V) print() bfs(V)
from collections import deque import sys def dfs(start): visited[start] = True print(start, end=” “) for i in graph[start]: if not visited[i]: dfs(i) def bfs(start): queue = deque([start]) visited[start] = True while queue: v = queue.popleft() print(v, end=” “) for i in graph[v]: if not visited[i]: visited[i] = True queue.append(i) N, M, V = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(N + 1)] for _ in range(M): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) # 정렬 for i in graph: i.sort() # dfs visited = [False] _ (N + 1) dfs(V) print() # bfs visited = [False] _ (N + 1) bfs(V)
- 백준 11724
11724번: 연결 요소의 개수
11724번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 연결 요소의 개수 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 3 초 512 MB 92904 42207 27849 42.448% 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1…
www.acmicpc.net
풀이 방식: 연결요소란 연결되어 있는 노드들을 하나로 보는 개념이다. 따라서 dfs를 통해 그래프를 탐색하였다. for 반복문을 통해 각 노드들을 시작으로 하여 dfs를 구성하였는데, 아직 방문하지 않은 노드만 반복하도록 설정하였다. 방문하지 않았는데 연결된 노드가 없다면 노드 혼자 있다는 의미이므로 하나의 연결요소가 된다는 뜻이다. 있다면 dfs탐색을 계속 하도록 하였다. 예를 들어 A-B-C-D가 하나의 연결요소를 이루고 E 혼자 연결요소를 이룬다면, A를 탐색하는 과정에서 A,B,C,D가 방문처리 되어 위 노드들에선 for 반복문이 작동하지 않는다. count는 재귀를 통해 dfs탐색이 이루어질 때 1 증가하도록 하였다. 위 예에서 E는 for반복문이 작동하지만 연결된 node가 없기에 또 count가 +1 된다. 정답 코드중 위가 dfs를 이용한 방법, 아래가 bfs를 이용한 방법이다.
dfs
import sys
sys.setrecursionlimit(5000) input = sys.stdin.readline
dfs로 그래프를 탐색한다.
def dfs(start, depth):
#해당 노드 방문체크 한다. visited[start] = True
1
# 해당 시작점을 기준으로 계속해서 dfs로 그래프를탐색한다.
for i in graph[start]: if not visited[i]: dfs(i, depth + 1)
N, M = map(int, input().split()) graph = [[] for _ in range(N + 1)]
for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a)
방문처리
visited = [False] * (1 + N) count = 0 # 컴포넌트 그래프 개수 저장
1~N번 노드를 각각돌면서
for i in range(1, N + 1): if not visited[i]: # 만약 i번째 노드를 방문하지 않았다면 if not graph[i]: # 만약 해당 정점이 연결된 그래프가 없다면 count += 1 # 개수를 + 1 visited[i] = True # 방문 처리 else: # 연결된 그래프가 있다면 dfs(i, 0) # dfs탐색을 돈다. count += 1 # 개수를 +1
print(count)
## BFS import sys from collections import deque input = sys.stdin.readline def bfs(start): queue = deque([start]) visited[start] = True while queue: node = queue.popleft() for i in graph[node]: if not visited[i]: visited[i] = True queue.append(i) N, M = map(int, input().split()) graph = [[] for _ in range(N + 1)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) # 방문처리 visited = [False] * (1 + N) count = 0 # 컴포넌트 그래프 개수 저장 # 1~N번 노드를 각각돌면서 for i in range(1, N + 1): if not visited[i]: # 만약 방문하지 않았다면 if not graph[i]: # 만약 그래프가 비어있다면 count += 1 # 개수 1개 추가 visited[i] = True # 방문 처리 else: # 만약 그래프가 비어있지 않다면(어느 점과 연결된 점이 있다면) bfs(i) # 해당 i를 시작노드로 bfs를 돈다. count += 1 # 연결요소 를 +1개 해준다. print(count)
- 새로 배운 내용
- 그래프 알고리즘 - 서로소 집합 자료구조
그래프자료구조는 주로 2가지 형태로 주어진다. 인접 행렬형태와 인접 리스트 형태이다. 인접 행렬은 메모리 공간이 많이 필요한(O(V^2)) 대신 시간 복잡도(O(1))가 낮다. 인접 행렬은 노드간의 정보를 행렬로 저장하는데, 노드 간에 연결되지 않은 정보도 0이라고 저장한다. 반면 인접 리스트는 메모리 공간이 비교적 덜 필요하지만(O(E), E = 연결된 간선의 갯수) 최악의 경우 노드의 전체 개수인 O(V)만큼의 시간 복잡도가 걸린다. 인접 리스트는 각 노드가 연결되있는 노드를 리스트 형태로 저장한 것이다. 연결되어 있지 않는 정보는 저장하지 않는다.
서로소 집합은 공통 요소(교집합)이 없는 서로 다른 집합이다. 나누어진 원소들의 데이터를 처리하기 위한 자료구조가 서로소 집합 자료구조이다. 서로소 집합 자료구조는 union(합집합 연산)과 find(찾기 연산) 2개로 이루어져 있다. ㅗ통 트리 자료구조를 이용하는 서로소 집합 자료구조에서 서로소 집합 계산 알고리즘은 다음과 같다.
- Union 연산 정보 중 1개를 확인하여, 서로 연결된 두 노드 A,B를 확인한다.
- 두 노드 각각의 루트노드를 알아낸다.
- 두 루트노드 중 작은 노드를 부모 노드라고 가정하고 연결시킨다.
- 이후 연산 정보를 순차적으로 받으면서 반복한다.
find 연산과 union 연산
서로소 집합 알고리즘의 동작을 조금 더 자세하게 설명하면 다음과 같다.
- (노드의 개수+1)을 길이로 하는 부모 테이블을 만든다. 리스트의 원소값은 해당 인덱스값을 넣어주는데, 즉 모든 원소가 자기 자신을 부모로 가진다는 의미이다.
- union 연산 하나를 받아온다. 이를 통해 해당 노드의 부모 테이블 값을 변경해준다. 예를 들어 (1,4) 연산이 들어왔다면 4번 노드의 부모 노드는 4로 설정되어있었지만 이것을 1로 바꾸어준다. 연산을 받아오면서 반복한다.
- 만약 이후 (2,4)가 들어왔다고 가정해보자. 2번 노드의 부모 노드는 2인 반면 2번 과정으로 4의 부모 노드는 1이다. 따라서 더 큰 부모 노드를 가진 2번 노드의 부모 노드 값을 1로 바꾼다.
위 과정이 서로소 집합 알고리즘이다. 만약 위 결과로 노드 1,2,3,4,5,6이 부모 노드를 1,1,2,1,5,5 로 가지게 되었다고 가정해보자. 다른 노드와 다르게 3번 노드의 루트 노드를 조회하기 위해선 3->2->1 이라는 재귀 과정을 거쳐야한다. 이것을 압축 경로를 통해 개선한다.
다음은 압축경로를 통해 개선한 알고리즘이다.
import sys
v, e - map(int, sys.stdin.readline().split()) parent = [0]*(v+1) for i in range(1, v+1): parent[i] = i
#find 연산 def find_parent(parent, x): # 부모노드 != 자식노드 => 부모노드 따로 있음 if parent[x] != x: parent[x] = find_parent(parent, parent[x])
부모 테이블에 바로 갱신
return parent[x]
#union 연산 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
for _ in range(e): a, b = map(int, sys.stdin.readline().split()) union_parent(parent, a, b)
- 크루스칼(Kruskal) 알고리즘을 통한 최소 신장 트리(minimum spanning tree) 찾기
신장 트리는 모든 노드들이 연결되어 있지만, 사이클이 존재하지 않는 부분 그래프이다. 최소 신장 트리는 원본 그래프에서 만들 수 있는 신장 트리 중 edge 비용이 가장 낮은 신장 트리를 의미한다. 크루스칼 알고리즘의 동작과정은 다음과 같다. 참고로 두 노드의 부모노드가 같다면 사이클이 발생한다.
- 주어진 모든 간선 정보를 비용을 기준으로 오름차순 정렬
- 정보를 하나씩 확인하며 사이클 발생시키는지 확인
- 사이클 발생이 없는 것만 최소 신장 트리에 포함
- 2~3 반복으로 모든 정보에 대해 수행
위 과정을 python으로 구현하면 다음과 같다.
import sys
v, e = map(int, sys.stdin.readline().split()) parent = [0] *(v+1) # 부모 테이블 초기화 for i in range(1, v+1): parent[i] = i
def find_parent(parent, x): #find연산 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x]
def union_parent(parent, a, b): #union 연산 a = find_parent(parent,a) b = find_parent(parent,b) if a < b: parent[b] = a else: parent[a] = b
#간선 정보 담을 리스트와 최소 신장 트리 계산 변수 정의 edges = [] total_cost = 0
#간선 정보 주어지고 비용을 기준으로 정렬 for _ in range(e): a, b, cost = map(int, sys.stdin.readline().split()) edges.append((cost,a,b))
#간선 정보 비용 기준으로 오름차순 정렬 edges.sort()
#간선 정보 하나씩 확인하면서 크루스칼 알고리즘 수행 for i in range(e): cost, a, b = edges[i] #find 연산 후, 부모노드 다르면 사이클 발생 안하므로 union 연산 수행 -> 최소 신장 트리에 포함 if find_parent(parent, a) != find_parent(parent, b): union_parent(parent, a, b) total_cost += cost
print(total_cost)
- try-except문
exception(예외)는 코드를 실행하는 중에 발생한 에러를 뜻한다. 따라서 예외가 발생했을 때도 스크립트 실행을 중단하지 않고 계속 실행하게 해주는 예외처리 방법중 하나가 try-except문이다. try에 실행할 코드를 넣고 except에 예외 발생시 처리하는 코드를 넣으면 된다. 다음은 정해지지 않는 수만큼의 줄에서 입력값을 받는 코드이다.
import sys num_list = [] while True: try: num = int(sys.stdin.readline().rstrip()) num_list.append(num) except: break
- dfs와 bfs함수 정의
DFS는 Depth-First Search의 약자로 깊은 부분을 우선하여 탐색하는 방식이다. stack이나 재귀함수를 이용한다. 과정은 다음과 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 더이상 2번 과정을 수행할 수 없을 때까지 반복
파이썬 코드는 다음과 같다.
import sys # 정점의 개수, 간선의 개수, 탐색 시작할 정점의 번호 N, M, V = map(int, sys.stdin.readline().split()) graph = [[False] _ (N + 1) for * in range(N + 1)] for * in range(M): a, b = map(int, sys.stdin.readline().split()) graph[a][b] = True graph[b][a] = True visited1 = [False] _ (N + 1) def dfs(V): visited1[V] = True # 해당 V값 방문처리 print(V, end=” “) for i in range(1, N + 1): if not visited1[i] and graph[V][i]: # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면 dfs(i) # 해당 i 값으로 dfs를 돈다.(더 깊이 탐색)
BFS는 Breath-Fist Search의 약자로 너비를 우선적으로 탐색하는 방식이다. Queue자료 구조를 이용한다. 과정은 다음과 같다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 더 이상 2번 과정을 수행할 수 없을 때까지 반복
파이썬 코드는 다음과 같다.
from collections import deque import sys # 정점의 개수, 간선의 개수, 탐색 시작할 정점의 번호 N, M, V = map(int, sys.stdin.readline().split()) graph = [[False] _ (N + 1) for * in range(N + 1)] for * in range(M): a, b = map(int, sys.stdin.readline().split()) graph[a][b] = True graph[b][a] = True visited2 = [False] _ (N + 1) def bfs(V): q = deque([V]) # pop메서드의 시간복잡도가 낮은 덱 내장 메서드를 이용한다 visited2[V] = True # 해당 V 값을 방문처리 while q: # q가 빌때까지 돈다. V = q.popleft() # 큐에 있는 첫번째 값 꺼낸다. print(V, end=” “) # 해당 값 출력 for i in range(1, N + 1): # 1부터 N까지 돈다 if not visited2[i] and graph[V][i]: # 만약 해당 i값을 방문하지 않았고 V와 연결이 되어 있다면 q.append(i) # 그 i 값을 추가 visited2[i] = True # i 값을 방문처리
- 참고할 만한 레퍼런스들
- 자료구조와 함께 배우는 알고리즘 입문 파이썬편(BohYoh Shibata 지음, 강민 옮김, 이지스 퍼블리싱)
- https://www.acmicpc.net/
- https://jm-codingmemo.tistory.com/22
- https://imzzan.tistory.com/41
- https://ji-gwang.tistory.com/291
- https://ji-gwang.tistory.com/292
- https://techblog-history-younghunjo1.tistory.com/262
- https://techblog-history-younghunjo1.tistory.com/257
- https://velog.io/@nzlk112/%EB%82%B4%EA%B0%80-BFS-DFS%EB%A5%BC-%EC%9D%B4%ED%95%B4%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%9D%B4%EC%9C%A0
- https://youtube.com/watch?v=7C9RgOcvkvo&feature=share
- https://dojang.io/mod/page/view.php?id=2398
-
특이사항
- 없음
-
회고
- 어제 쉬었던 만큼 열심히 하고 싶었다. 내일까지 DFS 관련 문제들은 1회독 해야겠다.
- TO-DO-LIST
- 3주차 파이썬 알고리즘 공부
- 3주차 파이썬 알고리즘 문제 풀이
- CSAPP 읽기
-
Previous
파이썬 알고리즘 3주차 : 카드 정렬하기, 괄호, 괄호의 값, 가운데를 말해요, 행렬 제곱 -
Next
파이썬 알고리즘 3주차 : 촌수계산, 트리의 부모 찾기, 구슬 찾기
