graph23 [백준 06118] 숨박꼭질 [Java] 문제https://www.acmicpc.net/problem/6118 풀이양방향 그래프의 1번 정점으로부터의 최대 깊이를 가지는 정점의 번호와 깊이, 동일한 최대 깊이를 가지는 정점의 수를 구하는 문제다.양방향 그래프부터 구성하자.import java.io.*;import java.util.*;public class Main { static List> graph = new ArrayList(); static int N; static int[] depth; public static void main(String[] args) throws IOException { // Init BufferedReader br = new BufferedReader(new Inp.. 2025. 2. 8. [백준 01325] 효율적인 해킹 [Java] 문제https://www.acmicpc.net/problem/1325 풀이단방향 그래프가 주어질 때, 가장 많은 정점을 방문할 수 있는 시작 정점을 찾는 문제다.A가 B를 신뢰할 때 B가 해킹 당하면 A도 해킹 당한다. 신뢰 관계에 대한 단방향 그래프를 구성하자.import java.io.*;import java.util.*;public class Main { static List> graph = new ArrayList(); static int N; static int[] cnt public static void main(String[] args) throws IOException { // Init BufferedReader br = new Buffere.. 2025. 2. 8. [프로그래머스] 등굣길 [Java] 문제https://school.programmers.co.kr/learn/courses/30/lessons/42898풀이MN크기의 보드에 장애물이 주어지고, (1, 1)에서 (M, N)까지 가는 최단 경로의 수를 1e9 + 7로 나눈 나머지를 출력하는 문제다.보통 좌표가 NM으로 주어지지만 여기서는 MN이다. puddles가 가지는 좌표또한 MN임을 유의하자.puddles에는 BLOCK표시를 해주자.( 0, 1 ) 또는 ( 1, 0 )에 1을 기입해 (1, 1)이 1을 가질 수 있도록 해주자.dp[i][j] : ( i, j )까지 오는 최단 경로의 수이후에는 모든 경로를 탐색하며 장애물이 없는 칸이라면 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]을 통해 최단 경로의 수를 합쳐주자.. 2025. 2. 1. [백준 11438] LCA 2 [Java] 문제https://www.acmicpc.net/problem/11438풀이기존에 선형 탐색으로 O(N)만에 LCA를 구하는 방법으로는 이 문제를 해결할 수 없다.2025.01.15 - [PS/Baekjoon Online Judge] - [백준 11437] LCA [Java] [백준 11437] LCA [Java]문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1kyr-db.tistory.com각 쿼리에 대해 O(logN)안에 LCA를 찾을 수 있는 방법에 대해 알아보자.깊이가 다른 두 노드의 깊이를 맞추고 LCA를 탐색하는 .. 2025. 1. 26. [백준 03584] 가장 가까운 공통 조상 [Java] 문제https://www.acmicpc.net/problem/3584풀이문제에서 주어지는 간선이 부모-자식 관계를 나타내고 있기 때문에 별도의 알고리즘 없이 dfs으로 선형탐색하면 된다. 우선 정점 u에 대해 루트 노드까지 탐색하며 방문 표시를 해주자.정점 v에 대해 루트 노드까지 방문하지 않은 노드까지 탐색하면 된다.소스코드보기 2025. 1. 25. [백준 11437] LCA [Java] 문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1번이라 언급되어 있으니, 1번 정점부터DFS를 통해 모든 노드의 부모 노드와, 깊이를 구해주면 된다.이제 LCA를 구해야 하는 두 노드 u, v에 대해 깊이가 다르다면 부모 노드로 올라가며 깊이를 맞춰주고,깊이가 동일한 두 노드의 부모노드가 같을 때까지, 즉 LCA를 찾아주면 된다.소스코드보기 2025. 1. 16. 이전 1 2 3 4 다음
