사다리게임 사다리찾기...

위와 같은 사다리를 타봅시다

우선 사다리는 배열로 구현하겠습니다.

간단하게 총 높이 7, 너비 5인 배열을 만듭시다. 높이값은 사다리가 복잡하면 복잡할수록 클 테지만, 예제에서는 굳이 높이값을 크게 줄 필요는 없을 것입니다.

위의 사다리를 배열로 구현하면 아래와 같습니다.

[
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 2],
    [0, 0, 0, 2, 0],
    [3, 0, 0, 0, 0],
    [0, 0, 4, 4, 0],
    [0, 3, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

편의상 사다리에서 아래로 내려가는 줄기를 줄기, 옆으로 이동하는 줄기를 가지, 줄기와 가지가 만나는 지점을 노드라고 표현하겠습니다.

그리고 배열에서 가장 윗줄의 [0, 0, 0, 0, 0]과 가장 아랫줄의 [0, 0, 0, 0, 0]은 시작위치와 끝위치를 표시하기 위한 장치입니다.

위 사다리 배열에서 0을 만나면 아래로 내려갑니다. 그리고 0이 아닌 숫자를 만나면 가지를 만난 것이므로, 가지를 타고 다른 줄기로 Jump합니다. 이 과정을 사다리 밑에 도달할 때까지 반복해야 합니다.

그리고 사다리의 가지를 정수값 1, 2, 3....으로 표현하였습니다. 만약 사다리를 타고 내려가다가 2행 2열 노드에 도달한다면, 줄기에서 같은 값을 가진 행, 열을 검색하여 2행 3열 노드로 점프하게 됩니다.
사다리 가지마다 갖는 정수값이 다른 이유는 서로 다른 가지들을 전부 구분하기 위해서입니다.

본격적으로 사다리를 탐색하는 코드는 다음과 같습니다.

def findPathInLadder(starting: int, board: list, desti: list):
    
    position_row = 0
    position_col = starting-1
    crossing = False # 사다리를 만났을 때 건너가는 중이면 True, 아니면 False
    
    current = board[position_row][position_col]
    while position_row < len(board)-1: # 사다리가 끝지점에 도착할 때까지 반복
        if current == 0 or (crossing and current != 0): # 만약 현재 위치의 배열값이 0이라면 / 혹은 가지를 건너온 후라면
            position_row += 1 # 아래로 내려감
            current = board[position_row][position_col] # current값 갱신
            crossing = False # 가지를 건너왔으므로 False로 갱신
        elif not crossing and current != 0: # 만약 현재 위치의 배열값이 0이 아니고 아직 가지를 건너기 전이라면 == 이제 가지를 건너야 한다면
            crossing = True # 기지를 건너야하므로 True로 갱신
            for i in range(1, len(board)-1): # 배열의 첫행부터 마지막행을 제외한 나머지 행을 탐색
                if position_col == 0: # 만약 제일 왼쪽 열일 경우
                    if board[i][position_col+1] == current: # 오른쪽 열만 탐색
                        position_row = i
                        position_col += 1
                        current = board[position_row][position_col]
                        break
                elif position_col == len(board[0])-1: # 만약 제일 오른쪽 열일 경우
                    if board[i][position_col-1] == current: # 왼쪽 열만 탐색
                        position_row = i
                        position_col -= 1
                        current = board[position_row][position_col]
                        break
                elif 0 < position_col < len(board[0])-1: # 중간일 경우, 양쪽 열을 모두 탐색
                    if board[i][position_col+1] == current:
                        position_row = i
                        position_col += 1
                        current = board[position_row][position_col]
                        break
                    elif board[i][position_col-1] == current:
                        position_row = i
                        position_col -= 1
                        current = board[position_row][position_col]
                        break
            if position_row == len(board)-1 :
                break
    destination = desti[position_col]
    if destination == starting:
        return True
    return False