분류 전체보기 (567) 썸네일형 리스트형 백준 2170번 [선 긋기](C++) -yes6686- 티스토리 백준 문제 풀이: 2170 (선 긋기)문제 링크: https://www.acmicpc.net/problem/2170문제 설명:좌표 평면 위에 n개의 선분이 주어집니다. 각각의 선분은 x축 위에서 시작점과 끝점을 가지며, 이 선분들이 겹치는 경우 중복을 제거한 실제 총 선 길이를 구하는 문제입니다.이 문제는 선분을 시작점을 기준으로 정렬한 뒤, 현재 선분이 이전 선분과 겹치는지를 판단하여 겹치지 않으면 누적 길이를 더하고, 겹치면 끝점을 갱신하는 방식으로 해결할 수 있습니다.문제 해결 코드// 선 긋기 (정렬 후 누적합)#include #include using namespace std;pair arr[1000001];int main() { ios::sync_with_stdio(false); c.. 백준 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.. 백준 16920번 [확장 게임](C++) -yes6686- 티스토리 백준 문제 풀이: 16920 (확장 게임)문제 링크: https://www.acmicpc.net/problem/16920문제 설명:여러 명의 플레이어가 각각 주어진 이동 속도만큼 자신의 영역을 확장하는 턴 기반 보드 게임입니다. 맵에는 벽(#)이 있을 수 있고, 이미 다른 플레이어가 점령한 칸은 차지할 수 없습니다. 모든 플레이어가 더 이상 영역을 확장할 수 없을 때 게임이 종료되며, 종료 시점에 각 플레이어가 점령한 칸 수를 출력해야 합니다.이 문제는 BFS와 다중 큐를 통해 각 플레이어의 독립적인 확장을 시뮬레이션하는 방식으로 해결할 수 있으며, 플레이어별 속도 제어가 핵심입니다.문제 해결 코드// 확장 게임 (BFS 방식 다중 큐 시뮬레이션)#include #include using namespac.. 백준 20304번 [비밀번호 제작](C++) -yes6686- 티스토리 백준 문제 풀이: 20304 (비밀번호 제작)문제 링크: https://www.acmicpc.net/problem/20304문제 설명:0부터 N까지의 숫자 중 보안상 사용할 수 없는 금지 번호들이 주어졌을 때, 가장 안전한 비밀번호를 선택하려 합니다. 안전도는 현재 선택한 비밀번호와 금지된 숫자들 사이의 XOR 거리 중 최소값으로 정의됩니다. 즉, 금지된 번호들과 가장 멀리 떨어진 비밀번호(= 최소 XOR 거리가 최대인 숫자)를 찾아 그 최소 XOR 거리를 출력하는 문제입니다.문제 해결 코드// BFS 기반 XOR 거리 확산을 통해 안전도가 가장 높은 숫자를 찾는 코드#include #include #include using namespace std;int visited[3000001];int n;voi.. 백준 15903번 [카드 합체 놀이](C++) -yes6686- 티스토리 백준 문제 풀이: 15903 (카드 합체 놀이)문제 링크: https://www.acmicpc.net/problem/15903문제 설명:N개의 카드를 가진 카드 묶음이 주어집니다. 이 중 가장 숫자가 작은 두 카드를 골라 합쳐 두 장 모두 그 합으로 바꾸는 작업을 M번 반복한 뒤, 모든 카드의 합을 출력하는 문제입니다.가장 작은 두 수를 반복적으로 찾아야 하므로, 우선순위 큐(Min-Heap)를 사용한 그리디 알고리즘이 적합합니다.문제 해결 코드// 우선순위 큐를 활용한 최적화된 풀이#include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n.. 백준 16933번 [벽 부수고 이동하기 3](C++) -yes6686- 티스토리 백준 문제 풀이: 16933 (벽 부수고 이동하기 3)문제 링크: https://www.acmicpc.net/problem/16933문제 설명:N×M 크기의 격자 지도에서 최단 경로로 (0,0)에서 (N-1,M-1)로 이동하고자 합니다. 이동 중 최대 K개의 벽을 부술 수 있으며, **낮에는 벽을 부수고 이동 가능하지만 밤에는 벽을 부술 수 없습니다.**또한, 벽이 있는 곳은 부수지 않으면 지나갈 수 없습니다. 이동은 상하좌우로 가능하며, 한 칸을 이동하는 데 1초가 걸립니다.문제 해결 코드// 벽 부수고 이동하기 3 - BFS + 낮밤 판별#include #include #include using namespace std;int n, m, k;int arr[1001][1001]; .. 백준 11967번 [불켜기](C++) -yes6686- 티스토리 백준 문제 풀이: 11967 (불켜기)문제 링크: https://www.acmicpc.net/problem/11967문제 설명:N×N 크기의 방이 주어지고, 일부 방에는 스위치가 있어 다른 방의 불을 켤 수 있습니다.(1, 1) 방에만 처음 불이 켜져 있고, 불이 켜져 있으면서 인접한 방만 이동할 수 있습니다.목표는 불을 켤 수 있는 방의 수를 구하는 것입니다.제약 조건:스위치는 (x, y) 방에 위치하며, (a, b) 방의 불을 켤 수 있음.불이 꺼진 방은 지나갈 수 없고, 불이 켜져 있어도 도달할 수 없는 방에는 갈 수 없음.문제 해결 코드// 불켜기 - BFS + 스위치 시뮬레이션#include #include #include #include using namespace std;int n, m, a.. 이전 1 2 3 4 ··· 71 다음