본문 바로가기

백준154

백준 16236 c++ "아기 상어" -[PlusUltraCode] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net [필자 사고] BFS탐색 문제이다. 문제를 이해하고 푸는 과정이 쉽지가 않았다. 문제는 쉽게 말해서 현재 위치에서 sero가 작은거부터 먹는다 만약 sero가 같은게 존재하면 garo가 작은걸 먹는다고 이해하면 쉽다. 또한 배열 내에서 먼저 먹어야 하는게 존재하기 때문에 우선순위큐를 이용하여 먹을거에 우선순위를 부여했다. 중요한건 먹고나면 다시 BFS를 이용하여 먹을거에 우선순위를 구해야 .. 2024. 3. 3.
백준 10026 c++ "적록색약" -[PlusUltraCode] https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net [필자 사고] 이 문제는 전형적인 2차원 배열 BFS탐색문제이다. BFS탐색을 적록색약인 사람과 아닌 사람 구별해서 해주면 문제를 쉽게 풀 수 있다. [소스 코드] #include #include #include using namespace std; int dy[4] = { 0,1,0,-1 }; int dx[4] = { 1,0,-1,0 }; vector Arr; vector Arr2; ve.. 2024. 3. 2.
백준 7562 c++ "나이트의 이동" -[PlusUltraCode] https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net [필자 사고] 이 문제는 BFS 너비우선 탐색 및 최단거리를 합쳐 놓은 문제이다. 대부분의 2차원 배열에서의 이동경로는 상 하 좌 우 만 있었지만. 공식처럼 외운 사람은 나이트의 이동 경로를 어떻게 코드로 짜는지 모를 수 있다. 약간의 팁이 있다면 공식처럼 외우지 말고 나이트가 이동할 수 있는 모든 경우의 수를 dx와dy에 순서대로 저장해 놓는다라고 생각하면 쉽게 작성할 수 있다. [소스 코드] #.. 2024. 3. 2.
백준 9470 c++ "Strahler 순서" -[PlusUltraCode] https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net [필자 사고] 이 문제는 위상정렬 알고리즘을 사용하여 해결해야 하는 문제이다. 이 문제만의 특이한 점은 몇개의 노드가 nextIdx에 가리키고 있는지, 동시에 그중 가장 큰값이 무엇인지를 어떻게 저장하고 관리하는지가 핵심인 문제같다. 필자는 vector안에 우선순위큐를 넣어 최댓값을 바로 바로 찾을 수 있도록 문제를 해결했다. [소스 코드] #include #include #include us.. 2024. 3. 2.

티스토리툴바