[이것이 코딩테스트다] 구현 (3) 게임개발

실전 문제

난이도 ●●

풀이시간 40분

시간제한 1초

메모리 제한 128MB

 

문제

1x1 크기의 정사각형으로 이뤄진 NxM 크기의 직사각형으로 각각의 칸은 육지 또는 바다.

캐릭터는 동서남북 중 한 곳을 바라봄

 

맵의 칸은 각 (A, B)로 나타낼 수 있으며 A는 북쪽으로부터 떨어진 칸의 개수. B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 메뉴얼은 이러하다.

 

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전하는 방향)부터 차례대로 갈 곳을 정함

2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로부터 한칸을 전진한다.

왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

3.만약 네방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

 

위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고한다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

 

[입력조건]

* 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력(3<=N, M<=50)

* 둘째 줄에 게임 캐릭터가 있는 칸의 좌표와 바라보는 방향 d 가 각각 서로 공백으로 구분하여 주어짐 방향 d의 값으로는

0 : 북

1 : 동

2 : 남

3 : 서

* 셋째 줄부터 맵이 육지인지 바다인지 정보 주어짐 

육지 : 0

바다 : 1

 

처음 캐릭터가 위치한 칸은 항상 육지

이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

 

[입력예시]

4 4

1 1 0

1 1 1 1

1 0 0 1

1 1 0 1

1 1 1 1

 

해결 방법

구현은 말그래도 머릿속에 있는 알고리즘을 소스코드로 구현하는 과정이다. 

완전탐색과 시뮬레이션 유형 이 두가지로 구분할 수 있다.

 

완전탐색 : 모든 경우의 수를 주저 없이 다 계산하여 해결하는 유형

시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해서 문제를 해결하는 유형

 

문제를 접하면 차례대로 과정이 써있는 것을 보고 시뮬레이션으로 풀어야겠다란 생각을 해야한다.

문제 이해가 핵심

코드

#게임개발
#현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 갈곳을 정함
#캐릭터의 바로 왼쪽 방향에 아직 가보지 않은칸이 존재 ->왼쪽 방향으로 회전한 다음 왼쪽으로 한칸 전진, 있다면 왼쪽 방향으로만 회전
#만약 네 방향 모두 가본칸이거나 바다로 되어있다면 바라보는 방향을 유지한 채 한칸 뒤로 가고 1단계로 돌아감. 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없으면 움직임을 멈춤

n, m=map(int,input().split())
x,y,d=map(int, input().split())

#맵 정보 입력해 리스트에 저장
map_list=[]
for _ in range(n):
        row=list(map(int,input().split()))
        map_list.append(row)
map_list[x][y]=1

def rotation() :
    global d
    d-=1
    if d==-1 :
        d=3

dx=[-1,0,1,0]
dy=[0,1,0,-1]
#시뮬레이션 시작

cnt=1
rotation_cnt=0
while True : 
    rotation()
    nx=x+dx[d]
    ny=y+dy[d]

    #회전한 이후 정면에 가보지 않은 칸이 있는 경우
    if map_list[nx][ny]==0 :
        map_list[nx][ny]=1
        x=nx
        y=ny
        cnt+=1
        rotation_cnt=0
        continue
    else :
        rotation_cnt+=1
    
    #네 방향 모두 갈 곳이 없을 경우
    if rotation_cnt==4 :
        nx=x-dx[d]
        ny=y-dy[d]
        if map_list[nx][ny]==0 :
            x=nx
            y=ny
        #뒤가 바다일 경우 탈출
        else :
            break
        rotation_cnt=0

print(cnt)

<간략설명>

n, m 입력을 받아 n*m 의 이중 배열 형태로 map 리스트를 입력받아 저장하고 회전해가며 전방에 0이 있는지 체크하고 있을 경우 1로 변경 후 x와 y이동

이때 회전 함수 rotation()에 gloabal을 써서 전역변수로 받자

전방에 0이 없을 경우 후방이 0일 경우 이동, 없을 경우 반복문 탈출한다

 

 

※이 포스팅은 <이것이 취업을 위한 코딩테스트다(나동빈 저)> 책 내용을 바탕으로 작성되었습니다.