[DFS/BFS] 18352번, 18405번

1. 특정 거리의 도시 찾기

링크 - https://www.acmicpc.net/problem/18352

코드

from collections import deque
import sys

input = sys.stdin.readline
#input
n,m,k,x = map(int,input().rstrip().split())

graph = [[] for i in range(n+1)]
answers=[]
def check_distance(x):
    q = deque()
    visited=[False]*(n+1)
    #노드와 거리
    q.append([x,0])
    visited[x]=True
    while q:
        now,count = q.popleft()
        if count==k:
            answers.append(now)
            continue
        for i in graph[now]:
            if not visited[i]:
                visited[i]=True
                q.append([i,count+1])
                
for _ in range(m):
    s,e = map(int,input().rstrip().split())
    graph[s].append(e) #단방향

check_distance(x)
if len(answers)==0:
    print(-1)
else:
    answers.sort()
    for a in answers:
        print(a)

bfs를 이용해서 푸는 간단한 문제였다. 다익스트라를 이용해서도 풀 수 있을 듯 하다.
큐에 노드 뿐만 아니라 거리 정보도 추가해주어 거리가 k가 되면 정답 리스트에 추가를 해준다.

bfs함수명을 의미있게 썼는데 호출할 때 bfs라고 호출해서 틀렸고, answers를 정렬을 안해줘서 틀렸다... 문제 잘 보기!!!!

경쟁적 전염

링크 - https://www.acmicpc.net/problem/18405

코드

from collections import deque
import sys

input = sys.stdin.readline

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

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

#지도 입력
graph=[list(map(int,input().split())) for _ in range(n)]

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

virus=[]

for i in range(n):
    for j in range(n):
        if graph[i][j]!=0:
            virus.append((graph[i][j],i,j,0))

#바이러스 번호를 기준으로 정렬
virus.sort()

def spread_virus():
    q=deque(virus)
    #바이러스를 큐에 넣는다. 
    
    while q:
        num,sx,sy,time = q.popleft()
        if time==s:
            break
        for i in range(4):
            nx = sx+dx[i]
            ny = sy+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if graph[nx][ny]==0:
                    graph[nx][ny]=num
                    q.append((num,nx,ny,time+1))
                    

spread_virus()
print(graph[x-1][y-1])

visited 리스트를 따로 안만들고 graph 자체를 방문 확인용으로 사용했다.
bfs를 이용해서 s초 동안 확산을 시키도록 구현을 했다.