해밀턴 회로: 무방향 그래프 G = (V, E)가 주어질 때,
- 임의의 정점에서 출발하여 간선을 따라 모든 정점을 한번만 방문
- 출발 정점으로 되돌아 오는 사이클
해밀턴 경로:
- 모든 정점을 한번만 방문하되, 되돌아 오지 않아도 됨
노드별로 해당 노드로 갈 수 있는 그래프 생성
def make_graph(n, m):
imove = [-2, -1, 1, 2, 2, 1, -1, 2]
jmove = [1, 2, 2, 1, -1, -2, -2, -1]
graph = {i:[] for i in range(n*m)}
for i in range(n):
for j in range(m):
for k in range(8):
ni, nj = i + imove[k], j + jmove[k]
if 0 <= ni < n and 0 <= nj < m:
graph[i*m +j].append(ni*m +nj)
return graph경로 저장, 백트래킹(모든 정점을 다방문)
## k: k번째, v: 현재노드, s: 출발노드, mark: 방문한건지 여부 확인
def tour(k, v, s, n, m, graph, mark):
global count
# k가 0번부터 시작해서 n*m가 되면 완료, 회로인지 체크
if k == n * m and s in graph[v]:
mark[v] = k
count += 1
else:
for u in graph[v]:
# 방문하지 않을 경우
if mark[u] == 0:
mark[u] = k + 1
tour(k + 1, u, s, n, m, graph, mark)
mark[u] = 0개수 찾기
def solution(n,m):
graph = make_graph(n,m)
make = [0]* (n * m)
s = 0 # starting vertex
mark[s] = 1 #mark starting vertex
count = 0
tour(1, s, s, n, m , graph, mark)
return count
