[Algorithm] 예제) 구현 - 게임 개발

이것이 코딩 테스트다 - 구현 - 실전문제 : 게임 개발

🔍 나의 답안

# 게임 개발 - 내 답

#input
n, m = map(int, input().split()) #맵의 크기 : 세로n, 가로m
y, x, direction = map(int, input().split()) #현재 나의 위치
maps = []
cnt = 1 #방문한 칸의 수 / 처음에 위치한 곳은 항상 육지이므로 초기값은 1
for i in range(n):
    maps.append(list(map(int, input().split())))

#기본 정보
directions = [0, 1, 2, 3] #북동남서
moves = [(0,-1), (1,0), (0,1), (-1,0)] #북동남서로 앞으로 한칸 움직일때의 변화되는 좌표값
back_moves = [(0,1), (-1,0), (0,-1), (1,0)] #북동남서로 뒤로 한칸 움직일때 변화되는 좌표값

maps[y][x] = 2 #첫시작위치를 이미 간 곳이라고 표시


while True:

    did_move = 0 #네 방향 중 한곳으로라도 이동했는가? 0:이동안함, 1:이동함
    t_direction = direction 

    for i in range(4): #네 방향을 모두 둘러봄.
        t_direction = directions[t_direction-1] #현재에서 왼쪽돌았을때의 방향을 임시변수에 저장
        tx = x + moves[t_direction][0] #왼쪽으로 한칸 이동했을 때의 위치
        ty = y + moves[t_direction][1] #왼쪽으로 한칸 이동했을 때의 위치
        
        if maps[ty][tx] == 0: #왼쪽방향으로 회전하고 왼쪽으로 한 칸 전진했을 때가 -> 아직 가보지않았고, 육지라면 전진
            direction = t_direction
            cnt += 1 #방문한 칸의 수 1 가
            did_move = 1 #이동했다는 증거.
            x = tx
            y = ty
            maps[y][x] = 2 #이동한 위치를 이미 간 곳이라고 표시.

            break #이동했으면 더이상 둘러볼 필요없으므로 빠져나감.


    #네 방향 모두 이미 가본 칸이거나 바다로 되어있는 경우 == 위의 for문에서 아무런 변화없는 경우
        #if 뒤쪽이동했을때가 바다인 경우: 위치 그대로 움직이지 않음.while문 탈출.
        #else: 한칸뒤로 이동

    if did_move == 0: #네 방향 아무곳도 이동하지 않음.
        tx = x + back_moves[direction][0]
        ty = y + back_moves[direction][1]

        if maps[ty][tx] == 1: #뒤쪽이동햇을때가 바다인 경우 -> 움직임을 멈춤.while문 탈출
            break
        else: #그냥 네 방향모두 가본 칸인 경우
            x = tx
            y = ty
    
    
print(cnt)

🔍 책의 답안 예시

# 게임 개발 - 책 답안 예시


n, m = map(int, input().split())

#방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
#현재 위치 입력받기
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)

코드 비교 : 4가지 방향 차례대로 갈 곳을 정하는 알고리즘

• 내 답 : for문으로 4가지 방향 탐색, 앞으로 이동가능하면 for문 탈출.
• 예시 답 : 회전할때마다 횟수 +1하고 회전횟수가 4가되면 이동불가능하다고 판단.

💫 느낀점 및 배운점

🔒 문제풀이를 위한 테크닉
일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다.

#예시
moves = [(0,-1), (1,0), (0,1), (-1,0)]

• 맵의 좌표 - 2차원배열로 받아오기

array = []
for i in range(n):
    array.append(list(map(int, input().split())))

• 2차원배열 초기화하기

d = [[0] * m for _ in range(n)]

틀렸던/수정한 코드

• x,y 입력받을 때 틀림.
  문제에서는 A,B를 입력받는데 A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수라 했으므로 A는 행, B는 열. 문제를 잘 읽자!

• maps[y][x] = 2
  이동한 위치를 이미 간 곳이라고 표시해야 함. 수정 전에는 이동하기 전 위치를 이미 간 곳이라고 표시해놔서 마지막 방문한 곳이 방문하지 않은 곳으로 처리되어있었음. 첫 시작위치를 이미 방문했다고 표시해두어야 함.

• t_direction = directions[t_direction-1] #현재에서 왼쪽돌았을때의 방향을 임시변수에 저장