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

  • 0
  • 0
0
0

1. 경쟁적 전염

A. 문제

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

B. 내 답안

a. 1차 시도 (실패)

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차 시도 (성공)

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. 문제 해설

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

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

a. 책 답안

python-for-coding-test/3.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

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

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

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.