[파이썬, 백준 20056] 마법사 상어와 파이어볼

문제

 

문제 바로가기: [백준] 마법사 상어와 파이어볼 

---

풀이

#구현, 시뮬레이션, 큐

 

#풀이

1. 흔히 평범한 N*N 2차원 그래프는 각 칸에 수를 넣어 표시합니다.

1	0	0
2	4	0
3	2	3

2. 그러나, 이번 문제에서는 위의 2차원 그래프에서 숫자가 아닌 리스트(큐)를 넣어줘서 풀이했습니다.

  2-1. 리스트를 큐로 구현했습니다.  

  2-2. 리스트 안에는 질량이 0보다 크면 해당 위치에 [질량,속력,방향] 을 넣어줬습니다.

[[5,2,2]]	[ ]	[ ]
[ ]	[ ]	[[1,9,4]]
[[3,1,2]]	[ ]	[ ]

graph = [[deque([]) for _ in range(N)] for _ in range(N)]

 

3. 모든 파이볼의 이동을 끝냅니다 

  3-1.(큐로 구현한 이유) 출발할 큐의 처음에 하나 빼서, 도착한 큐의 마지막에 삽입합니다

 

4. (반드시 모든 파이어볼 이동부터 끝내야 합니다) 파이어볼 2개 이상인 곳 찾습니다  (ex) [[5,2,2], [3,1,2]] )

 

5. 세부 및 기타 과정들을 구현하고, 위의 과정들을 반복합니다

---

코드

from collections import deque

N,M,K = map(int,input().split())


graph = [[deque([]) for _ in range(N)] for _ in range(N)]    #핵심
command = []
for _ in range(M):
  x,y,m,s,d = map(int,input().split()) #위치x,위치y, 질량,속력,방향  

  graph[x-1][y-1].append([m,s,d])
  command.append([x-1,y-1,m,s,d])

dx = [-1,-1, 0, 1, 1,  1, 0,  -1]
dy = [ 0, 1, 1, 1, 0, -1, -1, -1]


count_k = 0
while True:
  #모든 파이어볼 이동하기
  for x,y,m,s,d in command:
    graph[x][y].popleft()

    count = 0
    while True:
      nx = x + dx[d]
      ny = y + dy[d]

      if nx == N:
        nx = 0
      elif nx == -1:
        nx = N-1
      if ny == N:
        ny = 0
      elif ny == -1:
        ny = N-1
      
      x = nx
      y = ny
      
      count += 1
      if count == s:
        graph[x][y].append([m,s,d])
        break

  command = []
  #파이어볼이 2개 이상인 곳 찾기   
  for x2 in range(N):
    for y2 in range(N):
      if len(graph[x2][y2]) >= 2:
        sum_m = 0
        sum_s = 0
        sum_d_odd = 0
        sum_d_even = 0
        for fireball in graph[x2][y2]:
          sum_m += fireball[0]
          sum_s += fireball[1]
          if fireball[2] % 2 == 0:
            sum_d_even += 1
          else:
            sum_d_odd += 1

        sum_m = sum_m // 5
        sum_s = sum_s // len(graph[x2][y2])
        if sum_d_even == len(graph[x2][y2]) or sum_d_odd == len(graph[x2][y2]):
          if sum_m != 0:
            command.append([x2,y2,sum_m,sum_s,0])
            command.append([x2,y2,sum_m,sum_s,2])
            command.append([x2,y2,sum_m,sum_s,4])
            command.append([x2,y2,sum_m,sum_s,6])
            graph[x2][y2] = deque([[sum_m,sum_s,0],[sum_m,sum_s,2],[sum_m,sum_s,4],[sum_m,sum_s,6]])
          else:
            graph[x2][y2] = deque([])
        else:
          if sum_m != 0:
            command.append([x2,y2,sum_m,sum_s,1])
            command.append([x2,y2,sum_m,sum_s,3])
            command.append([x2,y2,sum_m,sum_s,5])
            command.append([x2,y2,sum_m,sum_s,7])
            graph[x2][y2] = deque([[sum_m,sum_s,1],[sum_m,sum_s,3],[sum_m,sum_s,5],[sum_m,sum_s,7]])
          else:
            graph[x2][y2] = deque([])
      elif len(graph[x2][y2]) == 1:
        for m,s,d in graph[x2][y2]:
          command.append([x2,y2,m,s,d])
      
  count_k += 1
  if count_k == K:
    break

#정답
answer = 0
for x in range(N):
  for y in range(N):
    while graph[x][y]:
      result = graph[x][y].popleft()
      answer += result[0]

print(answer)