728x90 Baekjoon/[Code.plus] 알고리즘 기초 2／261 [BOJ/백준] 1707 이분 그래프 ● [문제번호 1707] 이분 그래프 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ● 알아야 할 것 : vector 자료구조와 메소드 : BFS 넓이 우선 탐색 : DFS 깊이 우선 탐색 (재귀, 비재귀) ● 풀이 과정 : 문제에서 설명하는 이분그래프가 무엇인지 이해가 바로 되지 않아서 알아보니 그래프를 2가지 집합으로 나누는데 각 정점(기준)에 연결된 정점들은 정점(기준)과 다른 집합으로 나뉘는 것이다. 쉽게 이해하자면 두 집합을 빨강(1.. 2021. 9. 13. [BOJ/백준] 11724 연결 요소의 개수 ● [문제번호 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 : vector 자료구조와 메소드 ● 풀이 과정 : 다음 조건을 만족하면 연결 요소가 될 수 있다. (참고) 조건 1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다. 조건 2. 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된.. 2021. 9. 13. [BOJ/백준] 1260 DFS와 BFS ● [문제번호 1260] DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ● 알아야 할 것 : DFS(재귀, 비재귀), BFS : vector 자료구조와 메소드 : stack 자료구조와 메소드 : queue 자료구조와 메소드 ● 풀이 과정 : 아래 코드는 구현방법3 을 적용했다. (코드는 구현방법1, 2, 3 모두 있다) 구현방법1 (오름차순 → DFS 선택1 → 방문기록 초기화 → BFS).. 2021. 9. 13. [BOJ/백준] 13023 ABCDE ● [문제번호 13023] ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net ● 알아야 할 것 : 그래프 : DFS : 재귀 ● 풀이 과정 : 앞서 풀었던 DFS와 비슷하지만, 그래프에 적용하여 구현된 DFS이다. : 문제를 이해하기 조금 헷갈릴 수 있는데 이해한 바로는 주어진 친구 관계도에서 5명을 한번에 이어질 수 있는가 를 확인하면 된다. : BFS보다 DFS를 이용하여 구현해야겠다는 생각이 들었다. DFS는 재귀와 반복문을 이용하여 구현할 수 있는데 반복문으로 계속 시도하려다 친구 관계 5명을 확인하는 부분이 복잡하게 구현될 것 같아.. 2021. 9. 13. 이전 1 ··· 3 4 5 6 7 8 9 ··· 16 다음 728x90
