전체 글79 백준 15681번: 트리와 쿼리 (C++) https://www.acmicpc.net/problem/15681 풀이방법 해당 문제는 아래 설명되어있는 힌트를 토대로 문제를 해결하였다. 문제를 해결한 sequence는 다음과 같다. 우선 입력 받은 r값을 루트로 하는 트리를 구현한다. 이때 탐색하는 현재 노드의 자식 노드를 child변수를 이용하여 저장해 둔다. countSubtreeNodes함수를 사용하여 r기준으로 만들어지는 트리를 바탕으로 각 노드별로 만들 수 있는 서브 트리의 개수를 구하여 treeSize 배열 변수에 저장한다. 최종적으로 입력 받은 UTree를 treeSize배열 인덱스로 사용하여 원하는 출력 값을 얻어낸다. 코드 #include using namespace std; int n, r, q, u, v; vector adj[1.. 2024. 2. 2. 백준 4803번: 트리 (C++) https://www.acmicpc.net/problem/4803 풀이방법 개인적으로 문제를 푸는데 어려움이 있었다.. 첫 번째 이유는 문제가 잘 이해가 안 갔고, 두번째로 문제를 이해하고 나서 구현 방법 자체가 헷갈렸다. 첫 번째로 해당 문제를 이해하자면 n개의 정점으로 이루어진 그래프가 여러 개 존재하게 되는데 그 그래프 중에서 트리 형태의 그래프가 몇 개인지 맞추는 문제라고 볼 수 있다 이해가 안 가면 예시 입력을 바탕으로 그림을 그려보면 쉽게 이해가 갈 것이다. 두 번째로 구현 자체가 어려웠는데 bfs를 만들어서 풀 수 있다. 여기서 가장 중요한 포인트는 아래 코드 중에서 bfs함수 안쪽을 보면 if (nxt == prev) continue;의 의미는 bfs탐색 할 때 트리 같은 경우는 루트부터 .. 2024. 2. 2. 백준 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. 백준 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. 백준 11724번: 연결 요소의 개수 https://www.acmicpc.net/problem/11724 해당 문제는 그래프의 개념과 BFS를 동시에 물어보는 가장 기초적이고 핵심적인 문제이며 코드 구성을 외우고 이해할 필요가 있는 문제이다. 코드는 아래와 같다. #include using namespace std; int n, m; vector adj[1005]; bool vis[1005]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i > u >> v; adj[u].push_back(v); adj[v].push_back(u); } int num = 0; for (int i = 1; i 2024. 2. 2. 이전 1 2 3 4 5 6 7 8 ··· 10 다음