승코딩당당당

문제[C++] 백준 2251: 물통 GOLD 4https://www.acmicpc.net/problem/2251 접근 방법이 문제의 핵심은 상태를 그래프로 보고 BFS로 탐색하는 문제이다.각 물통의 상태를 하나의 노드로 보고, 물을 옮기는 행위를 간선으로 생각하면 된다. 처음에는 세 물통 A, B, C의 상태 (A, B, C)를 모두 고려해야 할 것 같지만,전체 물의 양이 항상 일정하기 때문에 다음과 같이 단순화할 수 있다.전체 물의 양 = 항상 C의 초기값따라서 C = 전체 - A - B로 계산 가능즉, (A, B)만 알면 상태를 완전히 표현할 수 있기 때문에 visited[A][B] 형태로 방문 체크를 진행한다.탐색은 BFS를 사용하여 가능한 모든 상태를 순회하며, 그 중에서 A가 0인 상태일 때의..

문제[C++] 백준 18352: 특정 거리의 도시 찾기 SILVER 2https://www.acmicpc.net/problem/18352 접근 방법백준 18352번은 특정 거리의 도시 찾기 문제로,시작 도시 X에서 출발했을 때 최단 거리가 정확히 K인 도시들을 모두 출력하는 문제다. 모든 도로의 거리가 1로 동일하기 때문에, 이 문제는 가중치가 없는 그래프에서의 최단 거리 탐색 문제로 볼 수 있다.이런 경우에는 BFS(너비 우선 탐색) 를 사용하면 된다. 그래프는 인접 리스트로 저장했다.vector> graph; 그리고 각 도시까지의 거리를 저장하기 위해 dist 배열을 사용했다.vector dist; 초기에는 모든 도시의 거리를 -1로 설정해두고,BFS를 하면서 처음 방문한 도시의 거리를 갱신해 나간..

문제[C++] 백준 16953: A → B SILVER 2https://www.acmicpc.net/problem/16953 접근 방법백준 16953번은 정수 A를 B로 바꾸는 최소 연산 횟수를 구하는 문제다.사용할 수 있는 연산은 두 가지뿐이다.현재 값 × 2현재 값 뒤에 1을 붙이기 (예: 23 → 231)이 문제는 연산이 두 갈래로 계속 뻗어나가는 구조이기 때문에 그래프 탐색 문제로 볼 수 있다. 각 숫자를 하나의 노드라고 생각하면,val → val * 2val → val * 10 + 1이렇게 두 개의 간선이 존재하는 셈이다.최소 연산 횟수를 구해야 하므로 BFS(너비 우선 탐색) 을 사용했다. 상세 아이디어1. BFS로 최소 횟수 탐색queue> Q;Q.push(make_pair(a, 1)); ..

문제[C++] 백준 14940: 쉬운 최단거리 SILVER 1https://www.acmicpc.net/problem/14940 접근 방법이 문제는 시작점(값이 2인 위치)에서 각 칸까지의 최단 거리를 구하는 문제이다.이동은 상하좌우로 가능하며, 값이 1인 칸만 이동할 수 있고 0은 이동할 수 없다.최단 거리를 구하는 문제이므로 BFS(너비 우선 탐색) 를 사용했다. 핵심 아이디어:시작점(2)의 좌표를 먼저 찾는다.BFS를 이용해 사방 탐색을 진행한다.이동 가능한 칸(값이 1)만 큐에 넣는다.현재 칸의 거리 + 1을 다음 칸의 거리로 저장한다.BFS는 먼저 방문한 경로가 곧 최단 거리이므로 별도의 최단 거리 비교 없이도 정확한 값이 저장된다.결과 배열 ret은 -1로 초기화하여 도달하지 못한 칸을 구분..

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

문제[C++] 백준 2667: 단지번호붙이기 SILVER 1https://www.acmicpc.net/problem/2667 접근 방법이 문제는 지도에서 1로 표시된 집들이 상하좌우로 연결되어 있을 때,각 단지(연결 요소) 의 개수와 단지별 집의 수를 구하는 문제이다. 지도는 n × n 크기의 격자이므로, 모든 칸을 순회하면서 아직 방문하지 않은 집(1)을 만나면 BFS를 시작한다.BFS로 연결된 모든 집을 탐색하면 하나의 단지가 완성되며, 탐색 과정에서 방문한 집의 개수를 세어 단지 크기로 저장한다. 이 과정을 전체 지도에 대해 반복한 뒤, 단지의 개수와 각 단지의 크기를 오름차순으로 정렬해 출력하면 된다. 구현 시 주의할 점BFS를 시작할 때 초기 집도 단지 크기에 포함되므로 카운트를 1부터 시작해..

문제[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는 그래프의 모든 노드를 빠짐없이 방문하..

문제[C++] 백준 1260: DFS와 BFS SILVER 2https://www.acmicpc.net/problem/1260 접근 방법이 문제는 그래프가 주어졌을 때, 시작 정점 v에서부터 DFS와 BFS를 각각 수행한 결과를 출력하는 문제이다.정점과 간선의 관계를 그래프로 표현하면 아래와 같다.정점 → 노드(Node)간선 → 노드 간의 연결 관계그래프는 무방향 그래프이므로, 간선 정보 (x, y)가 주어지면 x → y, y → x 양방향으로 모두 연결해야 한다.DFS는 재귀를 이용해 구현하고, BFS는 큐(queue)를 이용해 구현한다. 구현 시 주의할 점방문 가능한 정점이 여러 개일 경우 번호가 작은 정점부터 방문해야 하므로 각 정점의 인접 리스트를 오름차순으로 정렬해야 한다. 정점 번호는 1 ~..