둔필승총

https://www.acmicpc.net/problem/18352

1.

처음에 풀었을 때 BFS로 미로찾기와 비슷하게 풀었는데 메모리 초과가 생겼다. 

from collections import deque
import sys
input = sys.stdin.readline
n,m,k,x = map(int,input().split())
#도시의 개수 n, 도로의 개수 m, 거리 정보 k, 출발 도시의 번호 x
graph=[[0]*(n+1) for _ in range(n+1)]
distance=[99999]*(n+1)
visited=[False]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    graph[a][b]=1

def bfs(v):
    q=deque([v])
    distance[v]=0
    while q:
        x = q.popleft()
        for i in range(1,n+1):
            if graph[x][i]==1:
                q.append(i)
                distance[i]=min(distance[x]+1,distance[i])
bfs(x)
answer=[]
for i in range(len(distance)):
    if distance[i]==k:
        answer.append(i)
if len(answer)==0:
    print(-1)
else:
    for i in range(len(answer)):
        print(answer[i])

거리가 K인 것만 출력하면 된다는 사실과 graph를 통해 모든 지점을 탐색할 필요는 없다는 점을 통해 메모리 초과를 해결할 수 있었다.

2.

모든 도로의 거리는 1이다. 너비 우선 탐색을 이용하여 해결할 수 있다. 앞서 미로찾기와 같이 이동할 때의 거리는 +1하면서 해결할 수 있다. 문제의 조건에서 노드의 개수 N은 최대 300000개, 도로의 개수 M은 최대 1000000개이다. 따라서 BFS를 사용하여 시간 복잡도 O(N+M)으로 작동하는 소스코드를 작성하여 해결할 수 있다.

from collections import deque
n,m,k,x = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ 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)

3.

다익스트라 알고리즘이 유용하게 쓰이진 않지만 그 틀을 사용해서 풀었다.

import sys
input = sys.stdin.readline
from collections import deque

n,m,k,x = map(int,input().split())
visited = [False]*(n+1)
graph = [[] for _ in range(n+1)]
answer=[]

for _ in range(m):
    i,j = map(int,input().split())
    graph[i].append(j)

queue=deque()
queue.append((x,0))
visited[x]=True

while queue:
    v,dist=queue.popleft()
    if dist == k:
        answer.append(v)
    elif dist<k:
        for i in graph[v]:
            if not visited[i]:
                visited[i]=True
                queue.append((i,dist+1))

if len(answer)==0:
    print(-1)
else:
    answer.sort()
    for i in range(len(answer)):
        print(answer[i])