개발 노트

BOJ 7576번 토마토 https://www.acmicpc.net/problem/7576 BFS를 할 때 상하좌우를 직접 지정해줘도 되지만 방향 순서쌍 dx,dy를 이용해도 됨 BFS와 DFS의 차이는 que 자료형, dist 저장 위치가 가장 큰 차이인 듯.

풀이 1. 시작점과 출발점을 찾아야함 1.1. 임의의 끝점에서 다익스트라로 가장 먼 점 탐색 1.1. 가장 먼 점에서 다익스트라로 다시 가장 먼 점 탐색 1. 시작점과 출발점 경로 내의 마트 탐색 1.1. Main Road 내의 마트임을 표시 1. UnionFind를 변형하여 각 점별로 Main Road까지의 거리 계산

BOJ 1854 K번째 최단경로 풀이: 1. 도로가 단방향. 2. 시작점은 경로비용 0 (문제에서 제시) 3. 시작점은 1번도시로 고정 이 전제하에 각 도시에 대해 모든 최단경로를 가장 작은 순으로 정렬했을 때 문제에서 주어지는 K번째 경로비용을 구하면 된다. 다만 모든 최단 경로를 구할 경우 메모리 초과가 발생한다. 따라서 모든 경로를 탐색하면서 각 K번째 최단경로까지만 보관한다. 각 경로의 최단경로를 보관하기 위해 입력받는 순간 정렬되는 Priorityque를 배열로 사용한다. (PriorityQueue[] costList = new PriorityQueue[N]; //도시 개수만큼 생성) que에 들어가는 순간 정렬되는 효과를 이용한다. 적은 비용은 두고 큰 비용은 그거보다 작은 비용을 만날 경우 ..

BOJ 1238 파티 Java 풀이: 각 마을 -> 파티 목적지 에 드는 비용 + 파티 목적지 -> 각 마을 에 드는 비용 시작점을 파티 목적지로 설정하고 시작점에서부터 최소비용을 구하면 각 마을까지의 비용을 구할 수 있다. 하기 이미지의 파란색 글씨 중 1: 각 마을 -> 파티 목적지 2: 파티목적지 -> 각 마을 3: 1번마을->파티목적지까지의 연산. que.add(Node(To, Value)), 비용 Dist[], 방문여부 Visited[] 1번 마을 비용을 메인 Dist에 등록 4: 3번 마을-> 파티목적지까지의 연산. 5: 4번 마을-> 6: 파티목적지(2) -> 각 마을

BOJ 1197 최소 스패닝 트리 Java www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이: 여태껏 들었던 비용보다 적게 들 경우 그걸로 갱신해야한다.