CS(Computer Science)지식71 백준 1991번: 트리 순회 (C++) https://www.acmicpc.net/problem/1991 풀이방법 해당 문제는 트리 탐색 방법 중에서 재귀를 활용한 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)를 코드로 구현하는 방법을 물어보는 문제다. 순회에 대한 3가지 개념을 이론적으로만 알고 있어도 특별히 어려움은 없으나, 문자열을 숫자로 변환해서 생각 하는게 조금, 아주조금 헷갈릴 수 있는 문제다. 허나 A=1이라는 가정하고 문제를 풀면 굉장히 쉽게 풀 수 있다. 해설 풀이는 아래와 같다. 코드 #include using namespace std; int p[100'005]; vector adj[100'005]; int n; void dfs.. 2024. 2. 2. 백준 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. 이전 1 ··· 6 7 8 9 10 11 12 ··· 18 다음