dfs
-
[백준 1260번] BFS, DFSData Engineering/알고리즘 - Python 2021. 6. 29. 15:46
[백준 1260번] DFS와 BFS] https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net (정답) 처음 해보는 문제라서 많이 어려워서 다른 답들을 참고했다. n,m,v=map(int,input().split()) mat=[[0]*(n+1) for _ in range(n+1)] visit=[0]*(n+1) for i in range(m): x,y=map(int, input().split()) mat[x][y]=m..
-
BFS, DFSData Engineering/알고리즘 - Python 2021. 6. 29. 11:26
완전 탐색 기법 중에는 BFS/DFS 알고리즘이 있다. 코딩 테스트 문제에서 자주 만나게 되는 알고리즘 카테고리이다. 그렇기 때문에 문제를 풀기 전에 개념을 세우는 것이 가장 중요하다. 개념을 공부하기 전에 그래프/트리, 스택/큐 자료구조에 대해 알고 가자. 📍그래프란? : 정점(Node)와 정점을 연결하는 간선(Edge)로 이루어진 자료구조 : 순환 싸이클이 있을 수도 있고, 없을 수도 있다. ◾정점: A, B, C, D, E ◾간선: 정점을 이어주는 선(왼쪽의 경우 6개의 간선으로 이루어짐) 📍트리란? : 순환 싸이클이 없는 그래프를 의미한다. 📍스택이란? : 데이터를 기록하는 구조이다. → LIFO(Last Input First Out) → push: 가장 먼저 입력된 데이터가 가장 밑에 쌓인다. ..