Python으로 푸는 SW Expert Academy 1211. Ladder2

1211. Ladder2

문제는 2차원 배열의 0번째 줄부터 99번째 줄까지 가장 적은 칸을 이동하여 도달할 수 있는 시작점을 찾고,

그 시작점의 (0, X)의 X 값을 반환할 수 있도록 구현해야 한다.

삼성 SW Expert Academy에서 푼 문제 리스트 보기

github에서 코드 보기

문제 조건

문제 조건은 1210. Ladder1 유사하다. 

단, 도착 지점이 한 곳이 아니며, 가장 아래 도착지점에 가장 적은 칸을 이동하여 도달한 시작점의 값을 반환하여야 한다.

문제 풀이

문제는 1210. Ladder1 코드를 조금만 바꾸면 된다. 탐색해야 하는 부분은 도착지점의 모든 지점과 연결된 시작 지점이다.

기존 2110. Ladder1의 코드를 응용하기 위해서 모든 도착 지점을 리스트에 넣고 하나씩 꺼내 경로를 탐색한다.

꺼낸 도착지점에서부터 시작지점까지 사다리 타기의 조건에 맞춰서 이동하고 거쳐야 하는 칸들의 수를 센다. 

가장 적은 칸을 이동한 (만약 같은 칸을 이동한 경로가 여러 개일 경우에는 가장 오른쪽에 시작점이 위치한) 시작점의 y 값을 반환한다.

파이썬 코드

 
def solve(ladder):
    start_list = []
    for i in range(99, -1, -1):
        if ladder[99][i] == 1:
            start_list.append((99, i))
 
    left = (0, -1)
    right = (0, 1)
    up = (-1, 0)
    min_count = 99999
    min_y = None
    while start_list:
        start_x, start_y = start_list.pop()
        next_check_direction = [left, right, up]
        count = 1
        while start_x > 0:
            count += 1
            add_x = 0
            add_y = 0
            for dir in next_check_direction:
                if checkPosition(ladder, (start_x, start_y), dir):
                    if dir == left:
                        start_y -= 1
                        next_check_direction = [left, up]
                    elif dir == right:
                        start_y += 1
                        next_check_direction = [right, up]
                    else:
                        start_x -= 1
                        next_check_direction = [left, right, up]
                    break
        if count < min_count:
            min_count = count
            min_y = start_y
    return min_y
 
 
# if it is route, return True
def checkPosition(ladder, current_pos, dir):
    x, y = current_pos
    temp_x = x + dir[0]
    temp_y = y + dir[1]
    if temp_x < 0 or temp_y < 0 or temp_x >= 100 or temp_y >= 100:
        return False
    if ladder[temp_x][temp_y] == 0:
        return False
    return True
 
 
def gen():
    lines = []
    for i in range(100):
        line = list(map(int, input().strip().split()))
        lines.append(line)
    yield lines
 
if __name__ == "__main__":
    for j in range(10):
        t = int(input())
        for lines in gen():
            result = solve(lines)
            print("#{0} {1}".format(t, result))

# 파이썬 1211 ladder2  #1211. Ladder2 #sw expert 1211  #python 1211 ladder2