BFS

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 사용한 알고리즘 : BFS, 트리구조 풀이전략 1. 주이진 입력을 BFS를 사용하여 트리로 만든다. 2. BFS로 탐색 중, 특정 노드의 부모 노드를 저장해둔다. 3. 저장해뒀던 부모 노드들을 출력한다. 제출코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 사용한 알고리즘: BFS 풀이전략 문제를 풀기 앞서 이분 그래프가 어떤 구조인지 알고 있어야 문제 풀이가 가능하다. 위와 같은 그래프가 있을 때, 인접한 노드끼리 서로 다른 색을 지니는 그래프를 이분 그래프라고 한다. 노드끼리 모두 연결되어 있지 않아도, 서로 인접한 노드끼리만 다른 색으로 구분될 수 있어도 이분그래프다. 이런 이분 그래프의 성질을 이용하여 BFS를 사용하면 문제를 풀 수 있..

https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net import sys from collections import deque n,m,r=map(int,sys.stdin.readline().split()) graph=[[] for _ in range(n+1)] visited=[0 for _ in range(n+1)] def bfs(start): cnt=1 visited[sta..