2일차 - Ladder1

array_size = 100
ans = list()

for _ in range(10):
    _ = int(input())
    ladder = [list(map(int, input().split())) for _ in range(array_size)]
    start = ladder[-1].index(2)

    line_number = list()
    for i in range(array_size):
        if ladder[0][i] == 1:
            line_number.append(i)
    line_cnt = line_number.index(start)

    r, c = array_size - 1, start # row, column
    for i in range(array_size - 1):
        r -= 1
        if c > 0 and ladder[r][c-1] == 1: # 좌측에 1
            line_cnt -= 1
            c = line_number[line_cnt]
        elif c < array_size - 1 and ladder[r][c+1] == 1: # 우측에 1
            line_cnt += 1
            c = line_number[line_cnt]
        else: # 양쪽에 경로가 없을 때
            c = c # 그대로 유지

    ans.append(c)

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

 

처음에는 첫 줄에 값이 1인 곳에서 전부 내려가서 어디로 가는지 계산한 후 마지막에 비교하여 구하는 브루트 포스 방식으로 구현할까 생각했는데, 고민해보니 그냥 2에서 위로 올라가는 역추적 방식으로 구현하면 답이 나오는 문제여서 그렇게 구현했다.

 

사다리 별로 순서를 매겨주고 (line_cnt) 그 column 값을 따로 저장해줬다 (line_number)

그 후 위로 올라가면서 좌측에 길이 나오면 line_cnt의 값을 1 빼주고 column값을 line_number를 이용해 바꿔준다.

마찬가지로 우측에 길이 나오면 line_cnt의 값을 1 더해주고 column값을 line_number를 이용해 바꿔준다.

 

끝~