18352

2023년 8월 12일 알고리즘 문제풀이 문제 1 백준 18352 문제 링크 1차 시도 나의 생각 도시까지의 최단거리만 생각해야 하므로, bfs를 통해 도착한 도시에 얼마나 걸렸는지를 표시하고, 이를 방문표시로 이용하면 되겠다는 생각을 했다. 출발한 도시 와 도착지가 같을때는 0으로 표시하게 되는데, 이것 때문에 아직 방문처리하지 않은 것으로 취급되어 여러가지로 헷갈렸다. 따라서 제자리 거리를 1로 표시하여 모든 도시의 거리를 구하고 모두 1 만큼 감소시켜주었다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import sys from collections import deque n, m, k, x = map(int, sys.stdin.readline().split()) graph = [[]for _ in range(n+1)] for _ in range(m): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) ans = [] visited = [0 for _ in range(n+1)] def bfs(s): visited[s] = 1 arr = deque() arr.append(s) while arr: now = arr.popleft() for next in graph[now]: if not visited[next]: arr.append(next) visited[next] = visited[now]+1 bfs(x) ans = [] if k == 0: print(x) else: for i in range(1, n+1): visited[i] -= 1 if i == x: continue if visited[i] == k: print(i) ans.append(i) if not ans: print(-1) 문제 2 백준 2178 문제 링크 ...

1.개발 진행 및 완료상황 2주차 python algorithm bfs 문제 풀이 중 CSAPP 2주차 목표 읽기 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 18352 18352번: 특정 거리의 도시 찾기 문제 어떤 나라에는 1번부터 N 번까지의 도시와 M 개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X 로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K 인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X 에서 출발 도시 X 로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N =4, K =2, X =1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4… ...