그래프 탐색

문제: 1로 만들기 2 (백준 12852번)문제 분석주어진 정수 x를 아래 연산 세 가지를 사용하여 1로 만드는 최소 연산 횟수를 구하고, 그 과정에서 거친 수열(경로)도 출력하는 문제이다.가능한 연산은:x가 3으로 나누어 떨어지면 3으로 나눈다.x가 2로 나누어 떨어지면 2로 나눈다.x에서 1을 뺀다.BFS(너비 우선 탐색)를 활용하면 최단(최소 연산) 경로를 자연스럽게 찾을 수 있으며, 각 단계에서 이전 상태(부모 노드)를 기록하면 경로 재구성이 가능하다.해결 방법BFS 탐색을 통한 경로 찾기시작점: 입력받은 x를 시작 노드로 한다.방문 기록: visited 배열(혹은 벡터)을 사용해 각 숫자에 도달한 직전 노드를 저장한다.연산 적용: 현재 노드에 대해,만약 2로 나누어 떨어진다면 node/2를,만약..

문제: 트리 (백준 1068번)문제 분석루트 없는 트리가 주어질 때, 특정 노드를 삭제하면 남은 트리에서 리프 노드 개수를 구하는 문제이다.입력 처리graph[i]: 각 노드의 자식들을 저장하는 인접 리스트.depth[i]: 각 노드가 몇 개의 자식을 가지는지 저장.삭제할 노드(target) 반영부모 노드에서 삭제할 노드의 연결을 끊음 (자식 수 감소).BFS를 활용하여 삭제할 노드 및 해당 서브트리를 모두 제거 (depth 값을 -1로 설정).리프 노드 개수 계산depth[i] == 0인 노드 개수를 세어 출력.전체 코드#include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> ..

문제: 스타트링크 (백준 5014번)문제 분석스타트링크라는 고층 건물에는 총 f층이 있고, 현재 s층에 있는 사람이 g층으로 가야 한다. 엘리베이터에는 위로 u층, 아래로 d층만 이동할 수 있는 버튼이 있다. 주어진 조건 내에서 최소한으로 버튼을 눌러 목표 층에 도착해야 한다. 만약 도착할 수 없다면 "use the stairs"를 출력해야 한다.핵심 아이디어BFS 큐 초기화현재 층(s)을 큐에 삽입하고, visited 벡터를 활용해 방문한 층과 해당 층까지의 버튼 누른 횟수를 기록했다.층 이동 로직큐에서 노드를 꺼낸 뒤:위로 이동: 현재 층 + u가 건물의 총 층수 f를 넘지 않으면서 방문한 적이 없다면 큐에 추가.아래로 이동: 현재 층 - d가 1층 이상이면서 방문한 적이 없다면 큐에 추가.종료 조건..

문제: 음악 프로그램 (백준 16724번)문제 분석이번 문제는 주어진 그래프에서 사이클의 개수를 구하는 문제이다.입력 형식을 보면 지도 밖으로 나가는 방향의 입력은 주어지지 않기 때문에 결국 화살표들은 사이클을 최소 1개 이상 무조건 생성을 하게 되어있다.DFS를 사용한 사이클 개수 찾기사이클 개수를 구하기 위해 DFS를 활용한다.이때, 사이클 판별을 위해 visited와 finish 배열을 사용한다.visited[y][x]는 현재 칸이 방문되었는지 여부를 저장한다.finish[y][x]는 현재 칸에 대한 탐색이 끝났는지를 나타낸다.DFS를 통해 현재 칸에서 다음 칸으로 이동하면서, 다음과 같은 조건으로 사이클을 판별한다.다음 칸이 방문된 적이 있지만 탐색이 끝나지 않은 칸이라면, 이는 사이클이 형성되었..

문제: 빙산 (백준 2573번)간만의 구현 문제이다. 구현 문제는 말 그대로 구현하는 데 시간이 많이 걸리기 때문에 사용하는 알고리즘 자체는 크게 어렵지 않은 경우가 많다. 이번 문제도 그런 케이스이며, 전체적인 로직은 다음과 같다.문제 의도배열에 1 이상의 수가 남아있는 동안 반복time을 증가시키고2차원 배열을 돌며 상하좌우의 0의 개수와 해당 좌표를 저장저장해둔 0의 개수만큼 해당 좌표의 값을 감소 (0 미만이 되지 않도록)2차원 배열을 돌며 BFS로 그룹 개수 체크그룹 개수가 2개 이상이면 반복문을 정지배열의 1 이상의 수가 있으면 time을 출력아니면 0을 출력알고리즘 개요시간(time) 증가매번 반복할 때마다 시간을 증가시킨다.녹을 빙산 계산 각 좌표에서 상하좌우로 바다가 몇 칸 있는지 계산하..