[이코테] DFS/BFS - 경쟁적 전염

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

18405번: 경쟁적 전염

사고과정

• BFS를 생각했는데, 너무 복잡하게 생각한 듯하다.. 한 초에 증식된 후, 꼭 한 좌표에서 탐색을 시작해야되라고 생각해서 여기서 사고의 흐름이 완전 망가졌다.. 한 번 증식한 후, 다시 큐에서 꺼내서 해당 좌표에서 계속 탐색하면 되는데.. 너무 복잡하게 생각하는 것 같다.. 아~~~~~~~~
• 처음에 시간이 흘러감에 따라 반복문을 돌것이라고 생각했는데, 시간 변수까지 큐에 넣고 시간을 +1 업데이트하는 아이디어를 떠올리지 못했음..
• 입력을 한 줄씩 받아가면서 큐에 넣을 정보를 append 하는 것도 인상적이었음..
• 낮은 번호의 바이러스부터 활용하는 것을 보고 우선순위 큐를 활용할 수도 있다고 생각했음.

풀이(스스로 못 푼 풀이)

from collections import deque

n, k = map(int, input().split())
array = []
data = []
for i in range(n):
    array.append(list(map(int, input().split())))
    for j in range(n):
        if array[i][j] != 0:
            data.append((array[i][j], 0, i, j))  # 시간을 넣는 아이디어..
target_t, target_x, target_y = map(int, input().split())

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

data.sort()
queue = deque(data)

while queue:
    virus, s, x, y = queue.popleft()
    if s == target_t:
        break
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny  < n:
            if array[nx][ny] == 0:
                array[nx][ny] = virus
                queue.append((virus, s+1, nx, ny))


print(array[target_x-1][target_y-1])