[구현] 게임 개발 (실전문제, 이것이 코딩테스트다 with 파이썬)

구현

• 코딩테스트에서 자주 출제되는 유형
• (1) 정확한 풀이 방법, (2) 프로그래밍 언어 문법의 이해를 바탕으로 완벽한 구현
• 구현 : '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'
• 알고리즘 설계 후, 먼저 풀 문제가 없을 때 푸는 문제
• 피지컬을 요구하는 문제
• 언어의 문법(라이브러리)을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법
• 코테에서 1~2번 문제는 대부분 그리디 or 구현 → 합격을 좌우

구현하기 어려운 문제

• 코드가 지나칠 만큼 길어지는 문제
• 특정 소수점 자리까지 출력해야 하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등

유형

• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

문제

- (0, 0)으로부터 떨어진 위치 (A, B)

- 상하좌우 이동, 바다는 못 감

- 맵의 외곽은 항상 바다

- 게임 캐릭터가 위치한 칸의 상태는 항상 육지

 

1. 왼쪽부터!

2. 캐릭터의 바로 왼쪽 방향 안 가봤으면 -> 왼쪽 회전 후 직진

3. 네 방향 모두 가봤거나, 바다 -> 방향 유지하고 한 칸 뒤로

ㄴ반복

ㄴ뒤쪽도 바다면 스탑

 

입력

N M (맵의 세로 가로 크기)

A, B (캐릭터가 있는 칸 좌표) d (바라보는 방향)

N개 줄의 0, 1 (0 육지, 1 바다)

 

출력

마친 후 캐릭터가 방문한 칸의 수

 

풀이

# 변수 : N M 맵의 세로 가로 크기
# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 변수 : d 방문 위치 표시맵
# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]    # 리스트 컴프리헨션 문법으로 2차원 리스트 초기화

# 변수 : x y 현재 좌표, direction 바라보는 방향 (0 북 1 동 2 남 3 서)
# 현재 캐릭터의 X, Y 좌표, 방향을 입력받기
x, y, dirextion = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리

# 변수 : N개 줄의 0, 1
array = []
for i in range(n):
    array.append(list(map(int, input().split())))
    
# 북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 회전
def turn_left():
    global direction     # direction 변수가 함수 바깥에서 선언된 전역변수라서
    direction -= 1       # 왼쪽으로 회전
    if direction == -1:  # 북쪽에서 회전하면 서쪽 : -1 → 3
        direction = 3

# 시뮬레이션 시작
count = 1    # 첫
trun_time = 0
while True:
    # 왼쪽으로 회전
    turn_left()
    nx = x + dx(direction]
    ny = y + dy[direction]
    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[nx][ny] == 0 and array[nx][ny] == 0:    # d 방문위치, array 바다위치
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
        turn_time += 1    # 한번 더 회전
    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4:    # 3의 경우 : 바라보는 방향 유지, 한 칸 뒤로
        nx = x - dx[direction]
        ny = y - dy[direction]
        # 뒤로 갈 수 있다면 이동하기
        if array[nx][ny] == 0:
            x = nx
            y = ny
        # 뒤가 바다로 막혀있는 경우
        else:
            break    # 빠져나감
        turn_time = 0     # 다시 1의 경우로 돌아감
    
# 정답 출력
print(count)

 

해석

시뮬레이션 유형 : 문제에서 요구하는 내용을 오류 없이 성실하게 구현하면 풀 수 있음. 단, 소스코드로 옮기는 과정이 간단하지 않으므로 반복적인 숙달 필요

 

변수 : N M 맵의 세로 가로 크기, d 방문 위치 표시맵, x y 현재 좌표, direction 바라보는 방향 (0 북 1 동 2 남 3 서)

 

1. 맵의 크기(N, M) 입력받기

2. 방문위치 맵(d) 생성 및 초기화

3. 현재 좌표(x, y)와 방향(direction) 입력받기

4. 현재 좌표(d[x][y]) 방문 처리 : 1

5. 전체 맵_바다(array) 입력받기

6. 북, 동, 남, 서 방향(dx, dy) 정의

7. 회전 함수 정의 : (0 북 1 동 2 남 3 서), direction -= 1

-----시뮬레이션-----

8. 횟수 +1 : 현재 위치 방문

9. 왼쪽으로 회전, 직진 : turn_time += 1

ㄴ 가보지 않은 칸 and 육지 >> 이동, 횟수 +1

ㄴ 가본 칸 or 바다 >> 회전

     ㄴ네번 회전 점검했음에도 이동 불가 : turn_time == 4 >> 뒤로 이동

          ㄴ뒤가 바다 >> 게임 끝

10. 8로 돌아가 처음부터 다시 회전 : trun_time = 0

-----게임 끝-----

11. 횟수 출력

 

 

* 방향을 설정해서 이동하는 문제 유형

일반적으로 dx, dy라는 별도의 리스트 만들어 방향 정하는 것이 효과적

ex) 북쪽 이동 → x와 y좌표를 dx[0], dy[0] 더하기 = (-1, 0)만큼 이동

 

* 리스트 컴프리헨션 문법

대괄호[ ] 안에 조건문과 반복문을 넣는 방식으로 리스트 초기화

ex)

# 0부터 19까지의 수 중에서 홀수만 포함하는 리스트
array = [i for i in range(20) if i % 2 == 1]
print(array)
# [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]


# 1부터 9까지의 수의 제곱 값을 포함하는 리스트
array = [i * i for i in range(1, 10)]
print(array)
# [1, 4, 9, 16, 25, 36, 49, 64, 81]

 

특히, 코테에서 2차원 리스트 초기화할 때 효과적

이 경우 무조건 리스트 컴프리헨션 사용해야 함.

그렇지 않으면 의도하지 않은 결과가 나올 수 있음

# N X M 크기의 2차원 리스트 초기화
n = 3
m = 4
array = [[0] * m for _ in range(n)]
print(array)
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]


# 틀린! N X M 크기의 2차원 리스트 초기화
n = 3
m = 4
array = [[0] * m] * n
print(array)
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

array[1][1] = 5
print(array)
# [[0, 5, 0, 0], [0, 5, 0, 0], [0, 5, 0, 0]]

 

* global 키워드

정수형 변수 direction 이 함수 바깥에서 선언된 전역변수이기 때문

 

* 예외처리

3 3

1 1 0

1 1 1

1 0 0

1 1 0

이 경우 맵 외곽은 바다로 구성된다는 설정이 고려되지 않아 에러발생.

→ 실무 코딩은 예외 고려해서 코드 짜야 함. 코테는 입력값 대체로 주어지므로 예외처리하지 않고 빠르게 코드 작성.

=> 차이점을 알아 두자!