7. DFS/BFS(특정 거리의 도시 찾기, 경쟁적 전염)

<문제> 특정 거리의 도시 찾기(⭐)

# 특정 거리의 도시 찾기
from collections import deque
n,m,k,x = map(int,input().split())
graph = [[]for _ in range(n+1)]
for i in range(m):
    a,b = map(int, input().split())
    graph[a].append(b)
distance = [-1] * (n+1)
distance[x] = 0

q = deque([x])
while q:
    now = q.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            q.append(next_node)
check = False
for i in range(1,n+1):
    if distance[i] == k:
        print(i)
        check = True
if check == False:
    print(-1)

<문제> 경쟁적 전염(⭐)

# 경쟁적 전염
from collections import deque


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


graph = []
data = []

for i in range(n) :
    graph.append(list(map(int, input().split())))
    for j in range(n) :
        if graph[i][j] != 0 :
            data.append((graph[i][j], 0, i, j))
data.sort()
q = deque(data)

target_s, target_x, target_y = map(int, input().split())

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


while q :
    virus, s, x, y = q. popleft()
    if s == target_s :
        break

    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 < nx and nx < n and 0 < ny and ny < n :
            if graph[nx][ny] == 0 :
                graph[nx][ny] = virus
                q.append((virus, s+1, nx, ny))

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

Uploaded by Notion2Tistory v1.1.0