[이코테] 게임 개발

문제 풀면서 작성한 메모

풀이 과정

---

자그마치 2시간이 넘게 걸린 풀이~^^ 하.. 알고리즘 진짜 만만하게 봤는데 요즘 한없이 작아지는 중이다... 계속하다 보면 늘겠지~ 하하하 그래도 이전 문제 통해서 배운 거 이번엔 써먹었다..!

 

 

게임 개발 문제는 시간제한이 40분이었다. 지금까지 풀어본 연습문제 중 최대였다. N x M 직사각형이 있고 각 칸은 육지(0) 혹은 바다(1)이다. 단, 바다는 갈 수 없다. 게임 캐릭터가 있는 칸의 좌표는 (A, B)이고 A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 말을 좀 어렵게 해 놨는데 N x M 직사각형을 행렬로 보고 A랑 B는 그냥 몇 행, 몇 열이라고 보면 된다. (1,1)이면 1행 1 열인 거다. 특이한 건 바라보는 방향 d까지 주어진다. d의 값도 동서남북이 아니라 북동남서 순이라 조금 헷갈렸다.

 

 

캐릭터의 움직임을 설정하기 위해 정해놓은 매뉴얼이 나오는데, 여기서 시뮬레이션 알고리즘이라는 것을 눈치챘다. 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행해야 한다. 그래서 입력 예시를 직접 그려가며 이해했다.

 

처음에 '바로 왼쪽 칸'이 아닌 '현재 방향부터 왼쪽 방향까지 모든 칸'으로 잘못 해석해서 좀 헤맸다. 이래서 문제를 잘 읽는 것도 중요하다. 매뉴얼 1번이 말을 더 헷갈리게 만들어서 오히려 매뉴얼 1번이 없는 게 더 정확히 와닿았을 것 같다. 그리고 매뉴얼 2번에서 '바로 왼쪽 방향에'가 아니라 '바로 왼쪽 칸에'라고 해주면 더 좋았을 텐데.. 일부로 말장난한 건가? 마치 바로 왼쪽 칸은 가본 칸이거나 바다로 되어 있는 칸이더라도 왼쪽 방향의 모든 칸 중에 가보지 않은 칸이 있으면 갈 수 있는 것처럼 써놨는데 가본 칸이거나 바다로 되어 있는 칸 때문에 막혀서 갈 수가 없다. 결국 바로 왼쪽 칸을 말한다. 약간 이해력 문제인가 싶었다. 

 

변수명은 문제 거의 그대로 N은 n, M은 m, A는 a, B는 b, d는 d로 이름 지었다. 이외에 직사각형 게임 맵은 2차원 배열 gameMap으로, 출력해야 하는 캐릭터가 방문한 칸의 수는 cnt로 선언했다.

 

# 세로 크기 n, 가로 크기 m 저장

# 게임 캐릭터가 있는 칸의 좌표 (a,b)와 바라보는 방향 d 저장

# 캐릭터가 방문한 칸의 수 cnt 생성

# 육지인지 바다인지에 대한 정보 sea 저장
# 2차원 배열 gameMap 생성
# 한줄한줄 받아서 gameMap에 append

# 매뉴얼대로 움직이기
# 4번동안 반복
# 바로 왼쪽 방향에 0이 있으면 d 왼쪽으로 회전, 왼쪽 한칸 전진
# 바로 왼쪽 방향에 0이 없으면 d 왼쪽으로 회전

# 4번 반복 후에도 갈곳이 없다면 뒤로 한칸 후진
# 후진 할 수 있으면 1단계 다시 진행
# 후진 할 수 없으면 종료

# cnt 출력

 

문제를 토대로 의사 코드를 작성해보았다. 유독 이번 문제는 의사 코드 변동이 많았다. 코드를 작성하다 보니 또 필요한 게 생겨 고치고 추가하고를 자주 했다. 위의 의사 코드를 토대로 코드를 작성하면서 변경된 부분만 언급해보겠다.

 

1. 7번째 줄을 보면 육지인지 바다인지 sea 정보를 써놨다. 문제 읽을 때만 해도 칸에 대한 정보가 필요할 줄 알았는데 코드를 작성하다 보니 전혀 필요가 없었다. 삭제!

 

# 가본 칸은 바다로 변경, cnt 추가
gameMap[a][b] = 1
cnt += 1

 

2. 가본 칸이거나 바다로 되어 있는 칸은 갈 수 없기 때문에 캐릭터가 가본 칸을 기억해야 했다. 그래서 나는 가본 칸을 바다로 되어 있는 칸으로 처리했다. 문제에서는 이 두 경우를 나누고 있지만 결국 출력해야 하는 것은 방문한 칸의 수이므로 굳이 가본 칸이 어디인지 기억할 필요가 없다. 

 

# 동서남북 direction 생성
direction = [0, 1, 2, 3]

...

      # d 왼쪽으로 회전
      d = direction[direction.index(d) - 1]

 

3. 왼쪽으로 회전하기 위해 d를 바꿔줘야 했는데 여기서 문제가 생겼다. 예를 들어 북쪽에서 왼쪽으로 회전하면 서쪽인데 북쪽은 0이고 서쪽은 3이므로 -1을 한다고 3이 되지 않는다. 0, 1, 2, 3의 범위를 벗어날 수 있으므로 index로 접근해야 했다. direction = [0, 1, 2, 3]를 선언하고 왼쪽으로 회전하기 위해 d = direction[direction.index(d) - 1]를 해서 index를 움직여줬다.

 

 

# 움직일 수 있는 da, db 정의
da = [0, -1, 0, 1]
db = [-1, 0, 1, 0]

...

# 매뉴얼대로 움직이기
while True:
  # 4번동안 반복
  i = 0
  while i < 4:
    newA = a + da[d]
    newB = b + db[d]
    # 바로 왼쪽 방향에 0이 있으면
    if gameMap[newA][newB] == 0:
      # d 왼쪽으로 회전
      d = direction[direction.index(d) - 1]
      # 왼쪽 한칸 전진
      a, b = newA, newB
      # 가본 칸은 바다로 변경, cnt 추가
      gameMap[a][b] = 1
      cnt += 1
      i = 0
    # 바로 왼쪽 방향에 0이 없으면
    else:
      # d 왼쪽으로 회전
      d = direction[direction.index(d) - 1]
      i += 1

 

4. 대망의 dx, dy다. steps로 할까 했는데 어차피 a, b로 따로 취급하고 있어 da, db로 나누었다. direction과 da, db의 index를 맞추기 위해서 da와 db를 현재 방향이 d일 경우 왼쪽으로 회전하고 왼쪽으로 한 칸 전진할 경우로 선언했다. 예를 들어, 북쪽(d=0, direction[d])을 바라봤을 때 왼쪽으로 회전하고 왼쪽으로 한 칸 전진할 경우 a는 da[d]인 0만큼, b는 da[d]인 -1만큼 가야 하는 것이다.

 

전체 소스 코드는 다음과 같다.

 

# 세로 크기 n, 가로 크기 m 저장
n, m = map(int, input().split())

# 게임 캐릭터가 있는 칸의 좌표 (a,b)와 바라보는 방향 d 저장
a, b, d = map(int, input().split())

# 캐릭터가 방문한 칸의 수 cnt 생성
cnt = 0

# 2차원 배열 gameMap 생성
gameMap = []
# 한줄한줄 받아서 gameMap에 append
while True:
  line = input()
  if not line:
    break
  line = list(map(int, line.split()))
  gameMap.append(line)

# 동서남북 direction 생성
direction = [0, 1, 2, 3]

# 움직일 수 있는 da, db 정의
da = [0, -1, 0, 1]
db = [-1, 0, 1, 0]

# 가본 칸은 바다로 변경, cnt 추가
gameMap[a][b] = 1
cnt += 1

# 매뉴얼대로 움직이기
while True:
  # 4번동안 반복
  i = 0
  while i < 4:
    newA = a + da[d]
    newB = b + db[d]
    # 바로 왼쪽 방향에 0이 있으면
    if gameMap[newA][newB] == 0:
      # d 왼쪽으로 회전
      d = direction[direction.index(d) - 1]
      # 왼쪽 한칸 전진
      a, b = newA, newB
      # 가본 칸은 바다로 변경, cnt 추가
      gameMap[a][b] = 1
      cnt += 1
      i = 0
    # 바로 왼쪽 방향에 0이 없으면
    else:
      # d 왼쪽으로 회전
      d = direction[direction.index(d) - 1]
      i += 1

  # 4번 반복 후에도 갈곳이 없다면 뒤로 한칸 후진
  newA = a - db[d]
  newB = b - da[d]
  # 후진 할 수 있으면
  if gameMap[newA][newB] == 0:
    # 1단계 다시 진행
    a, b = newA, newB
    # 가본 칸은 바다로 변경, cnt 추가
    gameMap[a][b] = 1
    cnt += 1
  # 후진 할 수 없으면 while문 빠져나오기
  else:
    break

# cnt 출력
print(cnt)

답안 예시

---

4-4.py 답안 예시

# N, M을 공백을 기준으로 구분하여 입력받기
n, m = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
x, y, direction = map(int, input().split())
d[x][y] = 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 -= 1
    if direction == -1:
        direction = 3

# 시뮬레이션 시작
count = 1
turn_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[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
        turn_time += 1
    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        # 뒤로 갈 수 있다면 이동하기
        if array[nx][ny] == 0:
            x = nx
            y = ny
        # 뒤가 바다로 막혀있는 경우
        else:
            break
        turn_time = 0

# 정답 출력
print(count)

 

큰 틀은 비슷하게 맞추긴 했다. 내 코드와 다른 점을 짚어보자면,

 

1. 4번째 줄에서 방문한 위치를 저장하기 위한 맵을 따로 생성해 주었는데, 그럴 필요 없이 방문한 위치 또한 바다로 처리해주는 게 더 편한 것 같다. 어차피 방문한 칸이나 바다로 된 칸이나 둘 다 못 가는 칸이니까?

 

2. 10번째 줄에서 맵 정보를 입력받을 때 나는 while True하고 if not line: break 했는데 생각해보니 몇 개 들어오는지 알고 있는 상황이라 여기 나온 예시처럼 for i in range(n)이 더 적합했다.

 

3. 15~17번째 줄을 보면 나와 다르게 dx, dy를 선언했다. 나는 북쪽(0)을 바라보고 있을 경우 왼쪽으로 회전하고 왼쪽으로 한 칸 전진할 경우를 da[0]와 db[0]에 담았는데, 여기서는 북쪽(0)을 바라보고 있으면 북쪽으로 이동하는 경우를 dx[0], dy[0]에 담았다. 이게 더 직관적이었다. 이렇게 선언했기 때문에 왼쪽으로 회전하는 코드가 먼저 나온 것이다. 그러게. 어차피 가보지 않은 칸이 존재하든 존재하지 않든 왼쪽으로 회전은 둘 다 해줘야 한다. 문제를 기계적으로 읽지 말고 생각을 좀 더 해서 코드를 줄일 수 있으면 줄이자!

 

4. 19번째 줄에서 왼쪽으로 회전하는 코드를 따로 선언하는 것도 괜찮지만 global까지 쓰면 복잡해서 차라리 방향 d의 값을 모두 담은 배열을 따로 선언해서 인덱스로 접근하는 게 더 나을 것 같다. 그렇지만 예시 코드가 더 떠올리기 쉽고 직관적이긴 하다.

 

5. 29번째 줄부터 보면 while문이 크게 하나고, 그 안에서 if문 두 번으로 매뉴얼을 처리해주고 있다. 나는 while문 안에 while문과 if문으로 처리했는데 작은 while문은 사실상 필요가 없었다. 예시 코드처럼 작성하면 중복되는 코드를 좀 더 줄일 수 있다.

 

6. 이건 의문인 점인데, 49번째 줄에서 뒤로 갈 수 있다면 이동했을 때는 왜 count 안 해주는 거지? 이것도 가본 칸으로 count 해줘야 하는데.. issue탭에 질문을 남겨놨으니 답변이 오면 공유하도록 하겠다.

 

음.. 그런데 결론적으로 코드는 직관적으로 작성하는 것이 편한 것 같다. 그다음 단계를 나가는 데 있어서도 앞 단계가 직관적이지 못하면 꼬이는 듯하다. 빠르게 풀어야 하는데 너무 많은 설명이 필요한 코드는 좋지 않다. 누가 봐도 납득가게 직관적으로 코드를 작성해보자!

개념 정리

---

구현

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

 

취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제된다. 구현 유형은 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제다. 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다. 구현 유형의 문제는 문제의 길이가 꽤 긴 편이지만 고차원적 사고력을 요구하는 문제는 나오지 않는 편이라 오히려 쉽게 풀 수 있다.

 

혹시 코팅 테스트 환경에서 파이썬3 뿐만 아니라 Pypy3도 지원한다면 Pypy3의 실행 속도가 때로는 C/C++과 견줄 만큼 빠르므로 Pypy3을 이용하도록 하자. 특히 반복문이 많을수록 Pypy3와 파이썬3의 속도가 차이가 난다.

 

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다루고 있다.

완전 탐색

모든 경우의 수를 주저 없이 다 계산하는 해결 방법

시뮬레이션

문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

코드

---

GitHub - leeejihyun/algorithm: 알고리즘 문제 풀이

출처

---

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2021), p118-121