말하는 감자

들어가기 전 한붓그리기로도 알려진 문제 오일러 서킷은 그래프 이론에서 첫 번째로 연구된 문제로 유명하다. 오일러 서킷은 주어진 도형의 모든 선을 정확히 한 번씩 그리고 시작점으로 돌아오는 문제이다. 결론부터 말하자면, 간선들이 하나의 컴포넌트에 포함되어 있고(부분 그래프가 없고) 모든 정점의 차수가 짝수라면 오일러 서킷은 항상 존재한다. 오일러 서킷을 찾아내는 알고리즘 # 슈도 코드 # 인접 행렬 adj = [[], ... ,[]] answer = [] dfs(here): answer.append(here) for there in adj[here]: while(adj[here][there] > 0): # 방문할 간선을 지운다 adj[here][there] -= 1 # 무향 그래프라면 # adj[there..

그래프의 탐색 알고리즘은 특정 정점을 찾아낸다기 보다는 정점들을 정해진 순서대로 둘러보기 위한 알고리즘으로 이해하는 것이 맞다. 가장 유명한 깊이 우선탐색과 너비 우선탐색의 컨셉과 문제상황들을 살펴본다. 깊이 우선 탐색 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라간다. 더이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다 (재귀호출로 구현한다. 그러면 종료하고 호출시점으로 돌아간다). 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하는 알고리즘이다. 알고리즘의 큰 틀 # 슈도 코드 # 인접 리스트 or 인접 행렬 adj = [] # 정점의 방문 여부 리스트 - false 로 초기화 visite..