승코딩당당당

문제[C++] 백준 1707: 이분 그래프 GOLD 4https://www.acmicpc.net/problem/1707 접근 방법이 문제는 주어진 그래프가 이분 그래프인지 판별하는 문제이다.이분 그래프란, 정점을 두 개의 집합으로 나누었을 때 같은 집합 내에서는 간선이 존재하지 않는 그래프를 의미한다.이를 해결하기 위해 그래프를 탐색하면서 각 정점을 두 가지 색(0, 1)으로 칠하는 방식을 사용한다.인접한 두 정점은 반드시 서로 다른 색이어야 함만약 같은 색이 되면 → 이분 그래프 아님그래프는 여러 개의 연결 요소로 나뉠 수 있으므로, 모든 정점을 시작점으로 탐색을 수행해야 한다.탐색 방법은 DFS를 사용하였다. 상세 아이디어1. 그래프 구성 vector> graph; 인접 리스트 형태로 그래프를 구성..

문제[C++] 백준 1325: 효율적인 해킹 SILVER 1https://www.acmicpc.net/problem/1325 접근 방법백준 1325번은 효율적인 해킹 문제로,어떤 컴퓨터를 해킹했을 때 가장 많은 컴퓨터를 해킹할 수 있는 시작 노드를 찾는 문제다. 핵심 포인트는 다음이다.A → B 라는 관계는A를 해킹하면 B도 해킹할 수 있다는 의미가 아니라B를 해킹하면 A를 해킹할 수 있다는 의미다. 그래서 그래프를 그대로 저장하면 안 되고, 간선 방향을 반대로 저장해야 한다.이렇게 하면 “어떤 노드에서 시작했을 때 도달 가능한 모든 노드”를 DFS로 쉽게 탐색할 수 있다.graph[b].push_back(a); 상세 아이디어1. 그래프 구성graph[b].push_back(a)→ b를 해킹하면 a를 ..

문제[C++] 백준 1033: 칵테일 GOLD 2https://www.acmicpc.net/problem/1033 접근 방법백준 1033번은 재료들 사이의 비율 정보가 주어졌을 때,모든 재료의 양을 가장 작은 정수 비율로 구하는 문제다. 예를 들어 A와 B의 비율이 2:3 이라면,A의 양이 2일 때 B의 양은 3이 되고, A의 양이 4일 때 B의 양은 6이 되는 식으로 비율만 만족하면 여러 경우가 가능하다. 하지만 이 문제에서는 모든 재료의 양을 정수로 표현하면서, 동시에 더 이상 줄일 수 없는 최소 형태로 출력해야 한다.이 문제는 재료들을 정점, 비율 관계를 간선으로 생각해서 그래프 형태로 접근할 수 있다. 상세 아이디입력으로 주어지는 a, b, p, q는 다음 의미를 가진다.a : b = p : q..

문제[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는 “깊게..