BFS_경쟁적 전염(LEVEL2)
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])
BFS_미로 탈출
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque()
queue.append((x, y)
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = x + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return graph[n - 1][m - 1]
print(bfs(0, 0))
[이코테] BFS/DFS_연구소
n, m = map(int, input().split())
data = []
temp = [[0] * m for _ in range(n)]
for _ in range(n):
data.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
result = 0
def virus(x, y):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= 0 and nx < n and ny >= 0 and ny < m:
if temp[nx][ny] == 0:
temp[nx][ny] = 2
virus(nx, ny)
def get_score():
score = 0
for i in range(n):
for j in range(m):
if temp[i][j] == 0:
score += 1
return score
def dfs(count):
global result
if count == 3:
for i in range(n):
for j in range(m):
temp[i][j] = data[i][j]
for i in range(n):
for j in range(m):
if temp[i][j] == 2:
virus(i, j)
result = max(result, get_score())
return
for i in range(n):
for j in range(m):
if data[i][j] == 0:
data[i][j] = 1
count += 1
dfs(count)
data[i][j] = 0
count -= 1
dfs(0)
print(result)