https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
실버 2. 백준 1260번 : DFS와 BFS
파이썬 풀이
코드
import sys
from collections import deque
input = sys.stdin.readline
n, m, v =map(int, input().split())
graph = [[] for _ in range(n+1)]
dfs_list = []
bfs_list = []
for _ in range(m): # 그래프 생성
i, j = map(int, input().split())
graph[i].append(j)
graph[j].append(i)
for i in range(len(graph)) : # 그래프 내부 정렬
graph[i] = sorted(graph[i])
def bfs(v) :
visited = [False]*(n+1)
queue = deque()
queue.append(v)
bfs_list.append(v)
while queue:
l = queue.popleft()
visited[l] = True
for k in graph[l] :
if visited[k] == False:
visited[k] = True
queue.append(k)
bfs_list.append(k)
visited_dfs = [False] * (n+1)
def dfs(v) :
visited_dfs[v] = True
dfs_list.append(v)
for i in graph[v] :
if not visited_dfs[i] :
dfs(i)
dfs(v)
print(*dfs_list)
bfs(v)
print(*bfs_list)
간단하게 dfs와 bfs 사용하면 돼서 풀이 생략!
이제는 dfs와 bfs 어느정도는 풀 수 있는 거 같아서 다행이다 물론 꼬아서 나오면 아직도 힘들지만...
처음에 헷갈렸던 부분은, 예전에 dfs 풀때 회귀를 너무 많이 하게 되면 메모리 초과.. 어쩌고 된다고 해서 처음에 풀 때부터
" sys.setrecursionlimit(10**7) "
이거 걸어두고 시작했었는데, limit이 너무 컸던 거 같다..^^ 이것때문에 오히려 메모리 초과가 났음. 삭제하고 나니까 되더라....
언젠가는 잘 하겠거니!!!!!!
https://github.com/eunnnju/24repo
GitHub - eunnnju/24repo
Contribute to eunnnju/24repo development by creating an account on GitHub.
github.com
깃허브도 놀러오세요~~ ^^
'알고리즘 > Python' 카테고리의 다른 글
[백준] python - 9020번: 골드바흐의 추측 (1) | 2024.02.03 |
---|---|
[백준] 파이썬 - 10819번 : 차이를 최대로 (1) | 2024.01.31 |
[백준] 파이썬 python - 1874번 : 스택 수열 (0) | 2023.12.24 |
[백준] 파이썬 python - 9095번 : 1, 2, 3 더하기 (0) | 2023.12.12 |
[백준] 파이썬 python - 1270번 : 전쟁 - 땅 따먹기 (1) | 2023.12.07 |