BOJ 4921 - 나무 블록

문제

BOJ 4921 - 나무 블록

나무 블록 모양을 나타내는 숫자 시퀀스가 유효한지 판별하는 문제다. 블록은 8가지 모양(1~8)이 있으며, 각 모양에서 이어질 수 있는 다음 모양이 정해져 있다. 시퀀스는 반드시 1로 시작하고 2로 끝나야 하며, 연결 규칙을 모두 만족해야 VALID이다.

입력

• 여러 테스트 케이스 (0이 단독으로 오면 종료)
• 각 줄: 공백 없이 붙여쓴 블록 번호 시퀀스 (예: 1452)

출력

• 각 테스트 케이스에 대해 n. VALID 또는 n. NOT 출력 (n은 1부터 시작하는 케이스 번호)

예제

풀이

블록 연결 규칙을 딕셔너리로 미리 정의하고, 시퀀스의 시작/끝 조건과 인접 쌍 연결 가능 여부를 순차 검사하는 조건 분기 문제다.

1. 각 블록 번호를 키, 다음에 올 수 있는 블록 번호 집합을 값으로 하는 딕셔너리 d를 정의한다.
2. 0이 입력되면 종료한다.
3. 시퀀스의 첫 문자가 1이 아니거나 마지막 문자가 2가 아니면 NOT을 반환한다.
4. 인접한 두 블록 쌍 (s[i], s[i+1])에 대해 s[i+1]이 d[s[i]]에 포함되지 않으면 NOT을 반환한다.
5. 모든 검사를 통과하면 VALID를 반환한다.

핵심 아이디어: 연결 가능한 다음 블록을 set으로 관리하면 in 연산으로 O(1) 검사가 가능하다. 시작/끝 조건을 먼저 확인하면 불필요한 탐색을 줄일 수 있다.

코드

import sys
 
input = sys.stdin.readline
d = {
    "1": {"4", "5"},
    "2": {},
    "3": {"4", "5"},
    "4": {"2", "3"},
    "5": {"8"},
    "6": {"2", "3"},
    "7": {"8"},
    "8": {"6", "7"},
}
 
 
def f(s):
    if s[0] != "1" or s[-1] != "2":
        return "NOT"
    for i in range(0, len(s) - 1):
        if s[i + 1] not in d[s[i]]:
            return "NOT"
    return "VALID"
 
 
i = 0
while True:
    s = list(input().rstrip())
    if s == ["0"]:
        break
    i += 1
    print(f"{i}.", f(s))

복잡도

• 시간: O(N) — 시퀀스 길이 N에 대해 선형 순회
• 공간: O(1) — 딕셔너리는 고정 크기 (블록 종류 8개)