[백준/BOJ] 1937번: 욕심쟁이 판다 - Java 풀이 (DFS + DP)문제 소개백준 1937번: 욕심쟁이 판다 문제는 N x N 크기의 대나무 숲에서 판다가 최대한 오래 생존할 수 있는 일수를 구하는 문제입니다. 판다는 현재 있는 칸보다 대나무가 더 많은 칸으로만 이동할 수 있으며, 한 번 이동하면 하루가 지나는 것으로 간주합니다.이 문제는 모든 칸에서 출발하는 경우를 고려해야 하며, 각 출발점에서 가장 긴 이동 경로를 찾아야 합니다. 단순한 완전 탐색(Brute-force)으로 접근하면 시간 초과가 발생하기 쉬워, 동적 계획법(Dynamic Programming, DP)과 깊이 우선 탐색(DFS)을 결합하여 해결해야 하는 대표적인 문제입니다.문제 분석 및 접근 방식처음 문제를 접하면, 모든 칸..

https://www.acmicpc.net/problem/2644 👨‍👩‍👧 자바로 푸는 촌수 계산 (백준 2644) 📌 문제 개요 사람 수 n과 두 사람 x, y가 주어짐l개의 부모-자식 관계도 입력됨두 사람 간의 촌수를 계산하는 문제 촌수란? 부모와 자식은 1촌, 형제는 2촌부모-자식 관계만 주어지므로 그래프는 무방향 연결 그래프 💡 예제 입력97 371 21 32 72 82 94 54 6→ 7과 3의 관계는 다음과 같음:7 → 2 → 1 → 3 → 총 3촌 예제 출력3 🧠 알고리즘 접근 방식 각 사람을 정점으로 생각하고 양방향 그래프 구성DFS로 x부터 시작해서 y에 도달하는 경우를 탐색탐색 중 방문한 깊이 cnt를 통해 촌수를 구함 🔁 전체 코드import java.io..

https://www.acmicpc.net/problem/1068 🌲 자바로 푸는 트리 문제 풀이 (백준 1068 - 트리) 📌 문제 개요 N개의 노드로 이루어진 트리가 주어짐노드 중 하나를 삭제했을 때, 남은 트리의 리프 노드 개수를 구하는 문제 제약 조건 트리의 노드는 0번부터 N-1번까지루트는 부모가 -1인 노드삭제 시 해당 노드와 그 하위 노드 전부 제거 💡 예제 입력5-1 0 0 1 12→ 노드 2번을 지우면, 남은 트리 구조는 다음과 같다: 0 / \ 1 (X) / \ 3 4→ 리프 노드는 3, 4 → 2개 예제 출력2 🧠 알고리즘 접근 방식 입력 배열을 기반으로 트리 구조 생성tree[i] = [자식1, 자식2, ...]..

https://www.acmicpc.net/problem/2618 📌 자바(Java)로 푸는 경찰차 - 백준 2618 🚓🚓두 경찰차의 최소 이동 거리 + 이동 경로까지 구하는 DP 문제 🔎 문제 개요 백준 2618 - 경찰차 문제는N × N 크기의 도시에 경찰차 2대가 배치되어 있고,여러 사건이 순차적으로 발생할 때두 경찰차가 어떻게 사건을 분담해서총 이동거리를 최소화할 수 있는지를 구하는 문제입니다. 경찰차 1: 항상 (1,1) 위치에서 시작경찰차 2: 항상 (N,N) 위치에서 시작각 사건은 정확히 한 번만 처리해야 하며,각 사건은 경찰차 1 또는 경찰차 2가 처리해야 합니다.💡 예제 입력633 55 52 3 💡 예제 출력9121 총 이동거리: 9각 사건을 처리한 경찰차 번호 출력 🛠..

https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   📌 자바(Java)로 푸는 미로 탈출 명령어 문제 - 최적화 과정 🚀 🔎 문제 개요 프로그래머스 - 미로 탈출 명령어 문제입니다.주어진 N x M 크기의 미로에서 출발지(x, y)에서 도착지(r, c)까지 정확히 k번 이동하여 도달하는 가장 빠른 경로를 찾는 문제입니다.단, 사전순("d" → "l" → "r" → "u")으로 가장 빠른 경로를 찾아야 합니다. 💡 예제 입력int n = 3, m = 4;int x = 2, y = 3,..

https://www.acmicpc.net/problem/24480   📌 자바(Java)로 푸는 깊이 우선 탐색(DFS) - 백준 24480 문제 풀이 🚀🔎 문제 개요이 문제는 백준 24480번 - 깊이 우선 탐색 2 문제입니다.주어진 그래프를 깊이 우선 탐색(DFS)하며 방문 순서를 기록해야 합니다.단, 내림차순(큰 숫자부터) 으로 방문해야 한다는 점이 특징입니다.💡 예제 입력5 5 11 41 22 32 43 4💡 예제 출력14320➡ 1번 정점부터 내림차순으로 DFS 탐색하며 방문 순서를 출력해야 합니다.🛠 알고리즘 접근 방식이 문제를 해결하기 위해 DFS(깊이 우선 탐색) + 정렬을 활용합니다.✏️ 주요 고려 사항✔ DFS를 사용하여 그래프를 탐색✔ 간선 정보를 저장할 때 내림차순으로 ..

https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=2%2C3%2C4&languages=java&page=7 코딩테스트 연습 | 프로그래머스 스쿨개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!school.programmers.co.kr   📌 자바(Java)로 푸는 양궁대회 문제 풀이 🚀🔎 문제 개요이 문제는 프로그래머스 - 양궁대회 문제입니다.라이언이 화살 n개를 사용하여 어피치보다 높은 점수를 얻는 방법을 찾아야 합니다.단, 어피치의 화살 기록(info[])이 주어지며, 점수 차이가 가장 큰 경..

https://www.acmicpc.net/problem/24479   이 문제는 그래프 탐색 알고리즘인 DFS(Depth First Search)를 활용하여특정 시작 정점에서 탐색을 수행하며, 각 정점을 방문한 순서를 기록하는 문제다.아래 코드는 문제를 해결하기 위한 전체적인 흐름과 구현 방식을 포함하고 있다.우선, 입력으로는 정점의 개수 N, 간선의 개수 M, 탐색 시작 정점 R이 주어진다.이 정보를 기반으로 그래프를 인접 리스트 형태로 표현하기 위해 list라는 배열을 생성한다.이 배열은 각 정점이 연결된 다른 정점들을 저장하는 리스트를 담고 있다.이를 통해 그래프를 효율적으로 관리하고 탐색을 수행할 수 있다.입력으로 주어진 간선을 처리하여 무방향 그래프를 구성한다.각 정점의 연결 정보를 정렬하여 ..

https://school.programmers.co.kr/learn/courses/30/lessons/131130 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  while 문을 활용한 DFS로 풀이하였다.이번 문제는 cards[] 배열이 주워질 때, 랜덤으로 어떠한 두 박스를 고른다.두박스 안에는 박스번호와 박스안의 카드번호가 주워지는데 카드번호를 통해 다음박스 를 열게되고 그 박스안의 카드번호에 해당하는 박스를 다시 여는반복을 통해 cycle을 측정한 다음2가지 cycle의 크기 가 최대가 될 수 있는값을 구하는 문제다. 우선 boolean[] isVisited 를 활용하여 방문체크를 해주고반복문..

https://www.acmicpc.net/problem/1520   DFS와 메모이제이션을 활용하여 격자에서 시작점에서 도착점까지 내리막길만 따라가는 경로의 개수를 계산하는 문제다. 입력으로 주어진 N×M 크기의 격자는 각 칸에 고도 값이 저장되어 있으며, 이동은 인접한 칸으로만 가능하고 반드시 현재 위치보다 고도가 낮은 곳으로만 갈 수 있다.프로그램은 먼저 dpdpdp라는 메모이제이션 배열을 -1로 초기화한다.이는 특정 위치에서 출발해 도착점까지 갈 수 있는 경로의 개수를 저장하는 역할을 한다.그리고 value라는 2차원 배열에 고도 정보를 저장한다.dir 배열은 상하좌우 네 방향으로 이동하기 위한 도구로 사용된다.DFS는 시작점에서 출발해 가능한 모든 경로를 탐색한다.경로를 탐색하는 도중, 만약 이..