구현 문제 - 시뮬레이션을 실수 없이
이 장에서 배우는 것
앞 장에서 입력 크기와 연산 횟수를 연결해 풀이의 실행 시간을 살펴보았다. 이번에는 정해진 규칙을 코드로 정확하게 옮기는 방법을 다룬다. 규칙이 짧다고 구현도 간단한 것은 아니다. 로봇을 한 칸 움직이는 문제에서도 현재 위치, 바라보는 방향, 장애물, 격자의 경계를 함께 처리해야 한다.
시뮬레이션(simulation)은 현재 상태에 규칙을 적용해 다음 상태를 만드는 과정이다. 핵심은 긴 코드를 빠르게 쓰는 데 있지 않다. 무엇을 상태로 저장할지 정하고, 한 단계가 바꾸는 것을 제한하며, 중간 결과를 손으로 계산한 결과와 맞추는 데 있다.
- 문제의 상태와 고정된 환경을 구분해 자료로 표현한다.
- 방향 배열로 이동을 나타내고, 경계와 장애물을 올바른 순서로 검사한다.
- 명령마다 상태를 출력해 처음 어긋나는 단계를 찾는다.
- 작은 함수로 규칙을 나누고, 작은 입력 전체를 별도 정답 구현과 대조한다.
문제 상황
공용 작업실에서 사용하는 간단한 제어 프로그램을 만든다고 하자. 먼저 회의실 표시등을 생각해 본다. 표시등은 꺼짐과 켜짐 중 하나이며, 버튼을 누를 때마다 상태가 바뀐다. 처음에는 꺼져 있고, 기록에 나타난 버튼 누름을 순서대로 반영한 뒤 최종 상태를 출력해야 한다. 이 문제에서는 현재 켜져 있는지만 알면 다음 상태를 결정할 수 있다.
두 번째 문제는 작업실 바닥을 이동하는 운반 로봇이다. 바닥은 직사각형 격자이고 일부 칸에는 물건이 놓여 있다. 로봇은 빈 칸 하나에서 출발해 북쪽, 동쪽, 남쪽, 서쪽 중 한 방향을 바라본다. 명령은 왼쪽 회전 L, 오른쪽 회전 R, 한 칸 전진 F다. 회전은 위치를 바꾸지 않는다. 전진할 칸이 격자 밖이거나 장애물이면 그 명령만 취소하고 다음 명령을 처리한다.
운영 기록을 확인할 수 있도록 명령 처리 후의 위치와 방향을 매번 출력해야 한다. 전진이 취소되었을 때도 상태를 출력하고, 취소 이유를 경계와 장애물로 구분한다. 좌표는 행과 열을 모두 0부터 센다. 행은 아래쪽으로, 열은 오른쪽으로 증가한다.
예시 바닥은 세 행과 네 열이다. 점은 빈 칸, #은 장애물이다. 시작 위치는 행 1, 열 0이고 시작 방향은 동쪽이다. 처리할 명령은 FFLFFRFF다. 모든 명령을 처리하면 프로그램은 종료된다.
상태를 먼저 적고 손으로 따라간다
표시등에는 한 값이면 충분하다
표시등 문제에서 버튼을 누른 횟수 전체를 보관할 필요는 없다. 다음 버튼의 결과는 현재 켜져 있는지만으로 정해지기 때문이다. 다음 코드는 버튼을 세 번 누르는 경우다. 출력은 True다.
is_on = False
for _ in range(3):
is_on = not is_on
print(is_on)여기서 상태는 is_on 하나다. 반복문이 버튼 누름을 하나 처리할 때마다 is_on을 뒤집는다. 버튼 누름 기록이 길어져도 상태를 저장하는 공간은 일정하다. 누름 횟수가 K라면 시간은 O(K), 추가 공간은 O(1)이다.
이 코드의 정확성은 짧게 설명할 수 있다. 처리 전에는 초기 상태인 꺼짐을 저장한다. 앞의 버튼 누름을 올바르게 반영했다고 가정하면, 다음 누름에서 값을 한 번 뒤집는 것은 문제의 규칙과 같다. 따라서 매 단계의 값은 그때까지의 누름을 반영한다. 마지막 반복이 끝나면 최종 상태가 남는다.
로봇에는 위치와 방향이 필요하다
로봇에서는 좌표만으로 다음 상태를 결정할 수 없다. 같은 칸에 있어도 북쪽을 볼 때와 동쪽을 볼 때 전진 결과가 다르다. 따라서 상태를 행 r, 열 c, 방향 d의 세 값으로 표현한다. 이 장에서는 세 값을 묶은 튜플 (r, c, d)를 사용한다. 튜플은 리스트처럼 여러 값을 순서대로 묶지만, 만든 뒤 원소를 직접 바꾸지 않는다. 상태가 바뀌면 새 튜플을 반환한다.
반면 바닥의 모양과 장애물 위치는 명령으로 바뀌지 않는다. 이 정보는 문자열 리스트 grid에 저장한다. 고정된 환경과 변하는 상태를 나누면 한 번의 명령이 무엇을 바꿨는지 확인하기 쉽다. 단계 번호는 진행 상황을 출력하기 위한 값이며, 로봇의 다음 행동을 결정하는 상태에는 포함하지 않는다.
| 정보 | 표현 | 바뀌는 때 |
|---|---|---|
| 바닥과 장애물 | 문자열 리스트 grid | 실행 중 바뀌지 않는다 |
| 현재 위치 | 상태의 r, c | 전진에 성공할 때 |
| 현재 방향 | 상태의 d | 회전할 때 |
| 진행 단계 | 반복문의 번호 | 명령을 하나 처리할 때 |
코드를 쓰기 전에 명령을 손으로 따라가 본다. 특히 회전 직후의 전진과 이동이 거절되는 순간을 확인한다. 예시에서 두 번째 전진 뒤에는 행 1, 열 2에 도착한다. 왼쪽으로 돌면 북쪽을 바라본다. 바로 위인 행 0, 열 2에는 장애물이 있으므로 이후 두 번의 전진은 모두 취소된다.
| 단계와 명령 | 처리 후 위치 | 방향 | 결과 |
|---|---|---|---|
| 0 시작 | (1, 0) | 동 | 초기 상태 |
| 1 F | (1, 1) | 동 | 이동 |
| 2 F | (1, 2) | 동 | 이동 |
| 3 L | (1, 2) | 북 | 회전 |
| 4 F | (1, 2) | 북 | 장애물 |
| 5 F | (1, 2) | 북 | 장애물 |
| 6 R | (1, 2) | 동 | 회전 |
| 7 F | (1, 3) | 동 | 이동 |
| 8 F | (1, 3) | 동 | 경계 |
방향 배열과 경계 검사로 한 단계를 만든다
방향의 순서를 고정한다
방향 번호를 북 0, 동 1, 남 2, 서 3으로 정한다. 이 순서는 시계 방향이다. 오른쪽 회전은 번호에 1을 더하고, 왼쪽 회전은 1을 뺀다. 결과를 4로 나눈 나머지로 바꾸면 번호가 다시 0부터 3 사이에 들어온다. 예를 들어 북쪽에서 왼쪽으로 돌면 (0 - 1) % 4의 값인 3, 곧 서쪽이 된다.
각 방향으로 전진할 때의 행 변화량은 (-1, 0, 1, 0), 열 변화량은 (0, 1, 0, -1)이다. 두 배열에서 같은 번호의 원소를 함께 사용한다. 동쪽의 번호가 1이므로 행은 그대로이고 열만 1 증가한다. 방향 이름, 행 변화량, 열 변화량의 순서는 서로 같아야 한다.
전진에서는 현재 좌표를 바로 고치지 않는다. 후보 좌표 nr, nc를 먼저 계산한다. 후보가 경계를 통과하고 빈 칸이라는 사실을 확인한 뒤에만 새 상태로 채택한다. 이렇게 하면 실패한 이동을 되돌리는 코드가 필요 없다.
경계를 확인한 뒤 칸을 읽는다
행 수를 H, 열 수를 W라고 하면 유효한 후보는 0 ≤ nr < H와 0 ≤ nc < W를 모두 만족해야 한다. 둘 중 하나라도 어기면 그 좌표의 칸을 읽어서는 안 된다. 특히 Python에서 음수 인덱스는 뒤에서부터 원소를 가리킨다. 위쪽 경계를 벗어난 행 -1을 읽었는데 마지막 행이 조회되면, 예외 없이 잘못된 이동이 발생할 수 있다.
한 단계 처리 함수는 환경, 현재 상태, 명령을 받아 새 상태와 처리 결과를 반환하도록 만든다. 출력은 별도 함수가 맡는다. 이동 규칙 안에 출력이 섞이지 않으면 작은 입력을 수천 번 검사할 때도 불필요한 기록이 생기지 않는다. 또한 한 명령을 시험할 때 전체 프로그램을 다시 구성할 필요가 없다.
상태가 지켜야 할 약속을 적는다
로봇의 불변식은 “각 명령을 처리한 뒤 위치는 격자 안의 빈 칸이고, 방향 번호는 0부터 3 사이이며, 상태는 지금까지의 명령을 순서대로 적용한 결과다”라는 문장으로 정리할 수 있다. 여기서 불변식은 단계가 바뀌어도 계속 참이어야 하는 약속이다.
시작 위치와 방향이 조건을 만족하므로 첫 명령 전에는 약속이 성립한다. 회전은 위치를 유지하고 나머지 연산으로 방향 범위를 지킨다. 전진은 유효한 빈 칸만 새 위치로 채택하며, 실패하면 이전 상태를 유지한다. 각 분기가 명령의 규칙과 일치하므로 다음 단계에서도 약속이 성립한다. 따라서 마지막 상태는 전체 명령을 순서대로 적용한 결과다.
출력으로 확인하고 작은 입력을 모두 대조한다
최종 위치만 비교하면 어디서 잘못되었는지 알기 어렵다. 단계별 기록에는 명령, 처리 후 위치, 방향, 처리 이유를 함께 넣는다. 손으로 만든 표와 출력의 첫 번째 차이를 찾으면 조사할 명령이 정해진다. 예를 들어 4단계에서 위치가 바뀌었다면 장애물 검사나 후보 좌표 계산을 먼저 살펴본다.
다만 예시 하나가 맞는다고 모든 경우가 맞는 것은 아니다. 완성 코드에는 작은 격자의 모든 경우를 대조하는 검사도 넣는다. 여기서는 2행 2열의 각 칸을 빈 칸이나 장애물로 정하는 모든 배치, 모든 빈 시작 칸, 네 시작 방향, 길이 0부터 3까지의 모든 명령열을 검사한다. 길이 0인 명령열도 포함해야 아무 명령이 없을 때 상태가 유지되는지 확인할 수 있다.
검사용 정답 함수는 방향을 숫자 대신 북·동·남·서라는 문자열로 저장한다. 회전은 대응 딕셔너리로, 이동은 방향별 조건문으로 처리한다. 바닥의 빈 칸은 집합에 모으고 후보 좌표가 그 안에 있는지 확인한다. 집합은 중복 없이 값을 모으며, 여기서는 좌표가 허용된 칸인지 검사하는 데 쓴다. 정답 함수는 호출할 때마다 바닥을 다시 훑으므로 실제 처리 함수보다 느리지만, 방향 배열과 경계 분기를 공유하지 않아 대조에 도움이 된다.
검사는 마지막 위치만 비교하지 않는다. 명령 하나를 처리할 때마다 두 구현의 위치와 방향을 비교한다. 마지막에 우연히 같은 위치로 돌아오는 오류도 중간 상태의 차이로 발견할 수 있다. 이 대조는 작은 범위에 대한 확인이며, 큰 격자 전체의 정확성 근거는 앞에서 설명한 불변식이 맡는다.
명령 수를 K라고 하면 실제 이동 처리는 명령마다 일정한 작업을 하므로 O(K) 시간이다. 바닥을 저장하는 공간은 O(HW), 상태를 유지하는 추가 공간은 O(1)이다. 단계별 기록은 리스트에 모으지 않고 바로 출력한다. 출력할 정수의 자릿수까지 세면 비용이 늘어나지만, 보통의 분석에서는 좌표 한 개의 계산과 출력을 일정한 비용으로 본다.
아래 프로그램은 예시 입력 문자열과 명령 문자열도 보관한다. 따라서 프로그램 전체가 입력을 저장하는 공간은 O(HW + K)다. 검사용 정답 함수는 한 번 호출할 때 O(HW) 시간과 공간을 사용한다. 이번 검사의 격자는 2행 2열로 고정되어 있어 실행할 경우의 수를 직접 셀 수 있다.
완성 코드
다음 내용을 main.py에 저장한다. 입력은 코드 안의 문자열이며, io.StringIO로 파일처럼 읽는다. 첫 줄은 행 수와 열 수, 이어지는 줄은 바닥, 다음 줄은 시작 행·열·방향, 마지막 줄은 명령열이다. 예시 데이터는 모든 행의 길이가 같고, 시작점이 빈 칸이며, 명령이 L·R·F 중 하나라는 조건을 만족한다.
import io
from itertools import product
DR = (-1, 0, 1, 0)
DC = (0, 1, 0, -1)
NAMES = ("북", "동", "남", "서")
EXAMPLE = """3 4
..#.
....
.#..
1 0 1
FFLFFRFF
"""
def read_example():
stream = io.StringIO(EXAMPLE)
height, width = map(int, stream.readline().split())
grid = [stream.readline().strip() for _ in range(height)]
row, col, direction = map(int, stream.readline().split())
commands = stream.readline().strip()
assert all(len(line) == width for line in grid)
assert 0 <= row < height and 0 <= col < width
assert grid[row][col] == "."
assert 0 <= direction < 4
assert all(command in "LRF" for command in commands)
return grid, (row, col, direction), commands
def step(grid, state, command):
row, col, direction = state
if command == "L":
return (row, col, (direction - 1) % 4), "회전"
if command == "R":
return (row, col, (direction + 1) % 4), "회전"
if command != "F":
raise ValueError("알 수 없는 명령")
next_row = row + DR[direction]
next_col = col + DC[direction]
height, width = len(grid), len(grid[0])
if not (0 <= next_row < height and 0 <= next_col < width):
return state, "경계"
if grid[next_row][next_col] == "#":
return state, "장애물"
return (next_row, next_col, direction), "이동"
def show(number, command, state, result):
row, col, direction = state
print(
f"{number}: {command} 위치=({row}, {col}) "
f"방향={NAMES[direction]} 결과={result}"
)
def run(grid, state, commands):
show(0, "-", state, "시작")
for number, command in enumerate(commands, start=1):
state, result = step(grid, state, command)
show(number, command, state, result)
return state
def reference_step(grid, state, command):
row, col, facing = state
left = {"북": "서", "서": "남", "남": "동", "동": "북"}
right = {"북": "동", "동": "남", "남": "서", "서": "북"}
if command == "L":
return row, col, left[facing]
if command == "R":
return row, col, right[facing]
if command != "F":
raise ValueError("알 수 없는 명령")
if facing == "북":
candidate = (row - 1, col)
elif facing == "동":
candidate = (row, col + 1)
elif facing == "남":
candidate = (row + 1, col)
else:
candidate = (row, col - 1)
free_cells = set()
for r, line in enumerate(grid):
for c, cell in enumerate(line):
if cell == ".":
free_cells.add((r, c))
if candidate in free_cells:
return candidate[0], candidate[1], facing
return state
def verify_small_cases():
checked = 0
for cells in product(".#", repeat=4):
grid = ["".join(cells[:2]), "".join(cells[2:])]
for row in range(2):
for col in range(2):
if grid[row][col] == "#":
continue
for direction in range(4):
for length in range(4):
for commands in product("LRF", repeat=length):
fast = (row, col, direction)
slow = (row, col, NAMES[direction])
assert fast == (
slow[0], slow[1], NAMES.index(slow[2])
)
for command in commands:
fast, _ = step(grid, fast, command)
slow = reference_step(grid, slow, command)
expected = (
slow[0], slow[1], NAMES.index(slow[2])
)
assert fast == expected, (
grid, row, col, direction, commands,
command, fast, slow
)
checked += 1
return checked
def main():
grid, state, commands = read_example()
run(grid, state, commands)
checked = verify_small_cases()
print(f"작은 입력 대조: {checked}개 통과")
if __name__ == "__main__":
main()줄별 해설
import io는 문자열을 입력 통로로 다루기 위해 사용한다. product는 지정한 원소를 반복해 만들 수 있는 순서쌍과 명령열을 차례로 제공한다. 예를 들어 product("LRF", repeat=2)는 LL, LR, LF 등 길이 2의 아홉 명령열에 해당하는 튜플을 만든다. 전체 결과를 리스트로 저장할 필요는 없다.
DR, DC, NAMES는 같은 방향 번호를 공유한다. 세 자료의 0번째 원소는 모두 북쪽에 관한 정보다. 괄호로 묶인 튜플을 사용한 이유는 실행 중 방향 규칙을 바꾸지 않기 때문이다. EXAMPLE에는 줄바꿈을 포함한 입력 전체를 넣는다.
read_example의 첫 줄은 문자열을 읽을 수 있는 통로를 만든다. readline은 한 줄을 읽고, split은 공백을 기준으로 값을 나눈다. 바닥 줄에서는 strip으로 줄바꿈을 제거한다. 이 문제의 바닥 기호는 점과 #뿐이므로 앞뒤 공백을 제거해도 칸 정보가 사라지지 않는다.
이어지는 assert는 예시 입력이 약속한 형태인지 확인한다. 조건이 거짓이면 검사를 중단하고 오류를 알린다. 시작 좌표의 범위를 먼저 확인하고 그다음 시작 칸을 읽는 순서에도 주목한다. 이 검사는 예시 개발을 돕는 장치이며, 입력 형식을 보장하는 코딩 테스트에서는 생략할 수 있다.
step의 첫 줄은 상태를 세 변수로 풀어 놓는다. 회전 명령은 새 방향을 계산해 즉시 반환한다. 반환값은 새 상태와 결과 문자열의 두 부분이다. F가 아닌 나머지 명령은 오류로 처리하므로 오타가 전진으로 해석되지 않는다.
next_row와 next_col은 아직 확정하지 않은 후보 좌표다. 경계 검사에서 실패하면 원래 state를 반환한다. 경계를 통과한 뒤에만 grid[next_row][next_col]을 읽는다. 장애물이 아니면 후보를 새 상태로 반환하며 방향은 유지한다.
show는 상태를 사람이 읽을 수 있는 한 줄로 바꾼다. 숫자 방향을 이름으로 바꾸는 일도 여기서 맡는다. run은 시작 상태를 먼저 출력하고, enumerate로 명령에 1부터 번호를 붙인다. 새 상태를 받은 다음 출력하므로 각 줄은 해당 명령을 처리한 뒤의 상태다.
reference_step은 비교 기준이 되는 느린 정답 함수다. 문자열 방향을 사용하고, 빈 칸 좌표를 매번 집합에 모은다. 격자 밖 좌표는 이 집합에 들어 있지 않으며 장애물 좌표도 들어 있지 않다. 따라서 후보가 집합에 있는지만 확인해 이동 허용 여부를 판단할 수 있다.
verify_small_cases는 바닥 배치부터 명령열까지 차례로 만든다. 장애물인 시작점은 continue로 건너뛴다. 각 사례마다 두 상태를 같은 출발점으로 초기화하고, 명령을 하나씩 양쪽에 적용한다. 비교 전에 문자열 방향을 번호로 바꾸어 표현 차이를 없앤다. 결과가 다르면 실패한 입력과 두 상태를 함께 보여 준다.
checked는 단계 수가 아니라 시작 조건과 명령열을 묶은 사례 수다. 네 칸 중 특정 칸을 빈 칸으로 고정하면 나머지 세 칸의 배치는 8개다. 가능한 빈 시작 칸과 배치의 조합은 4 × 8 = 32개이고, 방향은 4개다. 길이 0부터 3까지의 명령열 수는 1 + 3 + 9 + 27 = 40개이므로 총 32 × 4 × 40 = 5,120개를 검사한다.
main은 입력 준비, 예시 실행, 작은 입력 대조를 순서대로 연결한다. 마지막 조건문은 이 파일을 직접 실행할 때 main을 호출한다. 난수나 외부 파일을 사용하지 않으므로 같은 코드로 실행하면 출력 순서와 내용이 같다.
실행 결과
macOS와 Linux의 터미널에서 다음 명령으로 문법 컴파일을 확인한 뒤 실행할 수 있다. 첫 명령은 성공하면 출력 없이 끝난다. 두 번째 명령은 입력을 기다리지 않는다. Python의 최적화 옵션은 붙이지 않아야 assert 검사가 실행된다.
python3 -W error -m py_compile main.py
python3 main.py예상 출력은 다음과 같다.
0: - 위치=(1, 0) 방향=동 결과=시작
1: F 위치=(1, 1) 방향=동 결과=이동
2: F 위치=(1, 2) 방향=동 결과=이동
3: L 위치=(1, 2) 방향=북 결과=회전
4: F 위치=(1, 2) 방향=북 결과=장애물
5: F 위치=(1, 2) 방향=북 결과=장애물
6: R 위치=(1, 2) 방향=동 결과=회전
7: F 위치=(1, 3) 방향=동 결과=이동
8: F 위치=(1, 3) 방향=동 결과=경계
작은 입력 대조: 5120개 통과4단계와 5단계는 명령이 달라진 것이 아니라 같은 전진 명령이 연속해서 취소된 경우다. 취소도 하나의 명령 처리이므로 단계 번호는 증가한다. 마지막 줄이 나타나면 작은 입력 대조가 끝까지 진행되었다는 뜻이다. 이동 취소 이유 문자열은 손으로 만든 표와 예시 출력으로 확인하며, 전수 대조에서는 위치와 방향을 비교한다.
실무에서 자주 틀리는 것
칸을 읽은 뒤 경계를 검사한다
다음 코드는 칸을 먼저 읽는다. 후보가 범위를 벗어나면 예외가 나거나, 음수 인덱스 때문에 다른 칸을 읽을 수 있다.
if grid[next_row][next_col] == "." and (
0 <= next_row < height and 0 <= next_col < width
):
row, col = next_row, next_col범위를 먼저 검사하도록 고친다. and는 앞 조건이 거짓이면 뒤 조건을 평가하지 않는다. 아래 구조에서는 유효한 좌표에 대해서만 칸을 읽는다.
if 0 <= next_row < height and 0 <= next_col < width:
if grid[next_row][next_col] == ".":
row, col = next_row, next_col왼쪽 회전에서 방향 번호만 뺀다
방향 번호를 그대로 줄이면 북쪽에서 왼쪽 회전한 뒤 -1이 된다. 배열에서 -1이 마지막 원소를 가리켜 당장은 맞아 보일 수도 있지만, 상태의 방향 범위를 어긴다. 회전이 누적되면 다른 코드에서 문제가 드러난다.
direction = direction - 1회전 직후 번호를 정해진 범위로 돌려놓는다. 이후 함수는 방향이 0부터 3 사이라는 약속을 믿고 사용할 수 있다.
direction = (direction - 1) % 4한 좌표만 갱신하고 이동을 검사한다
현재 행을 먼저 바꾸면 검사에 실패했을 때 원래 상태를 복구해야 한다. 다음 코드에서는 이동이 거절되어도 행이 이미 바뀌어 있다.
row += DR[direction]
next_col = col + DC[direction]
if 0 <= row < height and 0 <= next_col < width:
if grid[row][next_col] == ".":
col = next_col두 후보 좌표를 별도로 계산하고, 모든 검사를 통과한 뒤 함께 반영한다. 상태 변경 지점이 한곳에 모이면 실패한 이동의 처리가 단순해진다.
next_row = row + DR[direction]
next_col = col + DC[direction]
if 0 <= next_row < height and 0 <= next_col < width:
if grid[next_row][next_col] == ".":
row, col = next_row, next_col이동 취소를 전체 실행 종료로 처리한다
전진이 취소되면 다음 명령을 처리해야 한다. 다음 코드는 취소를 만나자마자 반복을 끝내므로 뒤의 회전과 이동을 놓친다.
for command in commands:
state, result = step(grid, state, command)
if result in ("경계", "장애물"):
break취소된 명령도 처리된 명령이다. 상태를 그대로 받은 뒤 반복을 이어가면 된다. 완료 후 상태를 출력하는 순서도 유지한다.
for number, command in enumerate(commands, start=1):
state, result = step(grid, state, command)
show(number, command, state, result)한눈에 보기
| 관점 | 이 장의 선택 | 확인할 질문 |
|---|---|---|
| 상태 | 행, 열, 방향 | 다음 행동을 결정할 정보가 충분한가 |
| 방향 | 북·동·남·서 순서의 배열 | 이름과 두 변화량의 순서가 같은가 |
| 이동 | 후보 계산 후 검사 | 실패하면 이전 상태를 유지하는가 |
| 경계 | 칸을 읽기 전에 확인 | 행과 열의 하한·상한을 모두 검사하는가 |
| 검증 | 단계 기록과 작은 입력 대조 | 처음 달라지는 단계를 찾을 수 있는가 |
| 비용 | 이동 O(K), 바닥 O(HW) | 출력과 입력 저장 비용도 구분했는가 |
구현 전에 상태와 한 단계의 규칙을 문장으로 적는다. 그다음 손으로 만든 표를 코드의 출력과 비교한다. 작은 입력 전체를 별도 구현과 대조하면 특정 예시에 드러나지 않은 회전과 경계 조합도 확인할 수 있다. 다음 장에서는 모든 경우를 빠짐없이 만드는 방법 자체를 살펴본다.
연습 문제
- 회의실 표시등이 처음에는 꺼져 있다. 버튼 누름 횟수가 0부터 6까지인 각 경우에 대해 반복문으로 구한 상태와
count % 2 == 1의 결과를 비교하라. 두 결과가 같은 이유도 설명하라. - 로봇의 명령에 B를 추가하라. B는 바라보는 방향을 유지한 채 뒤로 한 칸 이동한다. 경계와 장애물 규칙은 F와 같다. 예시 시작 상태에서 BF를 처리한 뒤의 상태를 구하고, 한 단계 처리 함수의 변경 부분을 작성하라.
- 격자가
[".#", ".."]이고 시작 상태가(0, 0, 0)일 때, 명령 RFRFF를 처리한 뒤의 상태를 단계마다 적어라. 이동이 취소되는 이유도 구분하라. - 작은 입력 대조에서 허용하는 명령열 길이를 0부터 4까지로 늘리면 사례 수가 얼마인지 구하라. 길이가 하나 늘어났는데 검사량이 크게 늘어나는 이유를 설명하라.
정답과 해설
-
누름 횟수 0부터 6까지의 결과는 차례로 False, True, False, True, False, True, False다. 버튼을 두 번 누르면 원래 상태로 돌아오므로 홀수 번 눌렀을 때만 켜진다. 다음 코드는 일곱 입력을 모두 대조한다.
for count in range(7): is_on = False for _ in range(count): is_on = not is_on assert is_on == (count % 2 == 1) -
예시의 시작점은 행 1, 열 0이며 동쪽을 바라본다. B의 후보는 행 1, 열 -1이므로 경계에서 취소된다. 이어지는 F는 행 1, 열 1로 이동한다. 최종 상태는
(1, 1, 1)이다.step에서 회전 처리 다음의 명령 검사와 후보 계산을 아래처럼 바꾼다. 이후 경계·장애물 검사와 반환은 그대로 사용한다. 입력의 허용 문자도 LRF에서 LRFB로 바꾼다.if command not in ("F", "B"): raise ValueError("알 수 없는 명령") sign = 1 if command == "F" else -1 next_row = row + sign * DR[direction] next_col = col + sign * DC[direction]대조 검사에도 B를 넣으려면 정답 함수에 뒤로 이동하는 규칙을 별도로 추가하고, 명령열을 만드는 문자 목록도 바꿔야 한다. 검사할 입력만 늘리고 정답 함수를 그대로 두면 새로운 규칙을 검증할 수 없다.
-
첫 R 뒤에는
(0, 0, 1)이다. 다음 F는 행 0, 열 1의 장애물 때문에 취소되어 같은 상태를 유지한다. 다음 R 뒤에는(0, 0, 2)다. 다음 F로(1, 0, 2)가 된다. 마지막 F의 후보는 행 2, 열 0이므로 경계에서 취소된다. 최종 상태는(1, 0, 2)다. -
명령열 수는 1 + 3 + 9 + 27 + 81 = 121개다. 바닥과 빈 시작 칸의 조합 32개, 시작 방향 4개를 곱하면 32 × 4 × 121 = 15,488개다. 새로 추가된 길이 4의 명령열만 81개다. 각 위치에 명령 세 개 중 하나를 넣을 수 있으므로 길이가 늘어날 때마다 해당 길이의 명령열 수는 세 배가 된다. 작은 범위의 대조가 유용하더라도 범위를 크게 늘릴 때는 검사량을 다시 계산해야 한다.