Python으로 푸는 SW Expert Academy 1210. Ladder1

SW Expert Academy 1210. Ladder1

 문제는 2차원 배열로 표현된 사다리를 타고 내려가서

표시된 도착 지점에 도달하는 스타트 지점을 찾아 위치 정보를 반환하도록 구현해야 한다.

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

github에서 코드 보기

문제 조건

도착 지점은 2로 표시되어 있으며, 0은 길이 아니고, 1이 길이다. 

좌우 방향으로 이동 가능한 통로가 나타나면 방향 전환을 해야 한다.

문제 풀이

어차피 도착 지점에 대응되는 출발점을 찾는 것이므로 

모든 출발지점을 다 탐색할 필요 없이,  도착 지점에서부터 출발하여 도달할 수 있는 출발 지점을 찾아 이동하는 코드를 짠다.

좌우로 이동이 가능하면 방향을 전환해 위로 다시 이동이 가능할 때까지 그 방향으로 전진해야 한다는 점이 핵심이다.

일단 통로에 들어선다면 위로 다시 이동이 가능한지를 살피면서 이동해왔던 방향으로 전진해야 한다.

안그러면 통로에서 왔다갔다 반복하는 무한 루프에 빠질 수가 있다.

파이썬 코드

def solve(ladder):
    start_x, start_y = 99, ladder[99].index(2)
    left = (0, -1)
    right = (0, 1)
    up = (-1, 0)
    next_check_direction = [left, right, up]
    while start_x > 0:
        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
 
    return start_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))

#1210. Ladder1 #python 1210. Ladder1 #1210. Ladder1 python #sw expert 1210 Ladder1 #파이썬 1210 Ladder1 # SW Expert Academy 1210. Ladder1