[알고리즘 - Python] 되추적 - 기사의 여행 문제와 해밀턴 회로 코드(BackTracking - Knight's Tour and Hamiltonian Cycle Code)

문제)

Description

n by m 체스보드에서 기사의 여행 문제를 해결하는 백트래킹 알고리즘을 구현하시오.

Knight's Tour 문제는 해밀턴 경로(path)와 해밀턴 회로(circuit, cycle)를 찾는 문제로 구분할 수 있다.

해밀턴 회로는 출발 정점과 무관하게 회로의 수를 구할 수 있고,

해밀턴 경로는 출발 정점에 따라 가능한 경로의 수가 달라짐에 유의하시오.

Input

첫 번째 줄에 체스보드의 크기 n(행의 크기)과 m(열의 크기)이 주어진다.

두 번째 줄에 출발정점의 개수 T가 주어진다.

이후로 T개의 출발정점이 i(row), j(col) 의 쌍으로 주어진다.

Output

첫 번째 줄에 해밀턴 회로의 개수를 출력한다.

두 번째 줄부터 입력에서 주어진 출발정점 각각에 대해 해밀턴 경로의 수를 한 줄에 하나씩 출력한다.

Sample Input 1

3 4
3
0 0
0 1
1 0

Sample Output 1

0
2
0
4

Sample Input 2

3 10
2
0 0
1 1

Sample Output 2

32
448
416

 

코드)

# def check(d):
#     # 경로용 검사
#     return d == n * m
#
#
# def circuit_check(d, i):
#     # 회로용 검사
#     return d == n * m and 0 in adj[i]
#     # 회로므로 시작이 0임. 따라서 마지막에서 0으로 갈 수 있는 경로가 있다면 True
#
#
def func(d: int, i: int) -> None:
    # d는 depth임
    global cnt
    P[i] = 1        # 방문 표시
    if d == S:
        if flag:        # flag에 따라서 경로 검사가 달라짐
            if 0 in adj[i]:
                cnt += 1
        else:
            cnt += 1
    else:
        for n_k in adj[i]:
            # 인접한 노드부터 방문해봄
            if P[n_k] == 0:
                # 만약 유망(방문하지 않았다면)하다면? 탐색함
                func(d + 1, n_k)
    P[i] = 0        # 다시 상위 노드로 올라가야하므로 방문 표시 해제


if __name__ == "__main__":
    dir = (         # 방향을 나타냄
        (-2, 1),
        (-1, 2),
        (1, 2),
        (2, 1),
        (2, -1),
        (1, -2),
        (-1, -2),
        (-2, -1)
    )

    n, m = map(int, input().split())        # 체스 보드의 행과 열
    S = n * m
    adj = dict()
    for i in range(n):
        for j in range(m):
            adj[i * m + j] = []     # 인접 리스트 구현
            for dir_i, dir_j in dir:
                n_i, n_j = i + dir_i, j + dir_j
                if 0 <= n_i < n and 0 <= n_j < m:
                    adj[i * m + j].append(n_i * m + n_j)

    P = [0] * S     # 방문 유무를 검사하는 리스트
    cnt = 0     # 갯수를 세는 변수
    flag = 1        # flag에 따라서 경로 검사가 다름 (회로, 경로)
    func(1, 0)
    print(cnt)

    T = int(input())        # 출발정점의 개수
    flag = 0
    for _ in range(T):
        i, j = map(int, input().split())
        P = [0] * S
        cnt = 0
        func(1, i * m + j)
        print(cnt)

 

2번째 코드)

def func(d: int, i: int) -> None:
    # d는 depth이고, i는 몇 번째 말판인지 표시함
    P[i] = 1        # 방문 표시
    if d == S - 1:      # 1부터 시작하므로 말판의 개수만큼 깊이가 있음
        global cnt
        if flag:        # flag에 따라서 경로 검사가 달라짐, 1 == 회로, 0 == 경로
            if 0 in adj[i]:     # 다시 출발 정점 (0)으로 돌아갈 수 있다면
                cnt += 1
        else:
            cnt += 1
    else:
        for n_k in adj[i]:
            # 인접한 노드부터 방문해봄
            if P[n_k] == 0:
                # 만약 유망(방문하지 않았다면)하다면? 탐색함
                func(d + 1, n_k)
    P[i] = 0        # 다시 상위 노드로 올라가야하므로 방문 표시 해제


if __name__ == "__main__":
    dir = (         # 방향을 나타냄
        (-2, 1),
        (-1, 2),
        (1, 2),
        (2, 1),
        (2, -1),
        (1, -2),
        (-1, -2),
        (-2, -1)
    )

    n, m = map(int, input().split())        # 체스 보드의 행과 열
    S = n * m       # 말판의 개수, 혹은 말판의 번호
    adj = dict()        # 인접 행렬
    for i in range(n):
        for j in range(m):
            adj[i * m + j] = []     # 인접 행렬 구현, 왼쪽 위부터 0, 오른쪽 아래가 S - 1임
            for dir_i, dir_j in dir:
                n_i, n_j = i + dir_i, j + dir_j     # i, j에서 갈 수 있는 좌표
                if 0 <= n_i < n and 0 <= n_j < m:       # 만약 해당 좌표가 말판 안에 있다면
                    adj[i * m + j].append(n_i * m + n_j)        # 좌표를 말판 번호로 변환하여 넣음

    P = [0] * S     # 방문 유무를 검사하는 리스트
    cnt = 0     # 갯수를 세는 변수
    flag = 1        # flag에 따라서 경로 검사가 다름 (회로, 경로)
    func(0, 0)      # 회로를 검사함, depth와 시작 번호를 입력
    print(cnt)

    T = int(input())        # 출발정점의 개수
    flag = 0
    for _ in range(T):
        i, j = map(int, input().split())        # 출발 정점의 좌표
        P = [0] * S
        cnt = 0
        func(0, i * m + j)      # 좌표를 말판 번호로 변환함
        print(cnt)