그래프 이론 (86) 썸네일형 리스트형 백준 5214번 [환승](C++) -yes6686- 티스토리 백준 문제 풀이: 5214 (환승)문제 링크: https://www.acmicpc.net/problem/5214문제 설명:지하철 노선과 환승 정보를 기반으로 1번 역에서 n번 역까지 이동하는 최소 환승 횟수를 구하는 문제입니다. 각 노선은 최대 k개의 역을 가지며, 총 m개의 노선이 존재합니다. 하나의 노선에 포함된 모든 역은 서로 직접 연결된 것으로 간주되며, 환승은 노선을 통해 다른 역으로 이동할 수 있을 때 발생합니다.핵심 알고리즘: 하이퍼 그래프 개념을 도입하여 노선(하이퍼노드)을 통해 역 간 이동을 BFS 방식으로 구현. BFS 레벨을 통해 최소 환승 횟수를 추적합니다.문제 해결 코드// 하이퍼 그래프 기반 환승 BFS 탐색#include #include #include using namespa.. 백준 1325번 [효율적인 해킹](C++) -yes6686- 티스토리 백준 문제 풀이: 1325 (효율적인 해킹)문제 링크: https://www.acmicpc.net/problem/1325문제 설명:컴퓨터 n대가 있고, 각각 신뢰 관계를 가진다. 한 컴퓨터가 다른 컴퓨터를 신뢰하면, 해킹 시 신뢰하는 컴퓨터도 함께 해킹된다. 이때, 어떤 컴퓨터를 해킹했을 때 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 모두 출력하라.핵심 알고리즘: 역방향 그래프를 구성하여 각 정점에서 DFS를 수행하면서 자신을 도달할 수 있는 정점 개수를 카운팅. 가장 큰 개수에 해당하는 정점들을 우선순위 큐에 저장 후 출력.문제 해결 코드// DFS로 역방향 해킹 그래프 탐색#include #include #include #include using namespace std;int visited[.. 백준 6118번 [숨바꼭질](C++) -yes6686- 티스토리 백준 문제 풀이: 6118 (숨바꼭질)문제 링크: https://www.acmicpc.net/problem/6118문제 설명:헛간 N개(1~N번)와 양방향 통로 M개가 주어진다. 농부 존은 1번 헛간에 있으며, 숨바꼭질을 할 때 가장 멀리 떨어진 헛간으로 도망가려 한다. 이때 1번 헛간에서 가장 멀리 떨어진 헛간 중 번호가 가장 작은 헛간의 번호, 그 거리, 그리고 그러한 헛간이 몇 개 있는지를 출력하는 문제이다.핵심 알고리즘: BFS를 통해 1번 헛간에서 각 헛간까지의 최단 거리를 구하고, 가장 먼 거리와 해당 거리의 헛간들을 정리한 후 결과 출력.문제 해결 코드// BFS로 가장 멀리 있는 헛간 탐색#include #include #include using namespace std;vector v[2.. 백준 15573번 [채굴](C++) -yes6686- 티스토리 백준 문제 풀이: 15573 (채굴)문제 링크: https://www.acmicpc.net/problem/15573문제 설명:지하 자원이 묻혀 있는 n×m 크기의 격자에서, 각 칸은 채굴에 필요한 비용이 정해져 있습니다. 채굴은 외곽(맨 윗줄, 맨 왼쪽 열, 맨 오른쪽 열)에 있는 칸들에서 시작해, 4방향(상하좌우)으로만 인접한 칸으로 확장할 수 있습니다. 이때 k개의 칸을 선택해 채굴할 때, 선택된 칸들 중 가장 높은 비용이 최소가 되도록 해야 합니다. 즉, k개의 칸을 채굴할 때 필요한 비용의 최대값을 최소로 만드는 것이 목표입니다.핵심 알고리즘: 다익스트라 스타일의 BFS를 이용한 최소 힙 기반의 탐색. 가장 작은 비용의 칸부터 k개까지 채굴하며, 그 중 가장 마지막 채굴 칸의 비용이 정답이 됩니다.. 백준 2617번 [구슬 찾기](C++) -yes6686- 티스토리 백준 문제 풀이: 2617 (구슬 찾기)문제 링크: https://www.acmicpc.net/problem/2617문제 설명:각 구슬의 무게가 서로 다르며, 일부 구슬들 사이의 비교 결과가 주어졌을 때, 특정 구슬의 무게가 전체에서 중간이 아님을 판별하는 문제입니다. 즉, 어떤 구슬이 n개의 구슬 중 정확히 중간보다 무거운지/가벼운지를 확정할 수 없는지를 판별합니다.구슬 수 N(≤100), 비교 결과 수 M(≤N(N-1)/2)이 주어지고, 모든 구슬을 대상으로 탐색하면서 절반 이상 무겁거나 가벼운 구슬 수를 구해 조건에 만족하면 해당 구슬은 중간이 될 수 없습니다.문제 해결 코드// 구슬 찾기 (양방향 DFS 탐색)#include #include #include using namespace std;ve.. 백준 33888번 [가오리 그래프](C++) -yes6686- 티스토리 백준 문제 풀이: 33888 (가오리 그래프)문제 링크: https://www.acmicpc.net/problem/33888문제 설명:가오리 그래프는 특정 규칙을 가진 무방향 연결 그래프입니다. N개의 정점과 N+3개의 간선으로 구성되며, 총 6개의 핵심 정점(머리 A, 왼쪽 날개 B, 중심 C, 오른쪽 날개 D, 아래쪽 날개 E, 꼬리 F)과 N−6개의 일반 정점으로 이루어져 있습니다.핵심 정점 사이에는 특정 쌍 간 단순 경로가 존재하고, 일반 정점은 항상 두 개의 정점과 연결되어 있으며 이 경로를 구성하는 중간 지점입니다. 주어진 그래프는 항상 가오리 그래프임이 보장되며, 정점 번호를 기준으로 핵심 정점을 판별할 수 있습니다. 단, D의 번호는 B보다 크다는 조건이 주어집니다.문제 해결 코드#incl.. 백준 10711번 [모래성](C++) -yes6686- 티스토리 백준 문제 풀이: 10711 (모래성)문제 링크: https://www.acmicpc.net/problem/10711문제 설명:모래사장의 모래성은 1부터 9까지의 강도를 가지며, 주변 8방향에 있는 파도가 침식되면 해당 강도만큼 버틸 수 있습니다. 빈 칸(.)은 이미 파도가 찬 상태이며, 매 시간마다 강도 이하로 주변 파도가 몰아치면 해당 성은 무너져 파도가 됩니다. 몇 초가 지나면 더 이상 무너질 모래성이 없는지 계산하는 시뮬레이션 문제입니다.이 문제는 BFS 또는 큐를 이용한 시뮬레이션으로 해결할 수 있으며, 각 턴마다 무너질 성을 계산하고 다음 턴에 영향을 줄 성들을 반복적으로 갱신합니다.문제 해결 코드// 모래성 (BFS 방식 시뮬레이션)#include #include using namespace.. 백준 9328번 [열쇠](C++) -yes6686- 티스토리 백준 문제 풀이: 9328 (열쇠)문제 링크: https://www.acmicpc.net/problem/9328문제 설명:감옥에 숨겨진 문서($)를 훔치기 위해 빌딩에 침입하려고 합니다. 빌딩은 벽(*), 빈 공간(.), 문서($), 문(A~Z), 열쇠(a~z)로 구성되어 있고, 바깥쪽에서 시작하여 내부로 진입하며 열쇠를 수집해 문을 열 수 있습니다. 초기 열쇠 목록이 주어지고, 주어진 보드에서 얻을 수 있는 문서의 최대 개수를 구하는 문제입니다.BFS와 키-문 매핑 로직을 이용하여 시뮬레이션을 구현해야 하며, 바깥 경계에서 진입 가능한 모든 지점을 탐색하는 것이 핵심입니다.문제 해결 코드// 열쇠 (BFS 기반 시뮬레이션)#include #include #include using namespace st.. 이전 1 2 3 4 ··· 11 다음