BFS2 [BOJ] 18352 특정 거리의 도시 찾기 - python 18352번: 특정 거리의 도시 찾기 (acmicpc.net) 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 시작 노드로부터 일정한 거리의 노드를 찾는 문제이다. 거리를 저장하는 부분에서 많은 시간이 걸렸다. 처음엔 방문 여부를 저장하는 visited와 거리를 저장하는 distance list를 따로 사용하였는데, 코드를 좀 더 간결하게 만들기 위해 visited_dis 하나로 통합하였다. 처음 제출에서는 리스트 형태의 큐를 사용하였더니.. 2022. 3. 30. [개념] BFS(Breadth-First Search) - python BFS(Breadth Fisrt Search)은 너비 우선 탐색이라는 뜻으로, 하나의 정점으로부터 가까운 노드부터 탐색하는 알고리즘이다. BFS는 그래프 탐색의 일종이다. 그래프 탐색? - 하나의 정점으로부터 시작하여 모든 정점을 한번씩 방문하는 것 직관적인 이해를 위해 먼저 트리를 대상으로 살펴보겠다. BFS는 너비 우선 탐색이라는 이름에 맞게 가로 노드들을 순서대로 방문한다. 1번 행을 모두 탐색하면 2번 행, 2번 행을 모두 탐색하면 3번행... 순서로 탐색을 이어나간다. 탐색 순서: A - B - C - D - E - F 이제는 무향 그래프에서 수행하는 BFS를 살펴보겠다. 해당 정점을 기준으로 탐색을 시작한다. 첫 번째로 방문한 노드와 인접한 노드들을 방문한다. 두 번째로 방문한 노드와 인접한 .. 2022. 3. 20. 이전 1 다음
