게임 개발

이 문제는 이것이 코딩테스트다 118페이지에 있는 문제이며 난이도는 2/3 이고 풀이시간은 40분이다.

이 문제는 한번 풀어본 적이 있어서 풀이시간안에 풀 수 있었다. 

DFS 문제와 거의 흡사한 듯하다.

 

아래는 나의 코드다.

import sys

direction=[(0,-1),(1,0),(0,1),(-1,0)] #북,동,남,서
mymap = []
n,m=map(int,sys.stdin.readline().split())
x, y, start_direction = map(int,sys.stdin.readline().split())
for i in range(n):
    mymap.append(list(map(int,sys.stdin.readline().split())))
result=0

def move(x,y,d):

    mymap[x][y]= 2 # 지나간
    global result
    result +=1
    for i in range(4):      #네방향 모두 확인
        if mymap[x+direction[(d-1+4)%4][0]][y+direction[(d-1+4)%4][1]]==0:   # d-1 에 +4 해준 이유는 음수가 될 수 있어서 해줌
            x=x+direction[(d-1+4)%4][0]  #x좌표 이동
            y=y+direction[(d-1+4)%4][1]  #y좌표 이동 칸
            d= (d - 1 + 4) % 4          # 방향 변경
            move(x,y,d)                 #이동
        else:
            d=(d-1+4)%4
                            # 함수끝나면서 이전의 함수로 돌아감 = 뒤로 한칸감

move(x,y,start_direction)

print(result)

 

 

아래는 예시코드이다.

 

# 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)

 

나는 DFS방식과 흡사하게 풀었는데 예시에서는 반복문안에서 처리를 하였다. 

아마 나도 DFS 문제 경험이 없었다면 위와 같이 풀지 않았을까...