[나동빈 코딩테스트] 구현 문제(게임 개발)

#나동빈 구현 문제 - 게임 개발

#난이도 : 중

N, M = map(int, input().split())  #세로, 가로

A, B, d = map(int,input().split())  #위, 왼쪽으로부터 떨어진 거리

game = []
for k in range(N):
  game.append(list(map(int,input().split())))

game_mark = []
game_mark.append((B+1,A+1))  #시작점 마킹, x좌표와 y좌표 순. 1부터 시작함.


direction_li = [0,1,2,3] #북,동,남,서 순
dx = [0,1,0,-1]
dy = [-1,0,1,0]

direction = d
x = B+1
y = A+1
tol = 0 #방향 바꾸는 한계

while game[y-1][x-1] == 0 : #이동한 곳이 바다면 중단.
  
  if game[y + dy[d] - 1][x + dx[d] - 1] == 0: #육지였을때 (직진, 방향전환, 뒤로가기 중 하나)
    if (x+dx[d],y+dy[d]) not in game_mark:  #가본적이 없으면 직진
      y = y + dy[d]
      x = x + dx[d]
      tol = 0
      game_mark.append((x,y))
    else: #가본적이 있으면 방향 전환 또는 뒤로 가기
      if tol == 4: #tol이 4면 뒤로 가기, game_mark에 넣을 필요 없음. (tol이 4라는뜻은 이미 그쪽방향으로 간적이 있다는 뜻)
        y = y - dy[d]
        x = x - dx[d]
        tol = 0
      else: #tol이 아직 4가 아니면 방향 전환
        d = direction_li[(d-1)%4]  # 반시계 방향 전환, %연산 -1에 적용가능. 이와 같은 순환문제에서 유용하게 사용될듯.
        tol += 1
  else: #바다였을때 (방향전환, 뒤로가기 중 하나)
    if tol == 4: #tol이 4면 뒤로 가기
      y = y - dy[d]
      x = x - dx[d]
      tol = 0
    else: #tol이 아직 4가 아니면 방향 전환
      d = direction_li[(d-1)%4]
      tol += 1

answer = len(game_mark)
print(answer) #그동안 방문했던 칸의 개수 (중복 X)

 

 

# 시간 복잡도 : O(NM) , 단 game_mark에서 서치하는 시간에 따라 변동 가능.

#안전하게 하기 위해서는 game_mark를 game과 같은 크기의 맵 형태로 저장하여 체크해나가는게 나을듯함.

#즉, if (x+dx[d],y+dy[d]) not in game_mark : 대신

if game_mark[m][n] == 0 : 과 같은 조건문 사용