그래프 이론
[BOJ/JAVA] 16958번: 텔레포트
16958번: 텔레포트https://www.acmicpc.net/problem/16958키워드2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다.두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자.구현두 도시 간 거리를 전부 계산하여 cityMatrix에 저장한다.만약 두 도시가 특별한 도시라면 T와 비교하여 더 작은 시간을 저장한다.플로이드-워셜 알고리즘을 이용하여 최소 이동 시간을 구하자.코드import java.io.BufferedRead..
[BOJ/JAVA] 11060번: 점프 점프
11060번: 점프 점프https://www.acmicpc.net/problem/11060키워드i번째 칸에 쓰여 있는 수를 AiA_iAi라고 했을 때, 재환이는 AiA_iAi이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다.가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력구현private static int dp(int index, int count)현재 위치가 index이고, 뛴 횟수가 count일 때 끝까지 갈 때의 최소 점프 횟수 반환하는 메소드끝에 도달한 경우 (index == N-1)현재까지 뛴 횟수를 반환한다.캐시값이 존재하는 경우 (cache[index][count] ≠ -2)캐시값을 반환한다.갈 수 있는 경로를 탐색한다.범위는 [1, A[index]] 이다.만약 뛰는 거..
[BOJ/JAVA] 7562번: 나이트의 이동
7562번: 나이트의 이동https://www.acmicpc.net/problem/7562키워드나이트가 한 번에 이동할 수 있는 칸은 아래와 같다.이 때 원하는 위치에 가기까지 이동 횟수를 구하라구현final static int dydx[][] 현재 위치 기준으로 나이트가 이동할 수 있는 방향(8방향)을 기록한다. private static int solution()현재 위치에서 나이트가 목적지까지 갈 때 최소 이동 횟수를 반환한다.board[][]모든 위치의 값을 -1로 초기화한다. 현재 위치 기준으로 이동할 위치(toY, toX)를 계산한다.해당 위치가 -1값이 아니라면(방문한 적이 없다면)board[toY][toX] = here.count+1 로 갱신한다. (방문 처리)갈 수 있는 경로를 큐에 추가..
[BOJ/JAVA] 1068번: 트리
1068번: 트리https://www.acmicpc.net/problem/1068키워드트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.구현private static int solution() 노드를 돌면서 리프 노트의 갯수를 반환하는 메소드방문할 노드를 찾기tree[i] 값은 i노드가 tree[i]값을 부모로 한다는 의미이다.tree[i]는 자식을 가진 노드라는 의미이므로 이 노드는 방문할 필요가 없다.만약 현재 노드가 지워지는 노드라면부모 노드가 리프노드가 될 수 있으므로, 부모 노드 추적을 하지 않는다.boolean isLeafNode[] 에 리프 노드일 수도 있는 ..
[BOJ/JAVA] 11403번: 경로 찾기
11403번: 경로 찾기https://www.acmicpc.net/problem/11403키워드가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램구현단순 플로이드-워셜 알고리즘을 이용하여 구현한다. private static void floydWarshall()k를 경유하여 i에서 j로 갈 수 있으면 경로에 추가한다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class java_11403 { static int N; stati..