그래프 이론65 [백준] 12913: 매직 포션 - JAVA https://www.acmicpc.net/problem/12913 풀이0번 도시에서 1번 도시까지 가장 빠른 시간에 가야 한다. 포션을 마실 수 있는데 마시게 되면 한 도시에서 다른 도시로 이동하는데 드는 시간을 반으로 줄일 수 있다. n개의 도시, 포션 사용 가능 개수 k가 주어진다. 즉, 이차원배열을 `dist[n][k + 1]`로 선언하여 포션을 사용한 개수마다 체크해주어야 한다. 우선 도시마다 걸리는 시간이 모두 양수이기 때문에 0번 도시부터 모든 도시까지 최소 시간을 구할 수 있는 다익스트라 알고리즘을 적용했다. 다음 도시로 이동할 때 포션을 쓰지 않는 경우, 쓰는 경우를 나눠 진행해야 한다. 포션을 쓰는 경우는 현재 도시에 오는데 쓰인 포션의 개수가 k보다 작은 경우에만 가능하다. 메모리:.. 2024. 9. 10. [백준] 22352: 항체 인식 - JAVA https://www.acmicpc.net/problem/22352 풀이숫자로 채워진 N x M 크기의 격자가 2개 주어진다. 첫 번째 격자를 before, 두 번째 격자를 after라는 이름으로 이차원 배열에 저장했다. 문제의 내용은 before의 어떤 한 점에 백신을 놓는다면, 인접한 영역 중 같은 숫자의 영역들이 함께 동일한 값으로 업테이트 된다는 것이다. 업데이트 하였을 때 입력에서 주어진 after와 같으면 YES, 다르면 NO를 출력하면 된다. (0, 0) 부터 순회하면서 before와 after가 처음으로 달라지는 부분을 찾았다. 해당부분부터 bfs탐색을 통해 인접한 같은 값의 영역들을 after에 해당하는 값으로 바꿔주었다. 그 후, 다시 (0, 0) 부터 before와 after를 비교하.. 2024. 8. 19. [백준] 10282: 해킹 - JAVA https://www.acmicpc.net/problem/10282 풀이문제풀고 바로 블로그에 써야하는데 게을러서 늦게 쓰는 풀이.. a가 b를 의존하고 있다면, b가 감염되고 일정 시간 뒤 a도 감염된다. 따라서, b에서 a로 가는 경로가 있다고 생각했다. 이런 관계들을 `ArrayList`에 담아주었다. 감염된 컴퓨터 c부터 시작하여 다익스트라 알고리즘을 통해 경로를 따라갔다. 다익스트라 알고리즘은 최단 경로를 알려주는데, b에서 a로 감염될 때 걸리는 시간을 가중치로 두고 진행했다. 최종적으로 dist배열의 값이 INF가 아닌것들을 세주면 끝. 메모리: 148832KB시간: 784ms언어: Java 11import java.io.*;import java.util.*;public class Mai.. 2024. 7. 18. [백준] 19542: 전단지 돌리기 - JAVA https://www.acmicpc.net/problem/19542 풀이트리모양의 길 위에서 전단지를 돌리는데, 현재 노드에서 거리가 d이하인 노드들에는 현재 노드에서 전단지를 돌릴 수 있다. 따라서, 어떤 노드로부터 리프 노드까지의 거리가 d이하라면 더이상 앞으로 나아가지 않아도 된다는 것이다. dfs탐색을 통해 리프까지의 최대 거리를 구한다. 해당 거리가 d이상이라면 `cnt`값을 늘려줬다. 다시 시작 정점으로 돌아와야 하므로 `cnt * 2`가 정답이 된다. 메모리: 70564KB시간: 456ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int s, d, cnt; static ArrayList> g.. 2024. 7. 13. [백준] 25195: Yes or yes - JAVA https://www.acmicpc.net/problem/25195 풀이방향그래프가 주어지고, 1번 정점에서 출발해 리프노드까지 도달해야한다. 이때, 팬클럽이 위치하는 정점들을 피해 리프노드까지 도달할 수 있는지 확인하는 문제이다. dfs탐색의 인자로 팬클럽을 만났는지 여부를 담아 진행했다. 리프노드에 갔을 때 팬클럽을 만난적이 없다면 boolean값을 갱신해준다. 방문처리를 하지 않고 진행했는데 그 이유는 주어진 그래프가 사이클이 없음이 보장되었고, 방문처리를 할 경우 1 -> 2 -> 4 의 루트로 여행했다면, 1 -> 3 -> 4 의 루트로 여행하는 것은 이미 4번 정점이 방문처리 되었기 때문에 진행이 안되는 문제가 있었기 때문이다. 따라서, 방문처리 없이 바로 이전 정점으로만 갈 수 없게 했다. .. 2024. 7. 13. [백준] 21278: 호석이 두 마리 치킨 - JAVA https://www.acmicpc.net/problem/21278 풀이건물들이 도로로 연결되어있고, 2개의 건물을 골라 치킨집을 열어야 한다. 이때, 치킨집으로부터 각 건물들까지의 거리의 합이 최소가 되게 해야한다. 먼저 플로이드-워셜 알고리즘을 통해 각 건물들 사이의 거리를 구했다. for (int k = 1; k 건물들 사이의 거리를 구한 후, 2개의 건물을 정해 거리의 합을 계산해 정답을 갱신해주었다. 메모리: 17220KB시간: 192ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] dist; public static void main(String[.. 2024. 7. 13. [백준] 14217: 그래프 탐색 - JAVA https://www.acmicpc.net/problem/14217 풀이도시마다 연결된 도로들이 주어진다. 도로가 만들어지고 없어지는 계획에 대한 정보가 주어진다. 계획이 주어질 때마다 수도까지 몇 개의 도시를 방문해야 갈 수 있는지 구하는 문제이다. 도시마다 연결된 정보를 이차원배열에 넣었다. 계획이 주어질 때마다 이차원배열을 업데이트하고 bfs탐색을 통해 수도 1부터 도시까지 얼마나 걸려서 갈 수 있는지 체크하여 배열에 담아 반환했다. 메모리: 49952KB시간: 1232ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n; static int[][] city; static StringBui.. 2024. 6. 20. [백준] 23747: 와드 - JAVA https://www.acmicpc.net/problem/23747 풀이이 문제는 보드 위에서 이동과 와드 설치를 처리하는 문제로, 주어진 명령에 따라 보드의 상태를 변화시켜야 한다. W 명령을 수행하여 해당 위치와 인접한 같은 타입의 영역을 방문 처리하고, 상하좌우 이동을 통해 요리사의 위치를 업데이트했다. 최종적으로 방문한 위치를 '.'으로 표시하고, 방문하지 않은 위치를 '#'으로 표시하여 결과를 출력했다. 메모리: 127596KB시간: 720ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int r, c; static char[][] board; static boolean[][] result;.. 2024. 6. 10. [백준] 15591: MooTube (Silver) - JAVA https://www.acmicpc.net/problem/15591 풀이N번까지 번호를 가진 동영상들이 서로 연결되어있다. 연결마다 유사도가 k의 값으로 정해져 있다. 경로를 연결하여 유사도들 중 최소값이 두 동영상의 유사도가 된다. 특정 값을 정해 유사도가 그 값 이상인 동영상들의 개수를 묻는 문제이다. 시작 정점으로 할 동영상의 번호와, 특정 값이 주어지면 bfs탐색을 진행했다. 연결된 노드들을 탐색하여 유사도가 특정 값 K 이상일 때 카운트를 1증가시키며 큐에 넣어 계속했다. 메모리: 80360KB시간: 1008ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int v;.. 2024. 5. 20. [백준] 15971: 두 로봇 - JAVA https://www.acmicpc.net/problem/15971 풀이두 로봇이 서로 통신하기 위해서는 서로 인접한 지역에 있어야 한다. a구역에 있는 로봇과 b구역의 로봇에 서로 통신할 수 있는 지역으로 이동할 때 이동해야하는 거리의 최솟값을 구해야 한다. 생각한 풀이방법은 먼저 a지역에서 b지역까지 이동하고, 그 중 거리가 가장 큰 구간을 빼주는 것이다. dfs를 통해 int배열에 이동한 구역의 거리를 기록했고, 이 배열을 방문처리용도로 사용했다. 메모리: 80360KB시간: 1008ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int v; int cost.. 2024. 5. 19. 이전 1 2 3 4 ··· 7 다음