99클럽 코테 스터디 8일차 TIL - DFS&BFS (백준2644- 촌수계산)
반응형
https://www.acmicpc.net/problem/2644
- 오늘의 학습 키워드 : DFS & BFS
- 공부한 내용
예제1
예제2
- DFS로 푼 경우
import sys # 입력 처리 n = int(sys.stdin.readline().strip()) # 총 사람의 수 a, b = map(int, sys.stdin.readline().strip().split()) # 촌수를 계산할 두 사람 m = int(sys.stdin.readline().strip()) # 관계의 수 graph = [[] for _ in range(n + 1)] # 각 사람의 관계를 나타내는 인접 리스트 # 관계 정보 입력 for i in range(m): x, y = map(int, sys.stdin.readline().strip().split()) graph[x].append(y) graph[y].append(x) # 무향 그래프이므로 양쪽 모두 연결 # 방문 배열 초기화 (-1은 방문하지 않았음을 의미) visited = [-1] * (n + 1) visited[a] = 0 # 시작 노드는 거리 0으로 설정 # DFS 함수 정의 def dfs(start, graph, visited): for i in graph[start]: # 현재 노드에 연결된 모든 노드를 순회 if visited[i] == -1: # 방문하지 않은 노드라면 visited[i] = visited[start] + 1 # 현재 노드까지의 거리 +1로 설정 dfs(i, graph, visited) # 재귀적으로 DFS 수행 # DFS 실행 dfs(a, graph, visited) # 결과 출력: 목표 노드까지의 거리 출력 (연결되지 않았으면 -1) print(visited[b])
- BFS로 푼 경우
import sys from collections import deque # 입력 처리 n = int(sys.stdin.readline().strip()) # 총 사람의 수 a, b = map(int, sys.stdin.readline().strip().split()) # 촌수를 계산할 두 사람 m = int(sys.stdin.readline().strip()) # 관계의 수 graph = [[] for _ in range(n + 1)] # 각 사람의 관계를 나타내는 인접 리스트 # 관계 정보 입력 for i in range(m): x, y = map(int, sys.stdin.readline().strip().split()) graph[x].append(y) graph[y].append(x) # 무향 그래프이므로 양쪽 모두 연결 # BFS 함수 정의 def bfs(start, graph, end): visited = [-1] * (n + 1) # 방문 배열: 방문하지 않은 노드는 -1 queue = deque([start]) # 탐색을 시작할 노드를 큐에 추가 visited[start] = 0 # 시작 노드는 거리 0으로 초기화 # 큐가 빌 때까지 반복 while queue: node = queue.popleft() # 큐의 첫 번째 노드를 꺼냄 # 현재 노드와 연결된 노드를 탐색 for i in graph[node]: if visited[i] == -1: # 아직 방문하지 않은 노드일 경우 visited[i] = visited[node] + 1 # 부모 노드 거리 +1 queue.append(i) # 큐에 추가하여 다음 탐색에 사용 return visited[end] # 목표 노드의 거리 반환 (방문하지 않았으면 -1 반환) # BFS 실행 및 결과 출력 print(bfs(a, graph, b))
- DFS로 푼 경우
- 오늘의 회고
- 이건.. 전형적인 dfs, bfs 문제여서 생각보다 쉽게 끝나서 약간 좀 허무해서 이거 정리하고.. 챌린저 문제를 한번 더 풀어볼까 한다.
- 오늘은 다른 공부는 하기 싫으니깐,, DFS BFS만 풀었다는 것에 만족하고 챌린저 끄적이러 간다 🫠
- ㅎㅎ.. 챌린저 문제 설명 : https://coooco.tistory.com/190
반응형
'Python > 😈 99클럽 코테 스터디 4기 TIL' 카테고리의 다른 글
99클럽 코테 스터디 13일차 TIL - 그리디,이분탐색 (백준27961 - 고양이는 많을수록 좋다) (0) | 2024.11.09 |
---|---|
99클럽 코테 스터디 12일차 TIL - BFS (백준7569- 토마토) (0) | 2024.11.08 |
99클럽 코테 스터디 7일차 TIL - (프로그래머스 - 모음사전) (3) | 2024.11.03 |
99클럽 코테 스터디 6일차 TIL - BFS (백준 2458번 - 키 순서) (0) | 2024.11.03 |
99클럽 코테 스터디 4일차 python TIL - 이분탐색(백준2512 예산) (0) | 2024.11.01 |