승코딩당당당

문제[C++] 백준 2606: 바이러스 SILVER 3https://www.acmicpc.net/problem/2606 접근 방법백준 2606번은 컴퓨터 바이러스 문제로,1번 컴퓨터가 바이러스에 감염되었을 때 연결된 다른 컴퓨터가 몇 대 감염되는지 구하는 문제다. 컴퓨터들이 네트워크로 연결되어 있기 때문에, 이를 그래프 탐색 문제로 볼 수 있다.문제의 핵심은 다음과 같다.컴퓨터 = 노드네트워크 연결 = 간선따라서 그래프 탐색(DFS 또는 BFS) 을 이용해서 1번 컴퓨터에서 시작하여 연결된 모든 컴퓨터를 방문하면 된다. 이번 풀이에서는 DFS(Depth First Search) 를 사용했다.먼저 그래프를 인접 리스트 형태로 저장한다.vector> graph;그리고 방문 여부를 확인하기 위해 배열을 사용..

문제[C++] 백준 11725: 트리의 부모 찾기 SILVER 2https://www.acmicpc.net/problem/11725 접근 방법이 문제는 루트가 1번인 트리가 주어졌을 때, 각 노드의 부모를 출력하는 문제다. 트리는 사이클이 없는 연결 그래프이기 때문에,1번 노드를 기준으로 DFS를 한 번만 돌면서 부모를 기록해주면 해결된다. 구현 아이디어는 간단하다:graph : 인접 리스트 (양방향 그래프)ret[i] : i번 노드의 부모 노드 번호visited[i] : 방문 체크DFS에서void dfs(int before, int now){ visited[now] = true; ret[now] = before; // now의 부모는 before for (int i = 0; i 이렇게..

문제[C++] 백준 21736: 헌내기는 친구가 필요해 SILVER 2https://www.acmicpc.net/problem/21736 접근 방법이 문제는 캠퍼스 지도가 주어졌을 때, 도연이(I)가 있는 위치에서 출발하여 벽(X)을 제외한 모든 경로를 탐색하면서 사람(P)의 수를 세는 문제다. 캠퍼스는 2차원 격자 형태이므로, 상·하·좌·우로 이동하면서 탐색하는 그래프 탐색 문제로 볼 수 있고,한 번 방문한 곳을 다시 방문하지 않기 위해 visited 배열을 사용한 DFS(깊이 우선 탐색) 로 해결했다. 풀이 흐름은 다음과 같다.캠퍼스 정보를 2차원 배열에 저장하면서, 도연이의 시작 위치(I)를 찾는다.시작 위치에서 DFS를 시작한다.이동할 수 있는 조건은캠퍼스 범위 안에 있고아직 방문하지 않았으며벽..

문제[C++] 백준 2468: 안전 영역 SILVER 1https://www.acmicpc.net/problem/2468 접근 방법비의 높이(rain)가 주어졌을 때, 잠기지 않은 영역(안전 영역)의 개수를 세고, 그 개수의 최댓값을 구하는 문제다.핵심은 비의 높이가 바뀔 때마다 지도에서높이 > rain 인 칸들만 “살아있는 땅”으로 보고상하좌우로 연결된 덩어리(연결 요소)의 개수를 DFS/BFS로 세는 것이다.그래서 rain을 0부터 (지도 최대 높이 - 1)까지 변화시키며 매번 탐색하고,각 rain에 대한 안전 영역 개수 중 최댓값을 ret에 저장한다. 구현 시 주의할 점visited 초기화는 매 rain마다 반드시 해줘야 한다. (이전 rain 탐색 흔적이 남으면 오답)탐색 조건은 vect[yy]..

문제[C++] 백준 2331: 반복수열 SILVER 4https://www.acmicpc.net/problem/2331 접근 방법이 문제는 수열을 생성하다가 중복이 처음 발생하는 지점 이전까지의 원소 개수를 구하는 문제이다.수열은 다음 규칙으로 만들어진다.현재 수의 각 자릿수를 P제곱한 값들을 모두 더해 다음 수를 만든다. 이를 구현하기 위해시작 값 a를 벡터 d에 넣고value() 함수를 이용해 다음 값을 계속 생성한다.이미 나온 값인지 빠르게 확인하기 위해 boolean 배열(check) 로 방문 여부를 관리한다.처음으로 중복이 발생하면 수열 생성을 멈춘다.중복된 값이 처음 등장했던 위치를 찾아, 그 인덱스가 곧 정답이 된다. 구현 시 주의할 점자릿수 계산은 % 10과 / 10을 이용해 하나씩 분리..

문제[C++] 백준 10451: 순열 사이클 SILVER 3https://www.acmicpc.net/problem/10451 접근 방법이 문제는 순열이 주어졌을 때, 그 순열에 포함된 사이클의 개수를 구하는 문제이다.각 숫자는 정확히 하나의 숫자를 가리키므로, 전체 구조는 방향 그래프이며 각 연결 요소는 반드시 하나의 사이클을 포함한다. 그래프를 graph[i] = 다음 정점 형태로 저장한 뒤,아직 방문하지 않은 정점에서 DFS를 시작하면 하나의 사이클을 전부 탐색할 수 있다.따라서 DFS를 한 번 시작할 때마다 사이클의 개수를 1 증가시키면 된다. (cnt++) 구현 시 주의할 점이 문제는 일반 그래프가 아니라 순열 그래프이므로,한 정점에서 갈 수 있는 다음 정점이 항상 하나뿐이라는 점을 이용하면 ..

그래프 문제를 풀다 보면 가장 먼저 접하게 되는 탐색 알고리즘이 깊이 우선 탐색(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까지이므로, 인접 리스트..