[SWEA][D4][#01210] Ladder1

출처

• 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 생략

제약 사항

한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다.

입력

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

총 10개의 테스트 케이스가 주어진다.

출력

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

예제

입력

1
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 ...
1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 ...
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
...

출력

#1 67
...

My Sol

# 함수 정의
def check9(mat, i, j):
    if j == 0:
        return 0
    elif mat[i][j-1]:
        return 1

def check3(mat, i, j):
    if j == 99:
        return 0
    elif mat[i][j+1]:
        return 1

# 입력
T = 10
for _ in range(10):
    tc = int(input())
    mat = [list(map(int, input().split())) for _ in range(100)]

    # 사다리 막대 idx 찾음
    v_lst = []
    for j in range(100):
        if mat[99][j] > 0:
            v_lst.append(j)

    # v_lst에서 vs(2)의 순서를 찾음
    v_i = 0
    for v in v_lst:
        if mat[99][v] == 2:
            k = v_i
            break
        v_i += 1

    # 시작 설정
    ni, nj = 99, v_lst[k]
    # 시작
    while ni > 0:
        ni -= 1
        if check9(mat, ni, nj): # 9시 확인
            k -= 1
            nj = v_lst[k]
        elif check3(mat, ni, nj): # 3시 확인
            k += 1
            nj = v_lst[k]

    print(f'#{tc} {nj}')

맨 아래에 2로 표시된 목적지부터 위쪽으로 사다리를 타고 올라간다. 먼저 mat에 사다리에 대한 정보를 입력받아 2차원 배열로 저장한다. 위로 올라가다가 좌측이나 우측으로 분기점을 만나면 옆의 막대로 좌표를 이동해야 하고, 그 사이 간격에 대한 정보가 필요하다. 이때 맨 아래에서 2를 조회할 때 막대를 의미하는 1을 조회하며녀 막대마다 몇 개가 있는지, 얼마나 서로 차이를 두고 있는지를 알 수 있다. 이것을 처음에 v_lst에 저장해주었다.

v_lst에서 2를 찾아 v_lst 내에서의 인덱스를 확인하고, 이를 k로 두었다. 그렇다면 mat에서 2의 좌표는 mat[99][k]가 될 것이다. 좌표는 포커스의 이동에 따라 조금씩 변화할 것이므로 현재 좌표를 ni, nj로 두었다. 이후 ni가 0보다 큰 동안 계속 좌우를 확인하며 위로 올라가면 되겠다.

while 반복문 내부에 진입하면 일단 좌우가 0인 무결한 상태이므로 ni-=1, 즉 위로 한 칸 올라가주었다. 그리고 좌우를 확인하는데, 이때 함수를 사용하였다. 이동하여 위치한 현재 좌표와 mat 배열을 함수에 parameter로 전달하는데 좌측을 확인하는 check9() 함수는 nj-1 한 좌표에 1이 있다면 1을 반환, 아니면 0을 반환하는 것이다. 그렇다면 k를 1을 빼주는 것이다. k는 아까 2를 목적지로 가지고 있는 v_lst의 인덱스였고, k를 1 빼는 것은 그 전, 즉 왼쪽에 있는 사다리로 이동한다는 말이다. 이후 조정된 k를 v_lst의 인덱스로 하여 nj를 계산해내면 되는 것이다. 우측을 확인하는 check3()도 같은 로직으로 작성되었다.

이렇게 좌우측을 확인하며 1이 있다면 옆 막대로 이동하면서 ni가 0이 되면 그때의 nj를 출력하면 되겠다.

결과

PASS