[SWEA] 1210. Ladder1 (python)

난이도 D4.

스택과 큐 파트에 있던 문제인데 스택도 큐를 안쓰고 풀었다. 

사다리타기라 시뮬레이션만 하면 되는데, 어느 쪽에서 시작할지가 이 문제의 핵심 포인트였다. 

[문제]

100 x 100 배열에 사다리가 그려져 있다. 세로 막대는 1이 세로로 이어진 것이고, 가로선도 1로 그려져 있다. 나머지는 0이다. 바닥 어딘가에 2로 표시된 도착점이 있다.

사다리를 타는 규칙은 아는 그대로다. 아래로 내려가다가 좌우에 가로선이 나타나면 그쪽으로 꺾고, 옆 막대로 옮긴 뒤에는 다시 아래로만 간다. 바닥에 닿으면 끝이다.

2에 도착하려면 맨 윗줄 어느 x에서 출발해야 하는지를 구하면 된다. 테스트 케이스는 10개 고정이고, 한 막대에서 출발한 가로선이 다른 막대를 가로질러 이어지는 경우는 없다.

[내 풀이]

처음엔 그냥 0행의 모든 칸에서 하나씩 내려보낼까 했다. 100번 내려보내도 100 x 100이라 시간은 남는다. 그런데 사다리를 그려놓고 보니 굳이 그럴 필요가 없어 보였다.

사다리는 갈라지지 않는다. 어느 칸에서 출발하든 도착지가 딱 하나로 정해지고, 반대로 도착점에서 거슬러 올라가는 길도 딱 하나다. 그러면 2에서 출발해서 위로 한 번만 올라가면 답이 나온다.

올라가는 규칙은 내려가는 규칙을 그대로 뒤집으면 된다. 위로 가는 중이면 좌우에 가로선이 있나 보고, 있으면 그쪽으로 끝까지 간다. 가로선이 끝나면 다시 위로 간다. 0행에 닿으면 그때 x가 답이다.

여기서 헷갈렸던 게 "끝까지 간다"를 어떻게 표현하냐는 거였다. 가로선을 타고 가다가 중간에 위로 꺾어버리면 안 되고, 반대로 가로선 끝에 도착했는데 계속 옆으로 가려고 해도 안 된다. 그래서 지금 어느 방향으로 가는 중인지를 prev_dir에 들고 다니기로 했다. 1이면 위, 2면 왼쪽, 3이면 오른쪽이다.

• prev_dir이 1(위)이면 왼쪽부터 보고, 없으면 오른쪽을 보고, 그것도 없으면 한 칸 위로
• 2(왼쪽)면 왼쪽만 계속 보고, 더 없으면 위로 꺾으면서 prev_dir을 1로
• 3(오른쪽)도 대칭

도착점은 마지막 줄에 있으니까 입력을 읽으면서 i == 99일 때 line.index(2)로 잡았다. 시작할 때 prev_dir을 1로 두고 시작하는 게 포인트인데, 바닥에서는 무조건 위로 올라가는 상황이기 때문이다.

# 상, 좌, 우
dr, dc = [-1, 0, 0], [0, -1, 1]

for test_case in range(1, 11):
    tc = int(input())
    ladder = []
    for i in range(100):
        line = list(map(int, input().split()))
        ladder.append(line)
        # 도착지점 찾기
        if i == 99:
            end = (99, line.index(2))

    # 도착지점부터 올라갈건데, 처음 한번은 무조건 올라가고 시작
    row, col = end[0], end[1]
    # 이전 이동방향 -> 좌/우로 이동중이었다면 좌/우 그대로 가거나 길이 없을 때 위로 꺾어야함(1/2/3)
    prev_dir = 1
    while row > 0:
        if prev_dir == 1:
            # 위로 이동중이었다면, 왼쪽/오른쪽에 길이 있나 확인부터 합시다.
            if 0 <= (col - 1) and ladder[row][col-1] == 1:
                col -= 1
                prev_dir = 2
                continue
            elif (col + 1) < 100 and ladder[row][col+1] == 1:
                col += 1
                prev_dir = 3
                continue
            else: # 왼쪽 / 오른쪽에 길이 없다면 위로 한칸 올라가
                row -= 1
                continue
        elif prev_dir == 2: # 좌로 이동중이였다면
            if 0 <= (col - 1) and ladder[row][col-1] == 1:
                col -= 1
                prev_dir = 2
                continue
            else:
                row -= 1
                prev_dir = 1
                continue
        else: # 우로 이동중이였다면
            if (col + 1) < 100 and ladder[row][col+1] == 1:
                col += 1
                prev_dir = 3
                continue
            else:
                row -= 1
                prev_dir = 1
                continue

    print(f"#{test_case} {col}")

[AI 피드백]

검증은 정방향 완전탐색으로 했다. 0행의 모든 출발점을 실제로 내려보내서 2에 닿는 놈을 찾는 참조 구현을 따로 짜고, 무작위 사다리 1,400케이스를 내 코드와 대조했다. 연속한 행에 같은 막대쌍을 잇는 가로선을 일부러 잔뜩 깔아둔 심술 케이스도 섞었는데 전부 일치했다.

항목	배점	점수	근거
정확성	40	40	참조 구현과 무작위 1,400케이스 전부 일치. 가로선이 연속으로 붙은 케이스도 통과
효율성	30	30	10케이스 0.02초. 사실상 입력 읽는 시간이 전부다
코드 품질	20	15	한 번도 안 쓰는 dr, dc 가 맨 위에 있고, 같은 일을 하는 분기가 세 벌 반복된다
접근 판단	10	9	역추적을 스스로 골랐다. 다만 방향을 상태로 들 필요까지는 없었다
총점	100	94

잘한 점

역추적을 고른 게 이 문제의 전부다. 정방향으로 100번 내려보내도 통과하긴 하는데, 사다리에 갈림길이 없다는 걸 보고 "그럼 거꾸로 한 번이면 되겠네"까지 간 게 좋았다. 이건 그래프에서 도착점 하나짜리 역방향 탐색이랑 같은 발상이고, 나중에 시작점이 많고 도착점이 하나인 문제에서 그대로 써먹을 수 있다.

prev_dir = 1로 시작한 것도 정확하다. 바닥에서 시작할 때 좌우를 먼저 보게 되는데, 이게 맞는 이유는 내려오는 사람이 마지막 행에서도 가로선을 만나면 꺾기 때문이다. 주석에 "처음 한번은 무조건 올라가고 시작"이라고 적어둔 걸 보면 이 자리를 그냥 넘기지 않고 한 번 생각했다는 게 보인다.

경계 검사도 빠짐없다. 0 <= (col - 1)과 (col + 1) < 100을 좌우 양쪽에 전부 붙였다. 파이썬은 음수 인덱스가 조용히 반대쪽을 읽어버려서 안 터지고 틀리는데, 그 함정을 피했다.

부족한 점

한 번도 안 쓰는 dr, dc가 맨 위에 있다 (품질 −2). dr, dc = [-1, 0, 0], [0, -1, 1]은 DFS/BFS 템플릿의 잔해다. 이 코드는 델타 배열을 한 번도 참조하지 않는다. 방향을 배열로 잡으려다가 prev_dir 방식으로 갈아탄 흔적 같은데, 갈아탄 뒤에 위를 안 지웠다.

이게 지난 문제에서도 똑같이 나왔던 자리다. 그때는 이중 루프를 지우면서 그 루프만을 위해 만들던 리스트를 안 지웠다. 코드를 다 쓰고 나서 맨 위부터 한 번 훑으면 둘 다 30초면 잡힌다.

방향을 상태로 세 개나 들고 다녔다 (품질 −2). prev_dir 2와 3이 하는 일은 "그 방향으로 계속 간다" 하나뿐이다. 이걸 상태로 만들면 갈래가 일곱 개로 늘어나고 조건식이 통째로 두 번씩 반복된다.

"끝까지 간다"를 안쪽 while로 옮기면 상태가 통째로 사라진다. 바깥 루프를 한 바퀴 돌 때마다 무조건 한 행 올라가게 되니까, "지금 어느 방향인가"를 기억할 자리 자체가 없어진다.

continue가 아홉 개 있는데 전부 없어도 된다 (품질 −1). 각 분기의 마지막 줄이라 어차피 다음 반복으로 넘어간다. 흐름을 강조하려고 붙인 것 같은데, 오히려 "여기서 뭔가 건너뛰나?" 하고 한 번 더 읽게 만든다.

개선판

import sys

def main():
    data = sys.stdin.buffer.read().split()
    p = 0
    out = []
    for tc in range(1, 11):
        p += 1                                   # 테스트케이스 번호
        g = [data[p + r*100 : p + r*100 + 100] for r in range(100)]
        p += 10000
        r, c = 99, g[99].index(b'2')
        while r:
            if c and g[r][c-1] == b'1':          # 왼쪽 가로선을 끝까지
                while c and g[r][c-1] == b'1': c -= 1
            elif c < 99 and g[r][c+1] == b'1':   # 아니면 오른쪽 가로선을 끝까지
                while c < 99 and g[r][c+1] == b'1': c += 1
            r -= 1
        out.append(f"#{tc} {c}")
    sys.stdout.write('\n'.join(out) + '\n')

main()

걷는 길은 내 코드와 한 칸도 다르지 않다. 달라진 건 세 가지다. prev_dir 세 상태가 안쪽 while 두 줄로 접혔고, int 변환을 안 하고 바이트 조각을 그대로 비교하고, 입력을 한 번에 읽는다. 이 개선판도 같은 참조 구현으로 800케이스를 대조해서 전부 맞는 걸 확인했다.

맺음말

역추적까지는 잘 갔는데 "끝까지 간다"를 상태로 풀지 루프로 풀지에서 어려운 쪽을 골랐다.

상태를 하나 만들기 전에 안쪽 루프로 되는 일인지 먼저 봐야겠다.