구현 실전 문제
게임 개발
🐾 문제 설명
현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.
1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.
단, 방향 d는 0 : 북쪽, 1: 동쪽, 2 : 남쪽, 3 : 서쪽으로 입력받는다.
🐾 입출력 예시
- 입력
4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1
- 출력
3
🐾 내 풀이
재귀를 이용한 풀이
def nextStep(gameMap, mapFlag, r, c, d, cnt):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
if gameMap[r + dx[d]][c + dy[d]] == 0 and mapFlag[r + dx[d]][c + dy[d]] == 0:
cnt += 1
mapFlag[r + dx[d]][c + dy[d]] = 1
return(nextStep(gameMap, mapFlag, r + dx[d], c + dy[d], d, cnt))
elif gameMap[r + dx[(d + 3) % 4]][c + dy[(d + 3) % 4]] == 0 and mapFlag[r + dx[(d + 3) % 4]][c + dy[(d + 3) % 4]] == 0:
cnt += 1
mapFlag[r + dx[(d + 3) % 4]][c + dy[(d + 3) % 4]] = 1
return(nextStep(gameMap, mapFlag, r + dx[(d + 3) % 4], c + dy[(d + 3) % 4], (d + 3) % 4, cnt))
elif gameMap[r + dx[(d + 2) % 4]][c + dy[(d + 2) % 4]] == 0 and mapFlag[r + dx[(d + 2) % 4]][c + dy[(d + 2) % 4]] == 0:
cnt += 1
mapFlag[r + dx[(d + 2) % 4]][c + dy[(d + 2) % 4]] = 1
return(nextStep(gameMap, mapFlag, r + dx[(d + 2) % 4], c + dy[(d + 2) % 4], (d + 2) % 4, cnt))
elif gameMap[r + dx[(d + 1) % 4]][c + dy[(d + 1) % 4]] == 0 and mapFlag[r + dx[(d + 1) % 4]][c + dy[(d + 1) % 4]] == 0:
cnt += 1
mapFlag[r + dx[(d + 1) % 4]][c + dy[(d + 1) % 4]] = 1
return(nextStep(gameMap, mapFlag, r + dx[(d + 1) % 4], c + dy[(d + 1) % 4], (d + 1) % 4, cnt))
elif gameMap[r - dx[d]][c - dy[d]] == 0:
return(nextStep(gameMap, mapFlag, r - dx[d], c - dy[d], d, cnt))
else:
return cnt
N, M = map(int, input().split())
r, c, d = map(int, input().split())
gameMap = []
for i in range(N):
gameMap.append(list(map(int, input().split())))
mapFlag = [[0 for i in range(M)]for j in range(N)]
mapFlag[r][c] = 1
cnt = 1
print(nextStep(gameMap, mapFlag, r, c, d, cnt))문제에서 주어진 메뉴얼을 순서대로 구현한 후, 함수를 재귀적으로 호출하여 답을 구하도록 코드를 작성하였다. 또한, 문제의 맵을 저장하는 배열과 함께 방문 여부를 저장할 배열을 하나 더 만들어 이를 확인하였다.
추가로, 그동안 책의 모범답안에 나왔던 방식대로, x, y의 변화에 대한 배열을 만들어 d에 따른 인덱스 접근으로 해결하도록 하였다.
🐾 답안 예시
< 이것이 취업을 위한 코딩 테스트다 with 파이썬 > 답안 예시
# 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)예시 답안에서는 재귀가 아닌 반복을 통해 답을 구하였는데 전체적인 알고리즘은 비슷한 듯 하다.
참고자료
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈
