728x90
반응형
https://www.acmicpc.net/problem/18352
18352번: 특정 거리의 도시 찾기
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개
www.acmicpc.net
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])728x90
반응형
'알고리즘 > 알고리즘 문제' 카테고리의 다른 글
| [파이썬] [프로그래머스 괄호 변환 60058] [kakao blind recruitment] (0) | 2021.08.27 |
|---|---|
| [파이썬] [백준 18405 경쟁적 전염] (0) | 2021.08.26 |
| [파이썬] 백준 2178번 (DFS/BFS) 미로 탐색 (0) | 2021.08.23 |
| 10845 큐 / 10866 덱 / 1406 에디터 (0) | 2021.08.05 |
| [파이썬] [백준 - 7569번] 토마토 (BFS) (0) | 2021.06.07 |
