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

- Author: @mildsalmon
- Published: 2021-08-11
- Updated: 2021-09-02
- Source: http://blex.me/@mildsalmon/chap-4-%EA%B5%AC%ED%98%84-%EA%B2%8C%EC%9E%84-%EA%B0%9C%EB%B0%9C
- Tags: 파이썬, 한빛미디어, 이것이취업을위한코딩테스트다, 나동빈, 코딩테스트, 문제, 풀이, 구현, dfs, 게임개발, bfs

---

# 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. 주먹구구식으로 품

```python

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 알고리즘 사용

```python

# 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 알고리즘 사용

```python

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)](https://github.com/ndb796/python-for-coding-test/blob/master/4/4.py)

# 참고문헌

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