본문 바로가기

BFS

 (4)
[Algorithm] [Python & Swift] 백준/BOJ - 1260 _ DFS와 BFS 1260 - DFS와 BFS INDEX INDEX ### 문제 설명 ### 입력 ### 출력 ### 예제 입출력 ### 제출 코드 ### 코드 설명 문제 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간..
[Python] BFS & DFS BFS & DFS BFS (Breath - First - Search)7u7jujjjuuujjjj from collections import deque # BFS (Breath - First - Search), 너비 우선 탐색 구현 graph = { # dictionary 'A': ['B'], 'B': ['A', 'C', 'H'], 'C': ['B', 'D'], 'D': ['C', 'E', 'G'], 'E': ['D', 'F'], 'F': ['E'],..
BFS Concept & Implementation BFS (Breath First Search) 1. 개념 파이썬 BFS 구현 큐를 사용하여 구현 아래와 같은 그래프 예시를 통한 BFS 시뮬레이션 출력 기존 입력 새로운 입력 ( 자손 ) A A B C D B C D E F C D E F G D E F G H I E F G H I F G H I J G H I J H I J I J K L J K L K L L 탐색 결과 : A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L 2. 구현 graph = { 'A' : set(['B', 'C', 'D']), 'B' : set(['A', 'E', 'F'..
BFS&DFS DFS & BFS 개념과 구현 탐색 알고리즘과 자료구조, 직관적으로 이해하기 DFS, BFS 등의 용어는 컴퓨터공학 계열 전공자 또는 개발 관련 공부를 진행해본 사람들이라면 한 번씩은 모두들 들어보았을 것이다. 들어보긴 들어봤으나, 그 개념과 구현은 생각보다 쉽지만은 않다. 이들을 탐색할 때 쓰이는 트리와 스택 또는 큐와 같은 자료구조까지 알아야 할 것들이 너무 많기도 할 뿐더러 이러한 알고리즘을 처음 접할때는 왜 stack queue등이 필요한지 잘 와닿지 않는다. 이것부터 알아보도록 하자! 자료구조가 왜 필요해? 한 예시를 들어보자. 어떠한 게임을 진행하면서 가능한 모든 경우의 수들을 생각해보고, 그 이후의 경우의 수도 모두 확인해보고자 할 때 우리는 기억에 용이함을 위하여 메모지에 메모 또는 머리속..

티스토리툴바