[구현(implement)>시뮬레이션(simulation)] '게임 개발' 문제

참고

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791162243077 

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

클릭하시면 위 이미지에 보이는 링크로 이동합니다.

1.목적

코딩 테스트 알고리즘 '구현' 중 게임 개발 문제에 대해서 상세하게 이해하기 위해 해당 글을 작성하였다.

 

 

2.개요

구현이란 한 마디로 '머릿 속에 있는 알고리즘을 코드로 구현하는 과정'

그 과정에서 우리는 *문제를 읽는다. --> 생각을 한다. --> 문제를 해결한다 * 3가지 단계를 거쳐야 비로소 가능하다.

참조하는 서적에서는 구현의 종류는 2가지로 정의한다.

1. '완전 탐색' : 모든 경우의 수를 주저 없이 다 계산하는 방법
2. '시뮬레이션' : 문제에서 요구하는 알고리즘을 한단계씩 나눠서 직접 코드로 짜서 수행
   
   

그 중 구현 시뮬레이션의 문제 방식인 '게임 개발' 문제를 살펴 볼 것이다.

 

 

3.문제

현민이는 게임 캐릭터가 맵 안에 움직이는 시스템을 개발 중이다.

1. 캐릭터가 있는 장소는 1 * 1 크기의 정사각형으로 이뤄진 n * m 크기의 직사각형이다.
2. 각각의 칸은 육지(0) 또는 바다(1)이다.
3. 캐릭터는 동서남북 중 한 곳을 바라본다.
4. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수,
   B는 서쪽으로부터 떨어진 칸의 개수이다.
5. 캐릭터는 상하좌우로 움직일 수 있고 바다로 되어 있는 공간에는 갈 수 없다.
6. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 다음과 같다.
   6-1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터
   차례대로 갈 곳을 정한다.
   6-2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면 왼쪽 방향으로 횐전한 다음
   왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행
   하고 1단계로 돌아간다.
   6-3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는 바라보는 방향을
   유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이 때 뒤쪽 방향이 바다인 칸이라
   뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

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

'''

입력 조건

1. 첫 째줄에 n * m 형태의 맵을 공백으로 구분해서 입력한다.
2. 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 a, b와 바라보는 방향 d가 각각 서로 공백으로 구분해서 주어진다.
   북 : 0, 동 : 1, 남 : 2, 서 : 3
3. 셋째 줄부터 맵이 육지(0)인지 바다(1)인지에 대한 정보가 주어진다. 첫 줄에 입력한 행의 길이 만큼 입력한다.

 

4.답안

요구사항이 정말 많은 문제이기 때문에 꼼꼼이 본 뒤 요구사항에 맞게 하나하나 코드로 구현해야 한다. 또한 방향에 관한 문제가 나온다면 방향 관련한 별도의 리스트를 만들어 본래의 2차원 리스트의 구조를 바꾸는 것이 효과적이다. 조건이 많으므로 devide and conquer 방식으로 해당 문제를 풀어보겠다.

 

 

4-1. 첫 번째 입력인 전체 맵의 크기 입력 코드를 생성한다.

# row, column을 공백으로 구분해서 입력을 받는다. (맵의 크기 : row * column)
row, column = map(int, input().split())

첫 번째 입력 조건에 맞는 코드를 작성한 부분이다. 해당 부분을 예로 들어보자. 만약 3 3 을 입력했다면 3 * 3의 맵을 생성 할 수 있는 조건이 부여된다.

 

 

4.2 두 번째 입력인 캐릭터의 x, y, 바라보는 방향 입력 코드를 생성한다. 그리고 방문한 위치를 저장하기 위한 맵을 생성한다.

# 현재 캐릭터의 x좌표, y좌표, 바라보는 방향을 입력받는다. 
x, y, direction = map(int, input().split())
# 방문한 위치를 저장하기 위한 맵을 생성한다. 
visited_location = [[0] * column for _ in range(row)]

# 좌표를 입력했다면 이 캐릭터는 현재 x, y 좌표에 있다는 뜻이다. 고로 해당 방문 지역을 1로 만들어야 됨 
visited_location[x][y] = 1

여기서 핵심은 전체 맵과 방문한 위치를 저장하기 위한 맵을 따로 둔다는 것이다. 그림으로 그리자면 다음과 같은 형태가 나올 것이다.

만약 x y를 1 1로 두었다면 우측에 있는 방문위치 중 가운데의 0이 1로 바뀔 것이다. 왜?

# 좌표를 입력했다면 이 캐릭터는 현재 x, y 좌표에 있다는 뜻이다. 고로 해당 방문 지역을 1로 만들어야 됨 
visited_location[x][y] = 1

해당 구문에 의해 초기 캐릭터 위치의 좌표가 방문한 것으로 처리되어 0에서 1로 만들어진다.

 

 

4.3 맵의 각 좌표에 대한 육지, 바다 여부를 입력 코드를 생성한다.

# 전체 맵 정보를 입력받는 코드를 생성합니다. 
map_lst = [list(map(int, input().split())) for _ in range(row)]

만약 세 번째 입력 값을

1 1 1

1 0 1

1 1 1

로 했다면 다음과 같은 그림이 도출 될 것이다.

 

 

4.4 입력 조건 2에 따른 이동 할 방향을 정의한다.

일반적으로 2차원 리스트를 통해 맵을 만들어 알고리즘을 푸는 문제 같은 경우에 이동 할 방향을 리스트로 정의하여 만들어주면 쉽게 풀 수 있다.

# 북, 동, 남, 서를 리스트 형태로 정의합니다. 이 형태는 입력 조건 2에 기반하여 작성하였습니다.
move_x = [-1, 0, 1, 0] # move_x는 방문 위치 맵에 대해 위 아래로 가는 변수입니다. 
move_y = [0, 1, 0, -1] # move_y는 방문 위치 맵에 대해 우측, 좌측으로 가는 변수입니다.

기존에 있는 초기 좌표를 move_x나 move_y를 통해 새로운 좌표로 업그레이드 할 수 있다.

 

 

4.5 문제 6-1 조건에 기반하여 함수를 정의한다.

# 우선적으로 왼쪽으로 회전한다는 조건이 제시되어 있다. 이 조건을 만족시키기 위해 함수 하나를 구현한다. 
def turn_left() :
    global direction # 함수 내에서 전역변수를 사용하려면 global 키워드를 사용해야 된다.
    direction -= 1 
    if direction == -1 :  
        direction = 3 

해당 코드는 좌측을 우선적으로, 반시계 방향 회전하는 코드이므로 다음과 같이

move_x = [-1, 0, 1, 0] # move_x는 방문 위치 맵에 대해 위 아래로 가는 변수입니다. 
move_y = [0, 1, 0, -1] # move_y는 방문 위치 맵에 대해 우측, 좌측으로 가는 변수입니다.

이 코드가 깔려있기 때문에 구현 가능한 함수이다. 추후 move_x[direction]이나 move_y[direction]으로 업데이트 좌표를 구현할 것이다.

 

4.6 문제 6번 조건에 대해서 시뮬레이션을 수행하는 코드 작성

4.6.1 캐릭터가 어떤 지점에 있을 때 왼쪽으로 회전하는 코드 구현

count = 1 # 캐릭터가 방문한 칸의 수
location_turn_count = 0 # 캐릭터가 그 지점에서 회전한 수를 초기화 및 0 대입 
while True : 
    # 왼쪽으로 우선 회전하는 turn_left() 함수 사용, 이후 해당 좌표를 바라보며 다음 지점으로 갈 수 있        는 기회가 있는new_x, new_y 선언 및 대입
    turn_left()
    new_x = x + move_x[direction]
    new_y = y + move_y[direction]

    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동한다. 
    if visited_location[new_x][new_y] == 0 and map_lst[new_x][new_y] == 0 : 
        visited_location[new_x][new_y] = 1
        x = new_x 
        y = new_y
        count += 1
        turn_time = 0
        continue

해당 코드는 일단 캐릭터가 입력한 방향을 기준으로 좌측으로 돌고 정면을 바라 봤을 때의 다음 좌표가 가보지 않은 곳(0)이고 땅(0)이라면 가게 만드는 것을 구현한 코드이다.
그림을 통해 설명하면 쉽게 이해 될 것이다.

입력 값이 다음과 같이 입력됐을 때 왼쪽의 맵은 다음과 같은 구조가 나올 것이며, 우측에 있는 방문한 위치를 나타내는 맵은 다음과 같이 나올 것이다. 여기서 만약에 1,1을 기점으로 캐릭터가 초기 위치로 작용되고, 북쪽(0)을 바라본 상태에서 좌측으로 틀고 해당 좌표를 바라보는 지점은 (1, 0) 일 것이다.

while True : 
    # 왼쪽으로 우선 회전하는 turn_left() 함수 사용, 이후 해당 좌표를 바라보며 다음 지점으로 갈 수 있        는 기회가 있는new_x, new_y 선언 및 대입
    turn_left()
    new_x = x + visited_location[direction]
    new_y = y + visited_location[direction]

이후 회전하여 바라보는 좌표 (1,0)이 가보지 않은 칸(0)이고 땅 지역이라면(map_lst의 (1,0)이 0이라면) 그 지점으로 가는 코드를 구현한 것이다.

    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동한다. 
    if visited_location[new_x][new_y] == 0 and map_lst[new_x][new_y] == 0 : 
        visited_location[new_x][new_y] = 1
        x = new_x 
        y = new_y
        count += 1
        turn_time = 0
        continue

만약 위의 이미지에서 (1,0) 인 좌표가 땅(0)이었다면 성립하여 캐릭터가 이동을 했겠지만 그게 아니기 때문에 이동할 수 없다. 따라서 다음에서 나오는 4.6.2 코드 구문이 실행 될 것이다.

 

 

4.6.2 회전한 이후에 정면에 가보지 않은 땅이 없거나 바다일 때

    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우 다음과 같이 정의한다.
    else : 
        location_turn_count += 1

해당 구문은 좌측으로 회전한 뒤 바라보는 좌표의 상태가 바다 또는 가본 곳이라고 가정했을 때 실행되는 구문이다. 즉 갈 수 없으니까 왼쪽으로 회전한 수를 1 증가시킨다.

 

 

4.6.3 문제 조건 6-3에 대한 코드를 구현한다.

    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동한다.
    if visited_location[new_x][new_y] == 0 and map_lst[new_x][new_y] == 0:
        visited_location[new_x][new_y] = 1
        x = new_x
        y = new_y
        count += 1
        location_turn_count = 0
        continue
    else:
        location_turn_count += 1

    # 네 방향으로 모두 갈 수 없을 경우
    if location_turn_count == 4:
        new_x = x - move_x[direction]
        new_y = y - move_y[direction]
        # 뒤로 갈 수 없다면 이동을 한다.
        if map_lst[new_x][new_y] == 0:
            x = new_x
            y = new_y
        # 뒤가 바다로 막혀있는 경우?!
        else:
            break
        location_turn_count = 0

print(count)

 

코드 정리

# row, column을 공백으로 구분해서 입력을 받는다.
row, column = map(int, input().split())

# 현재 캐릭터의 x좌표, y좌표, 바라보는 방향을 입력받는다.
x, y, direction = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵을 생성한다.
visited_location = [[0] * column for _ in range(row)]
# print(visited_location)
# 좌표를 입력했다면 이 캐릭터는 현재 x, y 좌표에 있다는 뜻이다. 고로 해당 방문 지역을 1로 만들어야 됨
visited_location[x][y] = 1

# 전체 맵 정보를 입력받는 코드를 생성합니다.
map_lst = [list(map(int, input().split())) for _ in range(row)]

# 북, 동, 남, 서를 리스트 형태로 정의합니다. 이 형태는 입력 조건 2에 기반하여 작성하였습니다.
move_x = [-1, 0, 1, 0]  # move_x는 방문 위치 맵에 대해 위 아래로 가는 변수입니다.
move_y = [0, 1, 0, -1]  # move_y는 방문 위치 맵에 대해 우측, 좌측으로 가는 변수입니다.

# 우선적으로 왼쪽으로 회전한다는 조건이 제시되어 있다. 이 조건을 만족시키기 위해 함수 하나를 구현한다.


def turn_left():
    global direction  # 함수 내에서 전역변수를 사용하려면 global 키워드를 사용해야 된다.
    direction -= 1
    if direction == -1:
        direction = 3


count = 1  # 캐릭터가 방문한 칸의 수
location_turn_count = 0  # 캐릭터가 그 지점에서 회전한 수를 초기화 및 0 대입
while True:
    # 왼쪽으로 우선 회전하는 turn_left() 함수 사용, 이후 해당 좌표를 바라보며
    # 다음 지점으로 갈 수 있는 기회가 있는new_x, new_y 선언 및 대입
    turn_left()
    new_x = x + move_x[direction]
    new_y = y + move_y[direction]

    # 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동한다.
    if visited_location[new_x][new_y] == 0 and map_lst[new_x][new_y] == 0:
        visited_location[new_x][new_y] = 1
        x = new_x
        y = new_y
        count += 1
        location_turn_count = 0
        continue
    else:
        location_turn_count += 1

    # 네 방향으로 모두 갈 수 없을 경우
    if location_turn_count == 4:
        new_x = x - move_x[direction]
        new_y = y - move_y[direction]
        # 뒤로 갈 수 없다면 이동을 한다.
        if map_lst[new_x][new_y] == 0:
            x = new_x
            y = new_y
        # 뒤가 바다로 막혀있는 경우?!
        else:
            break
        location_turn_count = 0

print(count)

 

5.해당 문제를 분석 후 의문점 또는 깨달은 점

백준이나 프로그래머스 코드업 같은 저지 사이트에서 해당 문제에 대한 유사 문제를 지속적으로 해결해야 되겠다. 이 문제만으로는 유사 문제를 푸는데 어려움을 겪을 것이며, 꾸준한 반복 학습으로 적응해 나가야 될 것 같다.

또한 예시를 3 * 3 맵을 들어 설명이 부족한 감이 없지 않아 있었다. 다른 4 * 4 구조의 맵을 생성하여 추후 다시 한번 설명을 통해 문제에 패턴을 적응해 나가야 겠다.

마지막으로 문제 조건 6-3에 대한 시나리오 성립 사례가 딱히 머릿 속에 떠오르지 않는다. 해당 시나리오가 발동되는 과정이 어떤 것이 있을까? 최대한 머릿 속으로 생각 했지만 딱히 생각나지 않는다. 음...