[DFS, BFS, 구현] 이코테, 백준 18405번 경쟁적 전염, 두가지 풀이

경쟁적 전염

https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

 

사고 과정

1. 보자마자 떠오르는 것은 이를 그대로 구현하는 방법이다. 매번 1, 2, 3 순서대로 전개하고 마지막에 정답을 찾는다. 매 초마다 1,2,3 순으로 전개해줘야 하기 때문에 순서를 queue를 이용하여 구하면 된다. 목표 위치에 가장 빨리 도달하는, 목표 위치를 가장 빨리 탐색하는 노드를 찾는 문제이므로 BFS로 해석할 수 있다. 
2. 또다른 풀이는 '구현' 방법을 사용한다. '바로 답이 나올 수 있는 경우'를 생각해보자. 처음부터 해당 위치에 바이러스가 있다면 계산 조차 의미가 없어져서 바로 답이 나올 수 있다. 또한 목표 위치에 가장 빨리 도달하는 노드를 찾으므로 단순 거리 계산으로만으로도 찾을 수 있다. 가장 거리가 가까운 세포가 도착하게 될것이다. 단, 예외처리를 신경쓰자.

 

 

<BFS>

from collections import deque

N, K = map(int, input().split())
testMap = []
for _ in range(N):
  testMap.append(list(map(int, input().split())))
S, X, Y = map(int, input().split())

# 바이러스별 위치 배열 생성
virusDataList = []
for i in range(N):
  for j in range(N):
    if testMap[i][j] != 0:
      # 바이러스 값, 바이러스 도착 시간, 위치i, 위치j
      virusDataList.append((testMap[i][j], 0, i, j))
virusDataList.sort()

# 상하좌우
di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

# bfs
queue = deque(virusDataList)

while queue:
  curNode = queue.popleft()
  ck = curNode[0]
  ct = curNode[1]
  ci = curNode[2]
  cj = curNode[3]
  if ct == S:
    break

  for i in range(4):
    ni = ci + di[i]
    nj = cj + dj[i]
    if ni < 0 or ni > len(testMap) - 1 or nj < 0 or nj > len(testMap[0]) - 1:
      continue
    if testMap[ni][nj] == 0:
      queue.append((testMap[ni][nj], ct + 1, ni, nj))
      testMap[ni][nj] = testMap[ci][cj]

print(testMap[X - 1][Y - 1])

 

 

<거리로 바로 계산>

N, K = map(int, input().split())
# 정적 배열로 고쳐보기
testMap = []
for _ in range(N):
  testMap.append(list(map(int, input().split())))
S, X, Y = map(int, input().split())

# 거리
dist = 999999999
shortestVal = K
si = 0
sj = 0

if testMap[X - 1][Y - 1] != 0:
  print(testMap[X - 1][Y - 1])
else:
  for i in range(N):
    for j in range(N):
      if testMap[i][j] != 0:
        tempDist = abs(i - (X - 1)) + abs(j - (Y - 1))
        if tempDist <= dist:
          if tempDist == dist:
            if testMap[i][j] >= shortestVal:
              continue
          dist = tempDist
          shortestVal = testMap[i][j]
          si = i
          sj = j

  if dist > S:
    print(0)
  else:
    print(testMap[si][sj])

 

 

당연히 가장 시간이 덜 들고 짧은 코드는 '구현' 방법으로 푼 거리계산 코드다.

항상 한번에 풀 수 있는 더 좋은 풀이가 있을까. 더 단순하게 풀 수 있을까 생각해보자.