2일차 - Ladder2

def line_to_line_distance(start, end):
    return abs(start_column[start]-start_column[end]) - 1

array_size = 100
repeat_number = 10
ans = list()

for _ in range(repeat_number):
    _ = input()
    ladder = [list(map(int, input().split())) for _ in range(array_size)]

    start_column = list()
    for i in range(array_size):
        if ladder[0][i] == 1:
            start_column.append(i)

    distance = list()
    for i in range(len(start_column)):
        ladder_cnt = i
        temp_dist = 0
        change_cnt = 0
        r, c = 0, start_column[i]

        for j in range(array_size - 1):
            r += 1

            if c > 0 and ladder[r][c-1] == 1: # 좌측 경로
                ladder_cnt -= 1
                c = start_column[ladder_cnt]
                temp_dist += line_to_line_distance(ladder_cnt + 1, ladder_cnt)
                change_cnt += 1
            elif c < array_size - 1 and ladder[r][c+1] == 1: # 우측 경로
                ladder_cnt += 1
                c = start_column[ladder_cnt]
                temp_dist += line_to_line_distance(ladder_cnt - 1, ladder_cnt)
                change_cnt += 1
            else:
                c = c
        
        distance.append(temp_dist + change_cnt)

    min_dist = 1e12
    min_idx = 0
    for i in range(len(distance)):
        if distance[i] <= min_dist:
            min_dist = distance[i]
            min_idx = start_column[i]

    ans.append(min_idx)

for i in range(repeat_number):
    print(f"#{i+1} {ans[i]}")

 

경로를 따라 가는 방식은 Ladder1 문제와 동일하다!

그러나 이 경우에는 모든 경로의 거리를 구하고 비교해주어야 해서 연산 횟수가 더 증가한다...

 

거리를 구한 방식은 내려가는 1의 갯수는 똑같기 때문에 제외하고, 좌측/우측 경로로 이동할 때마다 change_cnt에는 1씩, temp_dist에는 그 사이의 거리를 더해주었다...

 

고려해야할 점은 거리가 2인 직선 사이를 한 번 움직이는 것과 거리가 1인 직선 사이를 두 번 움직이는 것의 거리가 다르다는 것이다.. 따라서 change_cnt 변수를 만들어 해결해주었다!