게임 개발[Implement] -2 #이것이 코딩테스트다

2023.03.14 - [WIL/algorithm] - 게임 개발[Implement] -1 #이것이 코딩테스트다

게임 개발[Implement] -1 #이것이 코딩테스트다

 

지난번에 작성해뒀던 게임 개발 문제는 greedy method를 기반으로 하여 이하와 같은 케이스에서 제대로 작동하지 못하는 것을 확인하였습니다.

5 5
1 1 0
1 1 1 1 1
1 0 0 0 1
1 1 0 1 1
1 1 0 1 1
1 1 1 1 1
4

그래서 이 친구를 해결할 방법을 찾아보려고 합니다.

 

<Idea>

Q1. 그러면... 음.... 먼저 주변을 싹 둘러보는게 가장 간단한 답이지 않을까?
A1. 그치? 그러면 스택이나 큐를 가져다 써야할테니까 어떤걸로 할래?
Q2. 음... 그렇게 가면 거의 DFS나 BFS에 가까워지는데?
A2. 그치 이 문제는 조건만 다 빼고 input과 output만 보면 탐색문제잖아?
Q3. 생각해보니까 그러네 그러면 오늘은 BFS를 써보기로 할까?

 

data= list(map(int, input().split()))
x, y, sight=map(int, input().split())
now=(x,y)

#변수 세팅
dir=[(0,1), (1,0), (0,-1), (-1,0)]
table=[]
count=0
queue=[]

for i in range(data[1]):
  table.append(list(map(int,input().split())))
#simulation start
while 1:
  break_= 0
#step I
#step II
  #print("\n now is {},{}".format(now[0],now[1]))
  
  if table[now[0]][now[1]]!=1: #현 위치가 방문하지 않은 장소였다면
    count+=1                   #1을 더해주고
    table[now[0]][now[1]]=1    #테이블을 방문처리 해줍니다.

    for i in range(4):
      nx= now[0] + dir[i][0]
      ny= now[1] + dir[i][1]
      #print("1st phase: {}".format(table[nx][ny]))
      if table[nx][ny] != 0: #만약 앞 테이블이 방문한 적 있거나 바다라면
        continue
      queue.append((now[0],now[1],i)) #방문 해야하는 방향들을 Queue에 저장해줍니다.
      #print(queue)
  #print(table,end='\n')

  #다음 방문 값을 지정해줍니다.
  temp=queue.pop(0)
  nx=temp[0] + dir[temp[2]][0]; ny=temp[1] + dir[temp[2]][1]; sight=temp[2]
  now=(nx,ny)

#step III
  for i in range(4): #사방을 확인해줍니다.
    nx= now[0] + dir[i][0]
    ny= now[1] + dir[i][1]
    #print("2nd phase: {}".format(table[nx][ny]))
    if table[nx][ny] != 1: #만약 방문한 적 없는 위치가 존재한다면 이하는 작동할 이유가 없으니 최상단으로 돌아갑니다.
      break_=1
      break
  if break_ != 0: continue

  #꼬리는 세팅을 안하니까 체크해주고
  if table[now[0]][now[1]]!=1: #현 위치가 방문하지 않은 장소였다면
    count+=1                   #1을 더해주고
    table[now[0]][now[1]]=1    #테이블을 방문처리 해줍니다.

  nx= now[0] - dir[sight][0]
  ny= now[1] - dir[sight][1]
  if table[nx][ny]==1 and not queue: break #뒤를 봤는데 바다이거나 방문한 적 있고 queue가 비어있으면 멈춥니다.
  

print(count)

5 5
1 1 0
1 1 1 1 1
1 0 0 0 1
1 1 0 1 1
1 1 0 1 1
1 1 1 1 1
5

원하는대로 결과가 나왔네요

 

<Review>

메뉴얼에서 원하는 방식대로 구현한건 아니었지만 새로운 방법으로 접근하는 것도 재밌었던 것 같습니다. 다음에는 원본의 틀을 깔끔하게 지킨 식으로 만들어(?) 보겠습니다