코딩 테스트24 백준 11725번: 트리의 부모 찾기 (C++) 링크 https://www.acmicpc.net/problem/11725 풀이방법 해당 문제는 dfs를 이용하여 완전 탐색과, p라는 배열을 만들어서 p[i]=j i의 부모는 j라는 의미를 사용하여 문제를 해결 할 수 있다. 코드 #include using namespace std; int p[100'005]; vector adj[100'005]; int n; void dfs(int cur) { for (auto nxt : adj[cur]) { if (p[cur] == nxt) continue; p[nxt] = cur; dfs(nxt); } } int main() { cin >> n; for (int i = 0; i > u >> v; adj[u].p.. 2024. 2. 2. 백준 11403번: 경로 찾기 (C++) 링크 https://www.acmicpc.net/problem/11403 풀이방법 해당 문제는 BFS를 응용하여 다음과 같은 스텝으로 문제를 해결하였다. 우선 양방향 그래프가 아니고 특정 방향으로만 이동할 수 있는 방향 그래프이기 때문에 adj vector 배열 변수에 입력되는 순서로만 값을 대입하였다. 문제에서 i에서 간선을 따라 갔을 때 j까지 갈 수 있으면 1을 출력하고 아니면 0을 출력하라고 했으므로 i에서 bfs를 시작해서 이동하다가 j를 만나는 순간 for문과 while문을 탈출하고 출력용 배열인 board에 1을 넣어준다. 최종적으로 board 배열을 출력한다. 위 설명의 흐름대로 코드를 보면 무슨 말인지 이해할 수 있을것이다. 코드 #include using namespace std; in.. 2024. 2. 2. 백준 5667번: 결혼식 (C++) 링크 https://www.acmicpc.net/problem/5567 풀이방법 해당 문제는 BFS를 응용하여 시작 지점부터 거리를 측정하여, 시작 지점인 1로부터 거리가 1. 2인 값들만 찾아내서 개수를 세면 쉽게 풀 수 있는 문제다. 풀이 코드는 아래와 같다. 코드 #include using namespace std; int n, m; vector adj[505]; int vis[505]; int ans; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; int u, v; for (int i = 0; i > u >> v; adj[u].push_back(v); adj[v].push_back(u); }.. 2024. 2. 2. 백준 1260번: DFS와 BFS (C++) 링크 https://www.acmicpc.net/problem/1260 풀이방법 해당 문제는 그래프 관련 dfs와 bfs 기초적인 사용법을 묻는 문제로 기본적인 dfs, bfs지식만 가지면 풀 수 있다 하지만 문제에서 말하는 세 가지 조건을 유의해서 코드를 작성해야한다. 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 탐색을 시작할 정점의 번호 V가 주어진다. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 코드 #include using namespace std; int n, m; vector adj[1005]; bool vis[1005]; int v; void bfs(int v) { queue q; q.push(.. 2024. 2. 2. 이전 1 2 3 4 5 6 다음