[Python] 시뮬레이션 알고리즘 (Simulation Algorithm) - 게임 개발 (문제 예제)

시뮬레이션 알고리즘 (Simuliation Algorithm)은 말 그대로 어떤 문제에서 제시된 수행 조건들을 한 단계씩 순서대로 수행하도록 구현하는 알고리즘이다. 보통 캐릭터를 2차원 공간의 게임 맵안에서 이동시키는 구현에 많이 사용된다.

 

아래가 시뮬레이션 알고리즘의 예제이다.

게임 개발

• N * M 직사각형의 게임판 (3<=N, M <50)
• 게임 칸의 특성 : 육지(0), 바다(1)
• 캐릭터가 있는 위치(A, B) : A는 북쪽에서 남쪽으로의 거리, B는 서쪽에서 동쪽으로의 거리이다.
• 바라보고있는 방향(d) : 북쪽(0), 동쪽(1), 남쪽(2), 서쪽(3)

캐릭터 이동 방법

• 캐릭터의 위치에서 왼쪽 방향부터 순서대로 칸으로 이동하려고 한다. (상하좌우, 육지로만 이동 가능)
• 캐릭터의 왼쪽 방향에 아직 가보지 못한 칸은 왼쪽으로 방향을 회전하고, 1칸 전진한다. 만약, 가본 칸이라면 방향만 한번 더 회전한 후, 다시 왼쪽 방향부터 탐색한다.
• 만약 모든 방향이 가본 칸이거나 바다인 칸이라면, 바라보고있는 방향 그대로 뒤로 1칸 후진한다. 만약, 후진도 불가능한 칸이라면 이동을 멈추고, 종료한다.

# 입력 예시
4 4        # N, M
1 1 0      # A, B, d
1 1 1 1    # 게임판 입력
1 0 0 1
1 1 0 1
1 1 1 1

입력된 데이터를 바탕으로 시뮬레이션 알고리즘을 구현하여 아래와 같이 캐릭터가 방문한 칸의 수를 출력해주는 문제이다.

# 출력 예시
3

나의 풀이

N, M = list(map(int, input().split(" ")))
A, B, d = list(map(int, input().split(" ")))
game_map = []
for i in range(0, N):
    game_map.append(list(map(int, input().split(" "))))

count = 1
rotation = 0
da = [1, 0, -1, 0]
db = [0, 1, 0, -1]

while True:
    if rotation==4:
        next_a = A + da[(d+2)%4]
        next_b = B + db[(d+2)%4]
        if game_map[next_a][next_b] == 1:
            break
        A = next_a
        B = next_b
        rotation = 0
        count+=1
        continue

    game_map[A][B] = 1
    rotation+=1
    next_d = (d+3)%4
    next_a = A + da[next_d]
    next_b = B + db[next_d]
    if game_map[next_a][next_b] == 0:
        A, B, d = next_a, next_b, next_d
        rotation = 0
        count += 1
        continue
    d = next_d

print(count)

시뮬레이션 알고리즘 문제를 쉽고, 빠르게 코드로 옮기기 위해서는 문제에 제시된 조건을 정확히 잘 이해하고, 단순화시키는 것이 가장 중요할 것 같다. 

 

출처

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2021)