오늘은 알고리즘에 대한 예제?를 한 번 풀어보고자 한다.

다음의 문제는 SWEA(SW Expert Academy)라는 Samsung에서 운영하는 알고리즘 예제 사이트이다.
(https://swexpertacademy.com/main/main.do)

사다리(2일차 - Ladder1)

문제 설명

점심 시간에 산책을 다니는 사원들은 최근 날씨가 더워져,
사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기로 한다.
김 대리는 사다리타기에 참여하지 않는 대신 사다리를 그리기로 하였다.
사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 X표시에 도착하게 되는지 궁금해졌다. 이를 구해보자.
아래 <그림 1>의 예를 살펴보면, 출발점 x=0 및 x=9인 세로 방향의 두 막대 사이에 임의의 개수의 막대들이 랜덤
간격으로 추가되고(이 예에서는 2개가 추가됨) 이 막대들 사이에 가로 방향의 선들이 또한 랜덤하게 연결된다.
X=0인 출발점에서 출발하는 사례에 대해서 화살표로 표시한 바와 같이,
아래 방향으로 진행하면서 좌우 방향으로 이동 가능한 통로가 나타나면 방향 전환을 하게 된다.
방향 전환 이후엔 다시 아래 방향으로만 이동하게 되며, 바닥에 도착하면 멈추게 된다.
문제의 X표시에 도착하려면 X=4인 출발점에서 출발해야 하므로 답은 4가 된다. 해당 경로는 별도로 표시하였다.

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

• [제약사항]
  한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다.

• [입력]
  입력 파일의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.
  총 10개의 테스트 케이스가 주어진다.

• [출력]
  #부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도착하게 되는 출발점의 x좌표를 출력한다.

---

즉, 우리는 2라는 값을 얻기 위해 n x n 배열의 사다리를 역으로 거슬로 올라가면서 구하면 되겠다.

for _ in range(10):# 문제에서와 같이 10개의 케이스를 해결하기 위해 반복문을 10번 실행한다.
    arr = []# n x n 배열의 사다리를 담기 위한 arr리스트
    n = 100 # 배열은 100 x 100이 된다
    test_num = int(input()) # 몇 번째 테스트인지 입력받는 변수

행 씩 들어오는 입력 배열을 arr에 2차원 배열로 넣어봅시다.
그리고 우리가 원하는 값 (2)이 어느 인덱스에 있는지 구한다.
또한, 우리는 아래서부터 거꾸로 거슬러 올라갈 것이기 때문에 y는 99로 초기화한다.

for i in range(n):
        arr.append(list(map(int, input().split())))
    x = find_x(arr)
    y = 99

갈림길이 나오면 주석에 채울 코드를 실행하고, y의 값을 줄인다.
y가 0일때, 우리가 원하는 x값이 나올 것이다.

while y > 0:
        # 사다리 거꾸로 거슬러 오르는 코드
        # 갈림길을 만나면 왼쪽으로 갈지 오른쪽으로 갈지 정한다.
        y -= 1

while문 안 코드

현재 값에서 왼 쪽과 오른쪽 값을 확인하며, 값에 따라 왼쪽 혹은 오른쪽으로 이동한다.

	if x == 0: #현재 사다리의 맨 왼쪽에 있으므로 오른쪽 값만 확인한다
        if arr[y][x+1] == 1:
            while arr[y][x+1] == 1:
                x += 1
    elif x == 99:#현재 사다리의 맨 오른쪽에 있으므로 왼쪽값만 확인한다
        if arr[y][x-1] == 1:
            while arr[y][x-1] == 1:
                x -= 1
    else:
        if arr[y][x+1] == 1:#사다리의 중간에 있으므로 왼쪽 오른쪽 모두 확인한다.
            while arr[y][x+1] == 1:
                x += 1
                if x == 99:
                    break
        elif arr[y][x-1] == 1:
            while arr[y][x-1] == 1:
                x -= 1
                if x == 0:
                    break

x의 위치를 결과로 출력해본다.

print('#{} {}'.format(test_num, x))

결과화면

전체코드

def find_x(arr):
    return arr[len(arr)-1].index(2)
#
for _ in range(10):
    arr = []
    n = 100
    test_num = int(input())
#
    for i in range(n):
        arr.append(list(map(int, input().split())))
    x = find_x(arr)
    y = 99
#
    while y > 0:
        if x == 0:
            if arr[y][x+1] == 1:
                while arr[y][x+1] == 1:
                    x += 1
        elif x == 99:
            if arr[y][x-1] == 1:
                while arr[y][x-1] == 1:
                    x -= 1
        else:
            if arr[y][x+1] == 1:
                while arr[y][x+1] == 1:
                    x += 1
                    if x == 99:
                        break
            elif arr[y][x-1] == 1:
                while arr[y][x-1] == 1:
                    x -= 1
                    if x == 0:
                        break
        y -= 1
    print('#{} {}'.format(test_num, x))