게임 개발(이코테 실전문제)

처음에 이 문제를 접근할 때 단순히 bfs 알고리즘을 사용해서 갈 수 있는 방향을 탐색하고, 카운트를 늘려주었다. 그렇게, 더이상 방문할 수 있는 칸이 남아있지 않다면 탐색을 종료하도록 했다.

 

하지만 그렇게 했을 때 세번째 매뉴얼, '만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.'을 만족할 수 없었다.

그래서 네 방향을 모두 탐색했을 때 더이상 갈 수 있는 방향이 없다면, visited로 처리한 칸이라도 다시 방문했어야 했는데, 여기서 애를 좀 먹었다.

 

따라서 회전수를 기록하는 turn_times 변수를 선언해서 몇번 회전했는지 추적해야했다. 더이상 갈 수 있는 방향이 없고, 이때 회전수가 4번 이상이라면 이미 간 방향이라도 다시 갈 수 있도록 말이다.

 

위 내용만 숙지한다면, 일반 탐색문제와 다를 빠 없었다.

 

코드

import sys
n, m = map(int, sys.stdin.readline().split())
a, b, d = map(int, sys.stdin.readline().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]

# 현재 좌표를 방문 처리
visited[a][b] = True

# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽으로 회전 시켜주는 함수
def turn_left():
    global d
    d -= 1
    if d < 0:
        d = 3

cnt = 1

# 회전 횟수를 저장해주는 변수!! 회전횟수가 4개가 되면 뒤로 한 칸 이동해야한다!
turn_time = 0
while True:

    # 왼쪽 회전
    turn_left()
    nx = dx[d] + a
    ny = dy[d] + b

    if not visited[nx][ny] and matrix[nx][ny] != 1:
        visited[nx][ny] = True
        cnt += 1
        a = nx
        b = ny
        # 회전한 곳으로 갈 수 있다는 뜻은 추가적인 회전이 필요 없는것.
        turn_time = 0
        continue
    # 회전한 곳으로 갈 수 없는 경우 추가적인 회전이 필요.
    else:
        turn_time += 1
    
    # 모든 방향이 가본곳이거나, 바다라서 갈 수 없어 회전만 4번한 경우
    # 방향을 유지한 채로 뒤로가야함 때문에 turn_time += 1 한후 바로 if로 조건검사를 해야한다.
    # 뒤로 한칸가고 1단계로 돌아간다.
    if turn_time == 4:
        nx = a - dx[d]
        ny = b - dy[d]

        # 만약 뒤로 가려는데, 바다인 경우 모험을 종료한다.
        if matrix[nx][ny] == 1:
            break
        else:
            a = nx
            b = ny
        
        # 4번 다 돌았다면, 방향을 유지하고 뒤로 가야한다.
        # 이미 visited는 모두 방문 되었기 때문에,
        # 다음 while문들은 방향만 회전하고 결국 같은 방향으로 뒤로간다.
        turn_time = 0

print(cnt)