1210 - Ladder1

박재현·2022년 2월 15일
0

알고리즘 부수기

목록 보기
23/43
post-thumbnail

문제 설명

링크

문제 풀이

각 위치에서 방향과 인덱스를 고려해주어야 하기 때문에 재귀함수로 구현하였다.

  1. 맨 아래의 2 원소가 있는 인덱스를 찾는다.
  2. 해당 인덱스를 시작으로 재귀함수를 사용해 아래에서 위로 올라간다.
  3. 올라가는 방향은 direction = 0, 왼쪽 방향은 direction = -1, 오른쪽방향은 direction = 1 로 설정한다.
  4. 올라가는 방향일 경우 왼쪽 또는 오른쪽에 인덱스가 존재하는지 확인한 후 있으면 길이 있는지 확인한다.
  5. 왼쪽 또는 오른쪽 방향일 경우 위쪽에 인덱스가 존재하는지 확인한 후 있으면 길이 있는지 확인한다.
  6. 맨 꼭대기에 도착할 경우 값을 리턴한다.

개인적으로 어려웠지만 뿌듯한 문제중 하나이다.

코드

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
profile
공동의 성장을 추구하는 개발자

0개의 댓글