각 위치에서 방향과 인덱스를 고려해주어야 하기 때문에 재귀함수로 구현하였다.
- 맨 아래의 2 원소가 있는 인덱스를 찾는다.
- 해당 인덱스를 시작으로 재귀함수를 사용해 아래에서 위로 올라간다.
- 올라가는 방향은 direction = 0, 왼쪽 방향은 direction = -1, 오른쪽방향은 direction = 1 로 설정한다.
- 올라가는 방향일 경우 왼쪽 또는 오른쪽에 인덱스가 존재하는지 확인한 후 있으면 길이 있는지 확인한다.
- 왼쪽 또는 오른쪽 방향일 경우 위쪽에 인덱스가 존재하는지 확인한 후 있으면 길이 있는지 확인한다.
- 맨 꼭대기에 도착할 경우 값을 리턴한다.
개인적으로 어려웠지만 뿌듯한 문제중 하나이다.
def move(x, y, direction, arr):
if direction == 0:
if y+1 <= 99 and arr[x][y+1] == 1:
return move(x, y+1, 1, arr)
if y - 1 >= 0 and arr[x][y - 1] == 1:
return move(x, y - 1, -1, arr)
if x-1 >= 0 and arr[x-1][y] == 1:
return move(x-1, y, 0, arr)
if x == 0:
return y
if direction == 1:
if x-1 >= 0 and arr[x-1][y] == 1:
return move(x-1, y, 0, arr)
if y+1 <= 99 and arr[x][y+1] == 1:
return move(x, y+1, 1, arr)
if direction == -1:
if x-1 >= 0 and arr[x-1][y] == 1:
return move(x-1, y, 0, arr)
if y - 1 >= 0 and arr[x][y - 1] == 1:
return move(x, y - 1, -1, arr)
for T in range(10):
tc = int(input())
arr = [list(map(int, input().split())) for _ in range(100)]
for i in range(100):
if arr[99][i] == 2:
print(f'#{tc} {move(99, i, 0, arr)}')
break