[이것이 코딩 테스트다] 구현 - 게임 개발

YEAh·2021년 3월 5일

algorithm 구현 이것이 코딩 테스트다

이것이 코딩 테스트다

목록 보기

11/39

구현
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
완전 탐색 - 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

✅ 문제

장소는 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.

현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향을 회전만 수행하고 1단계로 돌아간다.
만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

0 : 북쪽
1 : 동쪽
2 : 남쪽
3 : 서쪽

0 : 육지 / 1 : 바다

입력 예시

4 4 # 4 x 4 맵 생성
1 1 0 # (1, 1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1 1 1 1 # 첫 줄은 모두 바다
1 0 0 1 # 둘째 줄은 바다/육지/육지/바다
1 1 0 1 # 셋째 줄은 바다/바다/육지/바다
1 1 1 1 # 넷째 줄은 모두 바다

출력 예시

💻 코드

N, M = map(int,input().split())

A, B, d = map(int, input().split())

input_map = []

# 맵 입력
for i in range(N):
    input_map.append(list(map(int,input().split())))

# 이동할 수 있는 모든 경우
move_steps = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# 바라보는 방향의 모든 경우
d_steps = [0, 1, 2, 3]

result = 0
# 캐릭터가 회전한 횟수
count = 0

# 현재 좌표 방문
input_map[A][B] = 2
result += 1

while True:
    d = d_steps[d-1]
    
    next_A = A + move_steps[d][0]
    next_B = B + move_steps[d][1]

    if input_map[next_A][next_B] == 0:
        A = next_A
        B = next_B
        input_map[A][B] = 2 
        result += 1
        count = 0
        #print("d = %d" %d + " - (A, B) = (%d, %d)" % (A, B))
    else :
    	count += 1
        #print("d =", d)
        # count = 4 일 때, 네 방향 모두 확인
        if count == 4: 
            next_A = A + move_steps[d-2][0]
            next_B = B + move_steps[d-2][1]
            # 이미 가본 곳으로 이동
            if input_map[next_A][next_B] != 1:
                A = next_A
                B = next_B
                count = 0
            else:
                break

#print("A, B 위치 = (%d, %d)" % (A, B), end=', ')
#print("result", result, end=', ')
#print("map:", input_map)
print(result)

설계

머릿속에서 잘 해결되지 않아 입력 예시로 시뮬레이션을 해보았다.

0 갈 수 있음 / 1 바다 / 2 간곳
-----------------------------
4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1

d = 0 시작

d = 3
d = 2
d = 1 -> A = 1 B = 2

d = 0 
d = 3
d = 2 -> A = 2 B = 2

d = 1
d = 0
d = 3
d = 2
if != 1 한칸뒤로 else break
------------------------------
4 4
1 1 0
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

d = 0 시작

d = 3
d = 2 -> A = 2 B = 1

d = 1 -> A = 2 B = 2

d = 0 -> A = 1 B = 2
  
A= 2 B = 2 마무리

맵에 방문한 칸은 2로 둔 이유가 메뉴얼 3번에서 한 칸 뒤로 가는 행동은 뒤쪽이 방문한 칸인 경우에 발생한다. 바다인 칸과 구분하기 위해서 2로 설정하였다.

행동의 모든 경우를 리스트에 튜플 또는 숫자로 저장하였다.