Hikenny25
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를 이용해 바꿔준다.
끝~
'SW Expert Academy > Programming - Intermediate' 카테고리의 다른 글
5일차 - 토너먼트 카드게임 (1) | 2023.12.12 |
---|---|
2일차 - Ladder2 (1) | 2023.12.11 |
2일차 - Sum (1) | 2023.12.11 |
1일차 - Flatten (0) | 2023.12.11 |
1일차 - View (1) | 2023.12.10 |
Comments