문제
어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.
이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.
입력
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.
출력
X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.
이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.
예제 입력 1
4 4 2 1
1 2
1 3
2 3
2 4예제 출력 1
4예제 입력 2
4 3 2 1
1 2
1 3
1 4예제 출력 2
-1예제 입력 3
4 4 1 1
1 2
1 3
2 3
2 4예제 출력 3
2
3나같은 평범한 사람은 새로운 문제를 접하면 응용력이 너무 떨어진다. 그래서 많이 풀고 많이 복습해야 내껄로 되는, 박지성 형님의 천재성은 없으나, 그 노력의 아이콘같은 모습이 되기 위해 계속 풀이 보고 이해하고 해석하는 일을 2년하다보면 언젠가 실력이 늘어있지 않을까 싶다 ㅎㅎ
자 서론이 길었고 문제 해석!!
# 1~N번 도시 M개의 단방향 도로 모든 도로 거리 1
# N - 도시의 개수 M - 도로의 개수
# K - 거리 정보 X - 출발 도시
# 도달하는 도시 번호 출력총 4개의 정보를 받아와야함
N - 도시의 총 갯수
M - 도시와 도시1개를 잇는 도로의 갯수
K - 총 몇개의 도시를 잇는 갯수
X - 출발 시작 도시
결국 도시에서 여러 갈래로 뻗쳐있는 도로를 체크해가며 K만큼의 이어져있는 도로를 갈 수 있는 도시가 몇개 있나 X부터 시작해서 구하는 문제이다
다익스트라 알고리즘을 배워서 그걸 적용해보고 싶었는데,
일단 bfs로 풀어보겠다
import sys
from collections import deque
imput = sys.stdin.read
data = input().splitlines()처음 splitlines를 사용해 봤는데,
splitlines() 메서드는 줄바꿈 문자를 기준으로 문자열을 나눠 리스트로 반환
즉 data[0]이 4 4 2 1을 한번에 받아옴
N,M,K,X = map(int, data[0].split())인트화 시켜서 각각 입력 값 담기
graph = [[] for _ in range(N+1)]가독성을 늘리기 위해 0인덱스를 제외한 1번에 1인덱스를 사용하기 위해 N+1까지 범위 설정
for i in range(1, M+1):
A, B = map(int, data[i].split())
graph[A].append(B)이 for반복문의 의미는,
1번도시에서 몇번도시로 갈 수 있나를 담아주는 의미
즉 저 for 반복문을 진행하면
[[],[2,3],[3,4],[],[]]0번째 인덱스는 무시하고,
1번 인덱스는 2,3도시로 갈 수 있고
2번 인덱스에선 2번도시가 3,4 도시로 갈 수 있고
3번 도시는 갈 곳이 없고
4번 도시 또한 갈 곳이 없다
queue = deque([X])
distances = [-1]*[N+1)
distances[X] = 0X 도시에서 시작해서 이웃 도시까지 갈 수 있나 없나 점검할 것이므로, queue에 담아준다.
distances의 초기값을 inf로 설정해도되지만 어쨋든 움직일 수 있는 거리가 있나 없나만 판단하면 되므로 임의로 -1를 각 인덱스에 담아준다
그리고 X에서 X로 가는 거리는 0으로 초기값을 설정해준다
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if distances[neighbor] == -1:
distances[neighbor] = distances[curruent] + 1
queue.append(neighbor)이 것 또한 분석하면 이해하지만 바로 내 머리속에선 떠오르지 않은 코드인데,
queue가 존재하면 계속 반복하면서,
처음 담은 X를 popleft로 빼내고, current에 담아준다.
그리고, graph의 X인덱스에 만약에 값이 있다? 그건 움직일 도시가 있다는 뜻!
그래서 거기서 뽑아낸 다른 도시로의 이동을 neighbor로 만들어서,
만약 distances[neightbor]가 -1이다? 아직 체크해보지 못한 도시다.
그러면 거기는 이동이 된다는 소리니까? 기존 distances[X]의 초기값0에서 1을 더해준다.
모든 도시간의 이동거리는 1이기 때문에,
그리고 그 위치를 다시 queue에 담아줘서 해당 위치에서 또 움직일 수 있는 도시가 있나 체크한다. 그러다보면 최초 도시부터 시작한 거리기 때문에 이어진 최대 도시까지 거리가 중복되서 더해진다.
그러한 과정이 이 while문에 담겨있다.
result = []
for city in range(1, N+1):
if distances[city] == K:
result.append(city)
if result:
result.sort()
print('\n'.join(map(str, result)))
else:
print(-1)최종 몇 몇 도시가 K만큼의 거리로 갈 수 있는지 체크위해 result를 만들고
1~N+1까지 반복하며 해당 위치에 distances가 K만큼거리에 존재하면 그 city가 갈 수 있는 도시이므로 append로 담고
오름차순 정리해서 print로 뽑아내고 없으면 -1을 출력하면 된다.
'\n'을 통해 줄 바꿈 출력 시키고, 이미 sort화시켰기 때문에 str로 뽑아낸다 그리고 join은 문자열 형태일때만 사용가능!!! 이부분도 새로알았다
그럼 최종 코드
import sys
from collections import deque
input = sys.stdin.read
data = input().splitlines()
N,M,K,X = map(int, data[0].split())
graph = [[] for _ in range(N+1)]
for i in range(1, N+1):
A, B = map(int, data[i].split())
graph[A].append(B)
queue = deque([X])
distances = [-1]*(N+1)
distances[X] = 0
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if distances[neighbor] == -1:
distances[neighbor] = distances[current]+1
queue.append(neighbor)
result = []
for city in range(N+1):
if distances[city] == K:
result.append(city)
if result:
result.sort()
print('\n'.join(str, result)
else:
print(-1)일단은 너무 오래풀었으니 이정도로 만족하자
