승코딩당당당

문제[C++] 백준 1167: 트리의 지름 GOLD 2https://www.acmicpc.net/problem/1167 접근 방법백준 1167번은 가중치가 있는 트리의 지름(가장 긴 경로의 길이) 을 구하는 문제이다.이 문제의 핵심 아이디어는 다음과 같다. 임의의 노드에서 가장 먼 노드는, 트리 지름을 이루는 두 노드(양 끝점) 중 하나이다.(즉, 한 번 멀리 찍고 → 그 점에서 다시 가장 멀리 찍으면 지름이 나온다.)그래서 BFS를 두 번 사용했다.임의의 노드(코드에서는 1번)에서 BFS → 가장 먼 노드 M_index 찾기M_index에서 다시 BFS → 최댓값이 트리의 지름 상세 아이디어1) 트리 저장 방식tree[node]에 (connect, value) 형태로 인접 리스트를 저장해 가중치 간선..

문제[C++] 백준 2178: 미로 탐색 SILVER 1https://www.acmicpc.net/problem/2178 접근 방법이 문제는 미로에서 시작점 (0, 0)부터 도착점 (N-1, M-1)까지 이동할 때 지나야 하는 최소 칸 수를 구하는 문제이다.각 칸은 이동 가능(1) 또는 불가능(0)으로 주어지며, 상하좌우로만 이동할 수 있다. 큐에는 현재 위치 (0, 0)를 넣고, 이동 가능한 다음 칸으로 확장하면서 방문 처리와 함께 maze 배열에 (0, 0)이전 칸 값 + 1을 저장해 거리 정보를 누적한다.최단 거리를 구해야 하므로 BFS(너비 우선 탐색) 를 사용한다.DFS보다 BFS가 적합한 이유는 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문이다. BFS는..

그래프 문제를 풀다 보면 깊이 우선 탐색(DFS)와 함께 반드시 등장하는 탐색 알고리즘이 너비 우선 탐색(BFS)이다.BFS 역시 그래프의 모든 노드를 빠짐없이 방문하기 위한 완전 탐색 알고리즘 중 하나로, 시작 노드를 기준으로 가까운 노드부터 차례대로 탐색하는 방식이 특징이다.이번 글에서는 BFS의 개념과 특징, 구현 방식, 시간 복잡도, 그리고 DFS와 다른 점까지 간단히 정리해보려고 한다. ✍️ DFS 관련 내용은 다음 링크를 참고하면 좋습니다!https://xeungcoding.tistory.com/25 DFS(depth-first search) 깊이 우선 탐색그래프 문제를 풀다 보면 가장 먼저 접하게 되는 탐색 알고리즘이 깊이 우선 탐색(DFS)이다.DFS는 그래프의 모든 노드를 빠짐없이 방문하..

그래프 문제를 풀다 보면 가장 먼저 접하게 되는 탐색 알고리즘이 깊이 우선 탐색(DFS)이다.DFS는 그래프의 모든 노드를 빠짐없이 방문하기 위한 완전 탐색 기법 중 하나로, 구현이 비교적 직관적이어서 알고리즘 입문 단계에서 자주 사용된다.이번 글에서는 DFS의 개념, 특징, 시간 복잡도, 그리고 어떤 문제들에 활용되는지까지 간단히 정리해보려고 한다. ✍️ 깊이 우선 탐색이란?그래프의 시작 노드에서 출발하여 한 방향으로 끝까지 깊게 탐색한 뒤,더 이상 갈 곳이 없으면 이전 분기점으로 돌아가 다른 경로를 탐색하는 방식의 알고리즘이다. 즉,한 노드를 방문하면그 노드와 연결된 노드 중 하나를 선택해최대 깊이까지 탐색을 먼저 수행하고이후 다른 분기를 차례로 탐색한다.이러한 동작 방식 때문에 DFS는 “깊게..

문제[C++] 백준 13023: ABCDE GOLD 5https://www.acmicpc.net/problem/13023 접근 방법이 문제는 사람 관계가 주어졌을 때, 서로 연속으로 연결된 5명(A–B–C–D–E) 이 존재하는지를 판단하는 문제이다.처음에 이 부분을 이해 못 해서 헤맸다;;즉, 그래프에서 길이 4의 경로(간선)가 하나라도 있으면 1, 없으면 0을 출력한다. 무방향 그래프이므로 친구 관계 (a, b)는 양방향으로 저장한다.각 정점을 시작점으로 삼아 DFS를 수행하면서,현재까지 연결된 사람 수(cnt)가 4가 되는 순간 4개의 조건을 만족한 것이므로 탐색을 종료한다. 간선이 4개 = 노드가 5개 → 조건 만족if (cnt == 4) // 4가지 조건 모두 만족 시{ flag = true;..

문제[C++] 백준 2023: 신기한 소수 GOLD 5https://www.acmicpc.net/problem/2023 접근 방법이 문제는 N자리 소수를 찾는 문제이다. 완성된 N자리 수가 소수여야 할 뿐만 아니라, 앞에서부터 잘라 만든 모든 자리 수가 전부 소수여야 한다.즉,4자리 수라면 👉 1자리 → 2자리 → 3자리 → 4자리모든 단계에서 소수 검사를 통과해야 한다.그래서 단순히 N자리 수를 전부 만들고 검사하는 방식이 아니라,자리수를 하나씩 늘려가며(DFS) 매 단계마다 소수인지 확인하고 진행하는 방식으로 풀었다. 1자리에서 시작 가능한 소수는 2, 3, 5, 7뿐이라 이 값들로 DFS를 시작한다.다음 자리로 확장할 때는 짝수나 5로 끝나면 소수가 될 수 없으므로, 뒤에 붙일 숫자를 1, 3,..

문제[C++] 백준 11724: 연결 요소의 개수 SILVER 2https://www.acmicpc.net/problem/11724 접근 방법이 문제는 정점과 간선이 주어졌을 때, 그래프의 연결 요소(Connected Component) 개수를 구하는 문제이다.그래프는 무방향 그래프이므로 간선 (u, v)가 주어지면 u ↔ v 양방향으로 연결한다.인접 리스트(vect)로 그래프를 구성하고, visited 배열로 방문 여부를 관리한다.아직 방문하지 않은 정점을 하나 선택해 DFS를 수행하면, 해당 DFS가 끝날 때까지 방문한 정점들은 모두 같은 연결 요소에 속한다.따라서 DFS를 한 번 시작할 때마다 연결 요소의 개수를 1 증가시키면 된다. 구현 시 주의할 점정점 번호가 1부터 n까지이므로, 인접 리스트..