[Algorithm] D-16 경쟁적 전염 ,괄호 변환, DFS와 BFS

경쟁적 전염

# https://www.acmicpc.net/problem/18405
from collections import deque

n, k = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))

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

time = 0
# 상하좌우
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

queue = []
for i in range(n):
    for j in range(n):
        # 바이러스 이면 다 집어넣기
        if data[i][j] != 0:
            # data[i][j](바이러스 종류) i,j(좌표) , 시간
            queue.append([data[i][j], i, j, time])
# 바이러스 종류 정렬
queue.sort()

queue = deque(queue)

while queue:
    virus, a, b, time = queue.popleft()
    if time == s:
        break
    for i in range(4):
        rx = a + dx[i]
        ry = b + dy[i]
        if rx < 0 or ry < 0 or rx >= n or ry >= n:
            continue
        if data[rx][ry] == 0:
            data[rx][ry] = data[a][b]
            queue.append([data[rx][ry], rx, ry, time + 1])

print(data[x - 1][y - 1])

상하좌우 움직이는 문제 많이 나오는데 패턴이 똑같아서 한번만 제대로 익히면 좋은것같다.

괄호변환

카카오 문제는 문제가 잘 이해가 안간다 왜 난이도 1인것..?

DFS BFS

# https://www.acmicpc.net/problem/1260
from collections import deque

n,m,v=map(int,input().split())
visited=[0] * (n+1)
data=[[0] * (n+1) for i in range (n+1)]
for i in range(m):
    a,b=map(int,input().split())
    data[a][b]=1
    data[b][a]=1

def dfs(v):
    visited[v]=1
    print(v,end=' ')
    for i in range (1,n+1):
        if visited[i]==0 and data[v][i]==1:
            dfs(i)

def bfs(v):
    visited[v]=0
    queue=deque([v])
    while queue:
        v=queue.popleft();
        print(v, end=' ')
        for i in range(1,n+1):
            if visited[i] == 1 and data[v][i] == 1:
                queue.append(i)
                visited[i] = 0


dfs(v)
print()
bfs(v)

bfs dfs 코드를 안보고 짜는건 아직 안된다....