알고리즘/BFS&DFS (6) 썸네일형 리스트형 백준 24479 시간초과 해결 (DFS) import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline def dfs(graph, v, visited): global cnt visited[v] = cnt for i in sorted(graph[v]): if visited[i] == 0: cnt += 1 dfs(graph, i, visited) n, m, r = map(int, input().split()) graph = [[] for _ in range(n + 1)] visited = [0] * (n + 1) cnt = 1 for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) d.. 백준 11725 트리의 부모 찾기 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n = int(input()) graph = [[] for _ in range(n + 1)] for _ in range(n - 1): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) visited = [0] * (n + 1) #부모 노드를 담을 리스트 def dfs(root): for i in graph[root]: if visited[i] == 0: visited[i] = root dfs(i) dfs(1) for i in range(2, n + 1): print(visited[i]) 백준 16953 (bfs) from collections import deque a, b = map(int, input().split()) q = deque([(a, 1)]) while q: now, cnt = q.popleft() if now == b: print(cnt) break if now * 2 b로 풀어가면 된다. 큐에 a값과 연산횟수값(처음1)을 넣어주고 시작한다. popleft()로 큐의 값이 있을 때 빼주어 현재값을 now에, 연산횟수를 cnt에 저장한다. now값과 b값을 비교하며 b값과 같으면 바로 연산횟수cnt를 출력하고 종료. 아니면, now값에 2를 곱한 값 또는 뒤에 1을 붙인 값(now * 10 + 1)이 b와 같거나 작을 때 큐에 넣어준다. (cnt값 + 1) 그렇게 now값이 b값과 같아질 때까지 .. 백준11724 *bfs풀이 from collections import deque def bfs(graph, start, visited): q = deque([start]) visited[start] = True while q: v = q.popleft() for i in graph[v]: if not visited[i]: visited[i] = True q.append(i) n, m = map(int, input().split()) graph = [[] for _ in range(n + 1)] visited = [False] * (n + 1) cnt = 0 for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) f.. [BFS&DFS기본] 백준1260번 (Python) *DFS(깊이 우선 탐색) #BFS(너비 우선 탐색) 백준 1260. [DFS와 BFS]문제 *DFS: 인접한 노드 중 시작점 V부터 숫자가 작은 노드부터 방문하고, 이미 방문했다면 다시 돌아가 인접 노드를 찾는다. *BFS: 1) 1번 노드 방문 후 큐에 삽입 2) 가장 앞에 있는 노드1을 pop 후, 인접 노드 2,3,4를 한꺼번에 q에 append 3) 가장 앞에 있는 노드2를 pop 후, 인접 노드 모두 방문처리 했으므로 append하지 않음 4) 가장 앞에 있는 노드3를 pop 후, 인접 노드 모두 방문처리 했으므로 append하지 않음 5) 가장 앞에 있는 노드4를 pop 후, 인접 노드 모두 방문처리 했으므로 append하지 않음 6) q는 공백이 되고 종료. from collections .. 백준 2644(촌수 계산) -BFS 무려 4번째에 맞게 된 문제라 기록하고 싶어서 게시 ㅎㅎ 처음엔 단순하게 부모 자식 관계를 노드-간선으로 보고 bfs로 풀어 cnt 로 값을 반환해주려고 했으나, cnt로 값을 올리면 같은 거리의 (자식 관계) 값이 달라지게 된다. 따라서 테스트케이스에서는 정답이 나왔으나 백준에서 탈락을 한 것이다.... 무엇이 문제일까? 아무리 생각해봐도 답이 안나온다.. 더욱이 테케는 통과되기 때문에... 그래서 도움을 요청했다. 이 문제는 다른 개념으로 봐야한다. distance라는 배열이 나온다! 시작하는 노드의 distance는 무조건 0. 부모 노드에 포함되는 자식노드의 distance는 부모 노드의 distance값에서 1을 더한 값으로 모두 동일하게 들어간다. cnt로 계산하면 같은 자식이지만, 2, 3 .. 이전 1 다음
