이번 문제는 플로이드-워셜 알고리즘에 대해 먼저 이해하고 풀어야한다! 플로이드-워셜(floyd-warshall)정의플로이드-워셜 알고리즘은 그래프에서 모든 쌍의 최단거리를 구하는 알고리즘입니다. 이 알고리즘은 동적 계획법을 사용하여 모든 노드 쌍 사이의 최단 경로를 효율적으로 찾을 수 있습니true-false.tistory.com DFS 풀이 코드(1% 시간초과)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public class 운동 { private static ArrayLi..

풀이 시간  - 1H 초과 풀이 과정 - 맵을 돌면서 벽이면 마주치면 BFS - visited 배열 초기화 - 다시 1번 과정 반복 1차 풀이 코드 (시간 초과)package algorithms.src.단기간성장;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class b16946_벽부수고이동하기4 { private static int N,M; private static int[][] map; private sta..

https://www.acmicpc.net/problem/1655  우선 문제를 풀기 전 최대힙과 최소힙 자료구조 개념을 알고 가면 좋을 문제이다.https://true-false.tistory.com/12  처음 문제를 봤을 땐 간단한 거 치고 티어가 낮지 않아서 조금 의아했다.그 마음으로 ArrayList를 작성해서 풀었는데 역시나 시간초과가 발생하더라..import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Comparator;public class b1655_가운데를말해요 { public static void ..

https://www.acmicpc.net/problem/12865  문제 설명이 문제는 전형적인 배낭 문제(Knapsack Problem)로, 다이나믹 프로그래밍(DP)을 사용하여 해결할 수 있다.주어진 물품들을 배낭에 넣을 때, 배낭이 담을 수 있는 최대 무게를 초과하지 않으면서 물품들의 가치 합을 최대화하는 문제이다. 다이나믹 프로그래밍의 기본 개념다이나믹 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 방법이다.각 부분 문제는 한 번만 풀고, 그 결과를 재사용하여 전체 문제를 해결한다.이번 배낭 문제가 딱 이런류이다. 예로, 최대 적재량이 8kg인 배낭에 여러 물건들(weight[])을 담아 최대 가치를 구하고자 한다.각각 가치가 3, 4이고, 무게가 3, 4인 1, 2번 물건을 담은..

https://www.acmicpc.net/problem/2644  풀이 시간  - 25M 풀이 과정 - 양방향 그래프 - 시작 사람 노드에서 출발해 끝사람 노드를 마주치면 출력, 못마주치면 -1 출력 - visited 배열 체크풀이 코드 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class b2644 { static int s, e, dist; static boolean isGoal = false; static ArrayList[] parent; public static void main(String[] args) th..

https://www.acmicpc.net/problem/2667 풀이 시간  - 1H 이내 풀이 과정 - 맵을 돌면서 집이 있는 곳을 마주치면 BFS - visited 배열 체크 - 다시 1번 과정 반복 - 단지 수, 단지별 건물 수 오름 차순으로 출력 (여기서 실수함) 풀이 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class b2667_단지번호붙이기 { private static int N; private static int[][] map; private static boolean[][] visited; stat..