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

@mildsalmon·2021-08-11 09:14

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. 테스트 케이스

입력 예시

출력 예시
```
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 중 어떤 것을 먼저 사용하는지 생각해야 한다.
상상만 하기보다는 연필로 써가면서, 그려가면서 상상을하자.
최대한 입력 값은 수정하지 않고 처리하자. 만약 수정해야 하는 경우가 발생하면 똑같은 것을 하나 만들어서 수정하자.