[Python] SW Expert Academy #1211 Ladder2

📚문제: #1211 Ladder2(D4)

전체 코드

# 1211. Ladder2
 
from copy import deepcopy
 
# 사다리 게임
def ladder(n, graph):
     
    # 최소 길이 변수 초기화
    min_dist = int(1e10)
     
    # 가능한 시작 지점에서 모두 시도해본다.
    s = []
     
    # 탐색
    for i in range(100):
         
        if graph[0][i] == 1:
             
            # 시작지점 추가
            s.append([0, i])
     
    # 가능지점에서 시작
    for coord in s:
         
        # 방문할 때 마다 카운트
        visited = 0
         
        # 원본 배열 복사
        copied = deepcopy(graph)
         
        # 현재 좌표
        cur_r, cur_c = coord
         
        # 시작지점
        X = cur_c
         
        # 시작 지점 방문처리
        copied[cur_r][cur_c] = 'v'
        visited += 1
         
        # 사다리 게임이 끝날 때 까지 계속 반복
        while True:
              
            # 범위를 벗어나지 않고, 오른쪽으로 이동할 수 있을 때
            if 0 <= cur_c + 1 <= 99 and copied[cur_r][cur_c+1] == 1:
           
                while True:
 
                    # 이동
                    cur_c = cur_c + 1
 
                    # 범위를 벗어나지 않을 때
                    if 0 <= cur_c <= 99:
                         
                        # 1이면 계속 이동
                        if copied[cur_r][cur_c] == 1:
                             
                            # 방문처리
                            copied[cur_r][cur_c] = 'v'
                            visited += 1
                            continue
                         
                        # 0이면 중단
                        elif copied[cur_r][cur_c] == 0:
                             
                            cur_c -= 1
                            break
                     
                    # 범위를 벗어날 때
                    else:
                         
                        cur_c -= 1
                        break
                     
            # 범위를 벗어나지 않고, 왼쪽으로 이동할 수 있을 때
            if 0 <= cur_c - 1 <= 99 and copied[cur_r][cur_c-1] == 1:
                 
                while True:
 
                    # 이동
                    cur_c = cur_c - 1
 
                    # 범위를 벗어나지 않을 때
                    if 0 <= cur_c <= 99:
                         
                        # 1이면 계속 이동
                        if copied[cur_r][cur_c] == 1:
                             
                            # 방문처리
                            copied[cur_r][cur_c] = 'v'
                            visited += 1
                            continue
                         
                        # 0이면 중단
                        elif copied[cur_r][cur_c] == 0:
                             
                            cur_c += 1
                            break
                     
                    # 범위를 벗어날 때
                    else:
                         
                        cur_c += 1
                        break
                 
            # 아래로 이동
            cur_r += 1
             
            # 범위 안쪽이면
            if 0 <= cur_r <= 99:
                 
                if copied[cur_r][cur_c] == 1:
                     
                    # 방문처리
                    copied[cur_r][cur_c] = 'v'
                    visited += 1
                    continue
             
            # 마지막 지점 도착
            else:
                 
                # 갱신
                if visited < min_dist:
                     
                    # 출발좌표
                    ans = X
                     
                    # 최소 거리
                    min_dist = visited
                 
                break
     
    # 답 출력
    print("#{} {}".format(n, ans))
 
# 10개의 테스트 케이스가 주어진다.
for t in range(1, 10+1):
     
    # 테스트 케이스의 번호가 주어진다.
    num = int(input())
     
    # 2차원 배열
    grid = []
     
    # 100 x 100 크기 2차원 배열
    for _ in range(100):
         
        grid.append(list(map(int, input().split())))
         
    # 함수 실행
    ladder(t, grid)