graph(38)
-
[백준 16236] 아기 상어 [Java]
문제http://boj.ma/16236요약초기 아기 상어의 크기는 2이며, 자신과 크기가 동일하거나 작은 물고기는 지나갈 수 있다.자신보다 크기가 작은 물고기만 먹을 수 있다.탐색 종료 조건: 더 이상 먹을 수 있는 물고기가 없는 경우먹을 수 있는 물고기가 2마리 이상일 경우 거리순으로 이동거리가 동일하다면 (1)최상단 (2) 가장 왼쪽을 우선시한다.이동에는 1초가 소모된다.상어의 크기만큼 물고기를 먹으면 상어의 크기가 1 증가한다.풀이 과정아이디어N ≤ 20이므로, BFS로 완전 탐색을 수행하며 다음에 먹을 수 있는 물고기를 찾으면 된다.좌표를 정렬해 비교하는 방식은 실제 상어의 이동 경로를 고려하지 못하므로 적합하지 않다.우선 상어와 물고기에 대한 클래스를 만들어주었다.static class Shar..
2026.01.05 -
[백준 12946] 육각 보드 [Java]
문제http://boj.ma/12946요약N * N 육각보드의 주어진 위치를 칠하기 위해 필요한 최소 색상의 수를 구하자.한 변을 공유하는 두 칸은 다른 색상을 사용해야 한다.풀이 과정아이디어인접한 칸은 현재 칸과 다른 색상을 사용해야 하므로, 그래프 탐색을 통해 주어진 위치에 RED - GREEN을 번갈아가며 부여하면 된다.if (board[nx][ny] == 'X' && visited[nx][ny] == NOT_VISITED) { cnt = Math.max(cnt, dfs(nx, ny, mark == RED ? GREEN : RED));}색상 부여 후, 현재 칸과 인접한 칸이 동일한 색상을 가진다면 (RED-RED or GREEN-GREEN) 두 색상 외에 또 다른 색상(BLUE)가 필요하다.3..
2025.11.29 -
[백준 27737] 버섯 농장 [Java]
문제http://boj.ma/27737 27737번: 버섯 농장 boj.ma 풀이문제 요약M개 이하의 버섯 포자를 심어 모든 빈 공간에 버섯이 자라도록 하자.아이디어독립된 빈 공간을 탐색하며 최소한의 버섯 포자를 사용했을 때, 모든 영역에 버섯이 자라도록 할 수 있는지 확인해야 한다. 버섯 포자를 최소 1개 이상 사용해야하며, 모든 영역을 채우기 위해 필요한 버섯 포자의 수가 M보다 크다면 불가능하다. // Solve int m = M; for (int i = 0; i 풀이 시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/27737.java problem-solving/baekjoo..
2025.09.13 -
[백준 21316] 스피카 [Java]
문제http://boj.ma/21316 21316번: 스피카 boj.ma 풀이문제 요약서로 다른 두 별에 대한 12개의 관계를 통해, Spica의 번호를 구하자.아이디어Spica는 연결된 별이 총 3개가 존재하며, 총 3개의 별에 연결된 별은 총 6개이다. 이는 전체 관계에서 유일하다. // Solve for (int i = 1; i 풀이 시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/21316.java problem-solving/baekjoon-online-judge/easy/21316.java at main · rogi-rogi/problem-solvingDa..
2025.08.04 -
[백준 32964] 재미있는 파이프 퍼즐 [Java]
문제http://boj.ma/32964 32964번: 재미있는 파이프 퍼즐 boj.ma 풀이문제 요약2 * N 공간에 있는 파이프를 조작해 도착지에 도착할 수 있는지 확인하자.아이디어이전 파이프 상태와 현재 영역의 파이프를 비교해 다음 영역이 이동 가능한 영역인지 확인하자.처음과 마지막은 직접 확인해주고, 1 ~ N - 1 구간은 이전/현재 파이프 상태를 확인해 다음 영역으로 넘어갈 수 있는지 상태를 업데이트 해주자. // Solve boolean goUp = true, goDown = (down[0] == 'L'); for (int i = 1; i 풀이 시간20분소스코드https://github.com/rogi-rogi/problem-solving/blob/main..
2025.07.30 -
[백준 31476] :blob_twintail_thinking: [Java]
문제http://boj.ma/31476 31476번: :blob_twintail_thinking: boj.ma 풀이문제 요약완전 이진 트리에 대해 주어진 규칙대로 bfs/dfs했을 때, 최소 비용을 구하자.아이디어문제에서 주어진 규칙은 다음과 같다.양갈래 블롭의 탐색: 기본 탐색 비용 U로 bfs를 했을 때, 두 자식이 존재할 때 마다 T만큼 비용이 증가한다.포니테일 블롭의 탐색: 기본 탐색 비용 U로 dfs를 했을 때, 더 이상 탐색할 자식 노드가 없어 돌아올 때도 U만큼 비용을 지불한다. 단, 탐색 가능한 마지막 노드에 도달한 후에는 복귀 비용을 지불하지 않는다.포니테일 블롭의 탐색의 구현을 하기 위해서는 방문 가능한 노드의 수를 알고 있어야 한다. 따라서 양갈래 블롭 탐색을 먼저 해주며 방문 가능한..
2025.07.24 -
[백준 18243] Small World Network [Java]
문제http://boj.ma/18243 18243번: Small World Network boj.ma 풀이문제 요약N명의 관계에 대해 누구든 6단계를 넘어 연결된 네트워크인지 확인하자.아이디어K개의 관계로 이루어진 양방향 그래프에 대해 임의의 번호에서 어떤 번호로든 6단계를 초과하는지 확인해야 한다.임의의 모든 위치에서 bfs를 수행하거나, floyd warshal로 최단 거리를 구해서 해결할 수 있다. private static int floydWarshall(int[][] graph, int N) { for (int k = 1; k 풀이 시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-ju..
2025.07.20 -
[Code Tree] 정수 사각형 최장 증가 수열 [Python]
문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-lis-on-the-integer-grid/description 정수 사각형 최장 증가 수열 설명 | 코드트리정수 사각형 최장 증가 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약N * N 행렬의 임의의 위치에서 값이 커지도록 상하좌우로 이동할 때, 가능한 최대 이동 횟수를 구하자.아이디어임의의 시작점(i, j)에서 DFS를 통해 구한 최대 이동 횟수는, 다른 시작점에서의 탐색 과정에서도 재사용될 수 있다.즉 부분 경로의 결과가 전체 탐색에서 활용된다.점화식은 다음을 나타낸다.dp..
2025.06.27 -
[백준 01388] 바닥 장식 [Java]
문제https://www.acmicpc.net/problem/1388 풀이주어진 보드에서 ‘|’ 또는 ‘-’ 모양의 타일을 각각 세로와 가로로 전부 연결해서 만들어지는 판자들이 몇개 인지 구하는 문제다.판자가 아닌 타일들을 방문하면서 규칙에 따라 하나의 판자로 만들어주는 횟수를 세면 된다. // Solve int cnt = 0; for (int i = 0; i 현재 타일의 종류에 따라 가로 또는 세로로 연결된 동일한 종류의 타일들을 모두 방문해주자.만약 다른 종류의 타일이 나온다면 더 이상 연결할 수 없으므로 탐색을 중단해야 한다. private static void connect(int x, int y, char type) { if (type ==..
2025.03.30 -
[백준 18405] 경쟁적 전염 [Java]
문제https://www.acmicpc.net/problem/18405 풀이N * N크기의 보드에서 번호가 낮은 바이러스부터 상하좌우로 증식한다.이 때, S초 후 ( X, Y )에 위치한 바이러스를 출력하는 문제다.우선 ( X, Y )에 시작부터 바이러스가 있을 수 있다. 확인 후 탐색을 진행하자. private static int bfs() { if (A[X - 1][Y - 1] != 0) return;번호가 낮은 바이러스 먼저 증식해야 하기 때문에 바이러스를 찾아, 바이러스 번호에 대해 오름차순으로 정렬 후 큐에 담아주자. List list = new ArrayList(); for (int i = 0; i 0) { ..
2025.03.03