알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 4. 구현 - 게임 개발

  • 0
  • 0
0
0

1. 게임 개발

  • 난이도
  • 풀이 시간
    • 40분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128MB

A. 문제

  • 캐릭터가 있는 장소는 1x1 크기의 정사각형으로 이뤄진 NxM 크기의 직사각형이다.

    • N
      • 세로 크기
    • M
      • 가로 크기
  • 각각의 칸은 육지 또는 바다이다.

  • 맵의 각 칸은 (A, B)로 표현한다.

    • A는 북쪽으로부터 떨어진 칸의 개수 (row)
    • B는 서쪽으로부터 떨어진 칸의 개수 (column)
  • 캐릭터는 동서남북 중 한 곳을 바라본다.

  • 캐릭터는 상하좌우로 움직이며, 바다에는 갈 수 없다.

  • 캐릭터의 움직임

    • 현재 방향을 기준으로 왼쪽 방향(반시계 90º 회전)부터 갈 곳을 정한다.
      • 바라본 위치가 아직 가보지 못한 곳이라면 바라보는 방향으로 전진한다.
      • 바라본 방향에 가보지 못한 곳이 없다면 1단계로 돌아간다.
    • 만약 네 방향 모두 가본 칸이거나 바다로 되어 있는 칸이면, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다.
      • 뒤쪽 방향이 바다라면 움직임을 멈춘다.
  • 메뉴얼에 따라 캐릭터를 이동시킨 뒤에 캐릭터가 방문한 칸의 수를 출력하라.

b. 입력 조건
  • 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다
    • 3 <= N, M <= 50
  • 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 공백으로 구분하여 주어진다.
    • 방향 값은 다음과 같다.
      • 0
        • 북쪽
      • 1
        • 동쪽
      • 2
        • 남쪽
      • 3
        • 서쪽
  • 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다.
    • N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다.
    • 맵의 외곽은 항상 바다이다.
    • 맵 값은 다음과 같다
      • 0
        • 육지
      • 1
        • 바다
  • 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.
c. 출력 조건
  • 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.
d. 테스트 케이스
  • 입력 예시

    
    4 4
    1 1 0
    1 1 1 1
    1 0 0 1
    1 1 0 1
    1 1 1 1
    
    
  • 출력 예시

    
    3
    
    

B. 내 답안

a. 주먹구구식으로 품

n, m = list(map(int, input().split()))  
a, b, d = list(map(int, input().split()))  
  
game_maps = []  
  
direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]  
  
count = 1  
false_area = 0  
  
for i in range(m):  
  game_map = list(map(int, input().split()))  
  game_maps.append(game_map)  
  
while True:  
  
  d = (d-1) % len(direction)  
  
  da = a + direction[d][0]  
  db = b + direction[d][1]  
  
  print("="*20)  
  print(*game_maps,sep='\n')  
  print("현재 방향 : ", d)  
  print("내 위치 : ", a, b)  
  print("바라보는 위치 : ", da, db)  
  print("1 횟수 : ", false_area)  
  print("="*20)  
  
  if game_maps[da][db] == 0:  
    game_maps[a][b] = 2  
    a = da  
    b = db  
    count = count + 1  
    false_area = 0  
    print("움직여")  
  
  false_area = false_area + 1  
  
 if false_area == 4:  
    a = a + direction[(d-2)%4][0]  
    b = b + direction[(d-2)%4][1]  
    if(game_maps[a][b] == 1):  
      break  
  
  
  
print(count)

b. DFS 알고리즘 사용

# n, m = list(map(int, input().split()))  
# a, b, d = list(map(int, input().split()))  
n, m = 4, 4  
a, b, d = 1, 1, 0  
v = ["1 1 1 1",  
 "1 0 0 1",  
 "1 1 0 1",  
 "1 1 1 1"]  
  
game_map = []  
d_all = [(-1, 0), (0, 1), (1, 0), (0, -1)]  
count = 0  
  
for i in range(n):  
    game_map.append(list(map(int, v[i].split(" "))))  
  
def move(x, y, d, depth=0):  
    global count  
    print("x, y, d, count, depth", x, y, d, count, depth)  
    depth = depth + 1  
    if x >= 0 and x < n and y >= 0 and y < m:  
        if game_map[x][y] == 0:  
            game_map[x][y] = 1  
            print(*game_map, sep='\n')  
            count = count + 1  
            for j in d_all:  
                dx = x - d_all[d][0]  
                dy = y - d_all[d][1]  
  
                d = d + 1  
  
                if d % 4 == 0:  
                    d = d - 4  
  
                move(dx, dy, d, depth)  
            return count  
        else:  
            return False  
    else:  
        return False  
  
count = move(a,b, d)  
  
print(count)


c. BFS 알고리즘 사용

from collections import deque  
  
n, m = list(map(int, input().split()))  
A, B, d = list(map(int, input().split()))  
game_map = []  
check_map = [[0] * m for _ in range(n)]  
  
for i in range(n):  
    game_map.append(list(map(int, input().split())))  
  
ds = [(-1, 0),  
 (0, 1),  
 (1, 0),  
 (0, -1)]  
  
q = deque()  
q.append([A, B])  
count = 0  
  
while q:  
    x, y = q.popleft()  
    check_map[x][y] = 1  
    count += 1  
    sea_count = 0  
    for i in range(4):  
        d = (d - 1) % 4  
        dx = x + ds[d][0]  
        dy = y + ds[d][1]  
  
        if sea_count == 4:  
            x = x - ds[d][0]  
            y = y - ds[d][1]  
            if game_map[x][y] == 0:  
                q.append([x, y])  
                break  
  
        if dx < 0 or dx >= n or dy < 0 or dy >= m:  
            continue  
  
        if game_map[dx][dy] == 1 or check_map[dx][dy] == 1:  
            sea_count += 1  
            continue  
  
        q.append([dx, dy])  
        break  
  
    print(*check_map, sep='\n')  
    print()  
  
print(count)


DFS로는 못풀꺼 같다고 생각해서, BFS로 풀고 기록하려고 왔더니... 이미 DFS로 풀었었다. 난 오늘도 DFS를 오해했다. 잘 생각해보면 DFS가 BFS보다 더 효율적일텐데..

d. 회고

반성

  • 노트에 어떻게 구현할지 구상을 하고 코드로 구현하여 한 번에 성공했다.
    • 아이디어는 전부 맞았는데, x축과 y축이 헷갈려서 시간을 많이 잡아먹었다.
  • 너무 상상에 의존하여 문제 푸는 속도가 느렸다.
  • 책 답안에서는 빈 맵을 만들어서 방문한 위치를 표시했다.
    • 나는 입력받은 맵에 숫자 2로 표시했다.
      • 내가 한 방법은 원본을 다시 참고해서 방향을 바꿔야하는 경우 문제가 생길 수 있는 방법이다.

결론

  • 좌표평면 문제(시뮬레이션)가 나온다면 무조건 캐릭터가 움직이는 방향을 중요하게 봐야한다.
    • x, y로 생각하기보다는 row, column 으로 생각하는게 편하다.
    • 문제에서는 row와 column 중 어떤 것을 먼저 사용하는지 생각해야 한다.
  • 상상만 하기보다는 연필로 써가면서, 그려가면서 상상을하자.
  • 최대한 입력 값은 수정하지 않고 처리하자. 만약 수정해야 하는 경우가 발생하면 똑같은 것을 하나 만들어서 수정하자.

C. 문제 해설

전형적인 시뮬레이션 문제. 별도의 알고리즘이 필요하기보다는 문제에서 요구하는 내용을 오류 없이 성실하게 구현만 할 수 있다면 풀 수 있다.

방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다.

파이썬에서 2차원 리스트를 선언할 때는 컴프리헨션을 이용하는 것이 효율적이다.

a. 책 답안

python-for-coding-test/4.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.