[Python, 파이썬] SWEA 1211. [S/W 문제해결 기본] 2일차 - Ladder2

최단거리로 바닥에 도착하는 출발점 X를 구하는 문제.

 

100 x 100 크기의 2차원 배열로 주어진 사다리에 대해서, 모든 출발점을 검사하여 바닥까지 가장 짧은 이동 거리를 갖는 시작점 x(복수 개인 경우 가장 큰 x좌표)를 찾는 문제!

 

 

def find_starting_points(maps): # 출발점 목록
    return [i for i in range(100) if maps[0][i] == 1]

    
T = 10 # 테스트케이스의 개수 T

for test_case in range(1, T+1):

    test_case = int(input()) # 테스트케이스 번호
    maps = [list(map(int, input().split())) for _ in range(100)]  # 맵 입력

    # 시작점 찾기
    starting_points = find_starting_points(maps)
    min_distance = float('inf')
    best_start = 0

    for start in starting_points: # 출발점 순회

        distance = 0 # 현재 출발점에서 목적지까지 가는 거리
        j = start # 출발점

        for i in range(100):

            distance += 1
            
            if(j > 0 and maps[i][j-1]): # 왼쪽 사다리가 있을 시
                while(j > 0 and maps[i][j-1]):
                    distance += 1 # 거리 +1
                    j -= 1 # 왼쪽으로 이동
                continue

            if(j < 99 and maps[i][j+1]): # 오른쪽 사다리가 있을 시
                while(j < 99 and maps[i][j+1]):
                    distance += 1 # 거리 +1
                    j += 1 # 오른쪽으로 이동
                continue

        if distance < min_distance: # 최단 거리가 있을 시
            min_distance = distance # 최단 거리 갱신
            best_start = start # 최단 거리 출발점 저장

    print("#%d %d" % (test_case, best_start))

 

 

 

 

[문제풀이]

---

 

SWEA 1210 사다리 문제의 확장판.

모든 출발점에서 사다리 타고 밑으로 내려오며 거리를 재고, 그 중 최단거리를 찾으면 된다.

 

우선 출발점들의 목록 starting_points을 찾는다.

그 후 출발점들 하나하나 사다리를 타고 내려오면서 거리를 재면 된다.

distance += 1

if(j < 99 and maps[i][j+1]): # 오른쪽 사다리가 있을 시
    while(j < 99 and maps[i][j+1]):
        distance += 1 # 거리 +1
        j += 1 # 오른쪽으로 이동
    continue

 

코드 자체는 SWEA 1210이랑 거의 동일하다.

다만 for문을 돌릴때, 그리고 사다리를 타고 이동할 때 이 distance를 +1 해주면 끝.

if distance < min_distance: # 최단 거리가 있을 시
    min_distance = distance # 최단 거리 갱신
    best_start = start # 최단 거리 출발점 저장

 

그리고 마지막에 현재 거리가 더 최단거리일 시, 최단 거리를 갱신하고 그 출발점 위치를 저장한다.

이렇게 모든 출발점들의 거리를 검사한 후 저장되어 있던 best_start가 최단 거리를 가지는 출발점이다.