DFS
[백준/BOJ]#13565:침투[DFS/그래프/깊이우선탐색/파이썬/python]
https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 메모리 초과의 늪에서 못 빠져나오게 한 문제,,, 대체 코드에 문제가 없는데 왜 이러는건가 재귀탐색제한을 줄여도 보고 30분을 헤매었는데,, 결국 컴파일러를 pypy3가 아닌 python3 으로 바꾸니 통과했다;;; 백준에서 이런 경우가 간혹 있는데 이럴때마다 시간이 아깝고 힘 빠진다^^;; 승부는 내야하니 정답은 내야겠고,, bfs보다는 dfs로 푸는 게 더 ..
[백준/BOJ] #1967: 트리의 지름 [트리/BFS/python/파이썬]
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #1967_트리의 지름 from collections import deque n = int(input()) tree = [[] for _ in range(n+1)] for _ in range(1,n): parent, child, weight = map(int, input().split()) tree[parent].append([weight, child]) tree[child]...
[백준/알고리즘] #16953: A → B [파이썬(python)/그래프/DFS]
https://www.acmicpc.net/problem/16953 #16953_A->B from collections import deque A, B= map(int, input().split()) def dfs(x,y): q=deque([(x,y)]) while q: num, cnt = q.popleft() if num == B: return cnt if num * 2
[백준/boj/알고리즘/파이썬(python)/C++/DFS]#11724:연결요소의 개수
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 그래프이론_너비우선탐색, 깊이우선탐색 BFS DFS 문제 나는 DFS를 이용하여 풀었다. (BFS까지 나중에 풀어봐야지!) 파이썬 코드에서 계속 시간초과가 나서 그 원인을 보니 input() 이었다. 백준에서는 input()함수가 시간초과가 잘 난다고 하니 참고하시길..! sys 라이브러리 import해서 입출력하면 해결된다. 그리고 ..