# [이.취.코] [백준] Chap 13. BFS_DFS - Q17. 경쟁적 전염

- Author: @mildsalmon
- Published: 2021-09-23
- Updated: 2021-09-23
- Source: http://blex.me/@mildsalmon/%EC%9D%B4%EC%B7%A8%EC%BD%94-%EB%B0%B1%EC%A4%80-chap-13-bfs_dfs-q17-%EA%B2%BD%EC%9F%81%EC%A0%81-%EC%A0%84%EC%97%BC
- Tags: 파이썬, 알고리즘, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, bfs, 백준

---

# 1. 경쟁적 전염

- 난이도
	- 중
- 풀이 시간
	- 50분
- 시간 제한
	- 1초
- 메모리 제한
	- 256 MB
- 출처
	- [18405번: 경쟁적 전염 (acmicpc.net)](https://www.acmicpc.net/problem/18405)

### A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

	
### B. 내 답안

##### a. 1차 시도 (실패)

```python

def dfs(graph, s, x, y):
    global n

    ds = ((-1, 0), (1, 0), (0, -1), (0, 1))

    # for i in range(s):
    if s < 0:
        return
    else:
        s -= 1
        for d in ds:
            dx = x + d[0]
            dy = y + d[1]

            if dx < 0 or dx >= n or dy < 0 or dy >= n:
                continue
            if graph[dx][dy] == 0 and temp_graph[dx][dy] == 0:
                graph[dx][dy] = graph[x][y]
            elif graph[dx][dy] != 0 and temp_graph[dx][dy] == 0:
                graph[dx][dy] = min(graph[x][y], graph[dx][dy])
                continue
            elif graph[dx][dy] != 0 and temp_graph[dx][dy] != 0:
                continue
                # graph[dx][dy] = max(graph[dx][dy], temp_graph[x][y])
            dfs(graph, s, dx, dy)

global n

n, k = list(map(int, input().split()))

graph = []
# 0, 0부터 리스트에 담는거 까먹음
for i in range(n):
    temp = list(map(int, input().split()))
    graph.append(temp)

s, x, y = list(map(int, input().split()))
x -= 1
y -= 1
temp_graph = [i[:] for i in graph]

# for i in range(n):
#     for j in range(n):
#         dfs(graph, s, i, j)
#
for i in range(s):
    for i in range(n):
        for j in range(n):
            if temp_graph[i][j] != 0:
                dfs(graph, s, i, j)

if graph[x][y] == 0:
    print(0)
else:
    print(graph[x][y])

print(*graph, sep='\n')

```

##### b. 2차 시도 (성공)

```python

from collections import deque

n, k = list(map(int, input().split()))

graph = [[0] * (n+1) for i in range(n+1)]
data = []

for i in range(1, n+1):
    temp = list(map(int, input().split()))

    for j in range(1, n+1):
        graph[i][j] = temp[j-1]

        if graph[i][j] != 0:
            data.append([graph[i][j], 0, i, j])

# for i in range(1, n+1):
#     temp = [0]
#     temp.append(list(map(int, input().split())))
#     # graph.append(temp)
#     for t in range(len(temp)):
#         if temp[t] != 0:
#             data.append([temp[t], 0, i, t])

s, x, y = list(map(int, input().split()))

data.sort()
q = deque(data)

ds = ((-1, 0), (1, 0), (0, -1), (0, 1))

while q:
    q_value, q_s, q_x, q_y = q.popleft()

    if q_s == s:
        break

    for d in ds:
        dx = q_x + d[0]
        dy = q_y + d[1]

        if dx < 1 or dx > n or dy < 1 or dy > n:
            continue

        if graph[dx][dy] != 0:
            continue

        graph[dx][dy] = q_value
        q.append([q_value, q_s+1, dx, dy])

print(graph[x][y])

```

##### c. 회고

> 내 풀이

- dfs라고 생각했다. 그래서 그냥 DFS로 풀려고 했다.

> 반성

- 바이러스의 값이 작은 것부터 전파된다는 점이 DFS로는 풀 수 없는 한계였다. 

> 결론

- 문제를 잘 파악해서, DFS가 효율적일지 BFS가 효율적일지 생각하자.

### C. 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

시간이 흐를때마다 바이러스는 값이 작은 것부터 확산된다. 바이러스가 위치한 곳에 다른 바이러스는 확산되지 못한다. (비선점 스케줄링)

![](https://static.blex.me/images/content/2021/9/23/9_KhAfutTldhosxNHHXw61.jpg)

##### a. 책 답안

[python-for-coding-test/3.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/13/3.py)

# 참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] [baekjoon](https://www.acmicpc.net/user/baekjoon). [1065번: 한수 (acmicpc.net)](https://www.acmicpc.net/problem/1065). Baekjoon. (accessed Sep 5, 2021)