BFS

DFS & BFS

DFS(Depth First Search) • 깊이 우선 탐색 • 스택 or 재귀함수 이용 • 동작 과정 1. 탐색 시작 노드를 스택에 넣고 방문 처리 2. 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼냄 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 BFS(Breadth First Search) • 너비 우선 탐색 • 그래프에서 가까운 노드부터 우선적으로 탐색 • 큐 사용 • 특정 경로에서 최단거리 찾을 때 많이 사용 • 동작 과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리..

[1707] 이분 그래프(C++)

문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 내 코드 // [1707] 이분 그래프 // https://www.acmicpc.net/problem/1707 // 그래프, dfs, bfs #include #include #include #include using namespace std; vector list[200001]; int visited[200001], v; bool ans = true; void bipartite(int start) { queue q; visited[start] = 1; q...

[11725] 트리의 부모 찾기(C++)

문제 [11725] 트리의 부모 찾기 해결 방법 이 문제도 전형적인 dfs, bfs 문제이다. 한 가지, 현재 노드의 부모 노드가 몇번인지 저장할 배열만 추가하면 된다. 나는 인접리스를 활용한 dfs로 구현하였는데, 인접한 노드를 모두 입력받은 후 리스트의 형태는 아래와 같다. 노드 1 6 4 2 4 3 6 5 4 1 2 7 5 3 6 1 3 7 4 1번 노드부터 탐색을 시작하는데, 1번 노드와 연결된 노드는 무조건 1번 노드의 자식임을 알아두자. 또한, 나와 연결된 노드는 나의 부모이거나 자식이거나 둘중 하나임을 기억하자. 탐색을 하면서 나와 연결되어있지만 이미 방문한 노드는 부모노드이고, 그렇지 않은 노드는 부모 노드가 아니기에 자식노드로 판단하고 부모로 저장해주면 된다! 내 코드(C++) // [1..

그래프(BFS, DFS)

[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 내 코드(C / C++) Ver.1(C++) // [11724] 연결 요소의 개수 // https://www.acmicpc.net/problem/1260 #include #include #include #include #define MAX 1001 using namespace std; bool visit[MAX]; vectorlist[MAX]; void dfs(int start); int cc..

[2668] 숫자 고르기(C++)

🌿 문제 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래 www.acmicpc.net 🌿 해결 방법 directed graph에서 cycle의 개수와 cycle을 구성하는 노드를 찾는 문제이다. 이것도.... 한참 해보다가 결국 구글링을 하긴 했다.... dfs의 매개변수로 시..

[10451] 순열 사이클(C++)

문제 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 해결 방법 계속 런타임 에러가 떠서 for문이 너무 많은건가.... 변수형을 잘못 선언했나..... 한참을 찾아보고 질문도 올려보고 검색도 해봤는데 그냥 배열의 크기를 잘못 설정해서 그런거였다ㅋㅋ 문제에서 순열의 크기는 최소 2, 최대 1000 이라고 했는데 이걸 착각하고 배열의 크기는 1000-2+1해서 999면 충분하다고 생각했다. 왜 그랬지? 아무튼 그래프 정점의 시작 노드는 1번..

[1260] DFS와 BFS(C++)

문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 내 코드(C++) #include #include #include #include #define MAX 1001 using namespace std; bool visit[MAX]; vectorlist[MAX]; void dfs(int start); void bfs(int start); int main(void) { int N, M, V; cin ..