[SWEA] 1210. Ladder1 - Python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh 

SW Expert Academy

 

< 📝 문제 >

점심시간에 산책을 다니는 사원들은 최근 날씨가 더워져, 사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기

 

로 한다. 김 대리는 사다리 타기에 참여하지 않는 대신 사다리를 그리기로 하였다.

사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 X 표시에 도착하게 되는지 궁금해졌다. 이를 구해보자.

아래 <그림 1>의 예를 살펴보면, 출발점 x=0 및 x=9인 세로 방향의 두 막대 사이에 임의의 개수의 막대들이 랜덤 간격

 

으로 추가되고(이 예에서는 2개가 추가됨) 이 막대들 사이에 가로 방향의 선들이 또한 랜덤하게 연결된다.

X=0인 출발점에서 출발하는 사례에 대해서 화살표로 표시한 바와 같이, 아래 방향으로 진행하면서 좌우 방향으로 이동

 

가능한 통로가 나타나면 방향 전환을 하게 된다.

 

방향 전환 이후엔 다시 아래 방향으로만 이동하게 되며, 바닥에 도착하면 멈추게 된다.

문제의 X표시에 도착하려면 X=4인 출발점에서 출발해야 하므로 답은 4가 된다. 해당 경로는 별도로 표시하였다.

<그림 1> 사다리 게임에 대한 설명 (미니맵)

아래 <그림 2>와 같은 100 x 100 크기의 2차원 배열로 주어진 사다리에 대해서, 지정된 도착점에 대응되는 출발점 X를

 

반환하는 코드를 작성하라 (‘0’으로 채워진 평면상에 사다리는 연속된 ‘1’로 표현된다. 도착 지점은 '2'로 표현된다).
 

<그림 2> 테스트 케이스에 의해 생성되는 실제 사다리의 모습

< ❓ 생각 >

1. 도착지점에서 거꾸로 올라가기!!

(위쪽, 오른쪽, 왼쪽으로 이동)

양쪽 중 1이 있으면 그쪽으로 이동( 다시 0이 나오거나 범위를 벗어날 때까지)

없으면 계속 위로 이동하기

-> 행의 위치가 0일때까지

 

2. 위에서 내려가기(0행에 1인 지점에서 내려가서 도착지점에 도착하는가 확인)

0행을 검사해서 시작점이라면 시작

(아래쪽, 오른쪽, 왼쪽으로 이동)

움직이는 방향을 바꿔야 하는지 검사

아래쪽 - > 좌 or 우로 갈 수 있음

좌 or 우 -> 아래쪽으로 갈 수 있음

 

< 💻 코드 >

1. 

T = 10
for tc in range(1,T+1):
    # N : 테스트 케이스의 번호
    N = int(input())
    # arr : 1-사다리, 0-여백, 2-도착지점
    arr = [list(map(int,input().split())) for _ in range(100)]

    # 도착지점에서 거꾸로 찾아가기
    
    # 도착지점 2가 어디에 있는지 idx 찾기
    # end : 사다리 결과 도착지점, 거꾸러 찾아가는 길의 시작지점
    end_r = 99
    end_c = 0
    for j in range(100):
        if arr[99][j] == 2:
            end_c = j

    # 오른쪽 or 왼쪽에 1 있을 경우 따라서 이동
    # 없으면 위로 이동

    # 위에 아무것도 없다면(arr[0][]) 이면 멈춰서 그 자리의 열의 위치 말하기
    while end_r != 0:
        # 오른쪽이 1이면 오른쪽에 0이 나올때까지 이동 + 위로 한 칸 이동
        if 0 <= end_c+1 <=99 and arr[end_r][end_c+1]:
            while end_c+1 <= 99 and arr[end_r][end_c+1]:
                end_c += 1
            end_r -= 1
        # 왼쪽이 1이면 왼쪽에 0이 나올때까지 이동 + 위로 한 칸 이동
        elif 0 <= end_c-1 <=99 and arr[end_r][end_c-1]:
            while 0 <= end_c-1 and arr[end_r][end_c-1]:
                end_c -= 1
            end_r -= 1
        # 옆에 1이면 위로 이동
        else:
            end_r -= 1

    print(f'#{N} {end_c}')

2.

T = 10
for _ in range(1,T+1):
    tc = int(input())
    ladder = [list(map(int,input().split())) for _ in range(100)]
    # 사다리 타기 시작
    # 0행을 검사를 해서 시작점이라면(1이라면) 시작
    
    # 아래쪽, 오른쪽, 왼쪽
    dr = [1, 0, 0]
    dc = [0, 1, -1]
    
    result = 0
    
    for i in range(100):
        if ladder[0][i]: # 시작점 찾음
            # 현재 위치를 r, c로 저장
            # 움직이는 방향을 지정 : 0아래쪽, 1오른쪽, 2왼쪽
            # 현재 위치 + 움직이는 방향에 대한 변화량 더하기
            # 방향을 바꾸어야 하는 경우가 생기면 방향 바꾸기
                # 움직이는 방향 : 아래쪽 > 좌 or 우 갈 수 있음
                #               좌 or 우 > 아래쪽으로 갈 수 있음
            # 만약에, r이 99라면 멈춰!!
            # 현재위치
            r, c = 0, i
            d = 0
            while r < 99:
                # 움직이기 전에 방향을 바꾸는 경우가 있는지 검사
                # 움직이고 있는 방향에 따라서 방향을 바꾸는 검사가 다름
                
                if d == 0: # 아래쪽 방향으로 움직이고 있었다면
                    # 좌, 우 검사 << 양쪽에 0이 있으면 내려가기
                    if c > 0 and ladder[r][c-1]: # 왼쪽으로 갈 수 있을 때
                        d = 2
                    elif c < 99 and ladder[r][c+1]: # 오른쪽으로 갈 수 있을 때
                        d = 1
                        
                else: # 좌 or 우 방향으로 움직이고 있을 떄
                    if ladder[r+1][c]: # 아래쪽으로 갈 수 있을 때
                        d = 0
                        
                # 현재 움직이는 방향에 대해서 변화량 더하기
                r += dr[d]
                c += dc[d]
                
            # r이 99가 되면서 반복이 끝난 시점에서 ladder[r][c] == 2 라면,
            # i가 정답
            if ladder[r][c] == 2:
                result = i
                break # 정답을 찾았으니 끝
                
    print(f'#{tc} {result}')