Ladder2 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 1211

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14BgD6AEECFAYh&categoryId=AV14BgD6AEECFAYh&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

이거 문제 설명이 개판이다. 요약정리 하면 사다리를 내려갔을때 제일 빠르게 내려가는 x의 위치를 찾으라 이다. 마지막에 2로 적힌 부분이 없다.

 

입력

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다. 총 10개의 테스트 케이스가 주어진다.

 

출력

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다. 총 10개의 테스트 케이스가 주어진다.

예시

입력	출력
홈페이지 참조	홈페이지 참조

---

2. 문제풀이

Ladder1과 비슷한데 다른점은 하나이다. Ladder1은 목적지가 있어서 거기서 타고 올라가면 쉽게 풀수 있었는데 Ladder2는 최단거리를 찾는 것이다. 따라서 위에서 시작하거나 밑에서 올라갈때 이동할때마다 count를 하여 제일 적은 count를 자장하고 그에 해당하는 x위치를 리턴하면 된다.

---

3. 소스코드

#D4 1211 Ladder2
 
T = 10
for t in range(T):
    test = int(input())
    #100번돌면서 데이터를 받는다.
    ladder = [list(map(int, input().split())) for _ in range(100)]
    #사다리 길이중 제일 적은길이 저장용
    min_count = 10000
    #제일짧은 사다리의 위치를 저장
    return_x = 0
    #제일뒤부터 앞까지 1인위치를 찾아 저장한다.
    #그냥 range(100)으로 넣어도 상관이없다. 그냥 뒤로했다.
    start_list = [i for i in range(99, -1, -1) if ladder[0][i]]
    #시작할수있는 포인트만큼 반복
    for start in start_list:
        #이동을 위해 좌표셋팅
        #제일 위에서부터 시작하므로 y좌표는 0이다.
        d_y = 0
        #x좌표는 1인곳에서 시작해야하고 그것은 start에 들어있다.
        d_x = start
        #현재 사다리의 이동칸수를 저장하기 위한 변수
        count = 0
        #좌우이동을 방지하기 위한 변수이다.
        move = 0
        #y축이 99가 될때까지 반복한다.
        #99라면 제일 밑이므로 더이상 계산할 필요가 없다.
        down = 0
        left = 1
        right = 2
        while d_y < 99:
            #밑으로 내려갔거나 왼쪽으로 이동했었다면
            #왼쪽으로 갈때 벽이 아닌지 확인하고
            #벽이 아니라면 1인지 체크한다.
            if (move == down or move == left) and d_x > 0 and ladder[d_y][d_x-1]:
                #위의 조건을 통과했다면 왼쪽으로 이동후
                #이동했던 행동을 left로 기록한다.
                d_x -= 1
                move = left
            #밑으로 내려갔거나 오른쪽으로 이동했었다면
            #오른쪽으로 갈때 벽이 아닌지 확인하고
            #벽이 아니라면 1인지 체크한다.
            elif (move == down or move == right) and d_x < 99 and ladder[d_y][d_x+1]:
                #위의 조건을 통과했다면 오른쪽으로 이동후
                #이동했던 행동을 right로 기록한다.
                d_x += 1
                move = right
            #왼쪽도 오른쪽도 못간다면 아래로 내려간다.
            #내려갈수있는지 체크했지만 그냥 else로 적어도 무방하다.
            elif ladder[d_y + 1][d_x]:
                #아래로 이동하고 행동을 down으로 바꾼다.
                d_y += 1
                move = down
            #이동을 할때마다 count를 기록해준다.
            count +=1
            #이동행동을 체크하는 이유는
            #오른쪽으로 이동후 왼쪽과 오른쪽이 1인경우가 생긴다.
            #그때 무한루프에 빠질수있으므로 단방향으로 이동하기위해 사용한다.
        #끝까지 내려왔다면 이동했던 count를 현재 최소카운트와 비교한다.
        if min_count > count: 
            #현재 거리가 더짧다면 count를 갱신한다.
            min_count = count
            #출발했던 좌표또한 기록한다.
            return_x = start
    #모두 반복하여 여기까지 왔다면 결과를 출력한다.
    print("#{} {}".format(test, return_x))