java

[JAVA] 백준 11403 : 경로 찾기

문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 해결 방법 플로이드 와샬을 사용하는 기본적인 문제이다. 입력에서 주어진 값들을 해당 하는 배열에 넣고, 플로이드 와샬 알고리즘을 이용해서 정점 i에서 k를 들렸다가 j로 갈 수 있는 경로를 찾아서 배열에 입력해준 뒤에 출력하면 된다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; public class Main { p..

[JAVA] 백준 11779 : 최소비용 구하기 2

문제 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 해결 방법 다익스트라를 사용해야하는 문제이다. 다익스트라 문제를 여러 개 풀어보는 중인데 조금 생각이 필요한 문제라 괜찮은 것 같다. 경로는 인접리스트를 통해 입력해 주었고, Bus 클래스를 비용이 적은 순서대로 정렬한 뒤 우선순위큐를 사용해서 다익스트라를 구현하였다. 이 문제에서는 총 방문한 도시의 개수와 방문한 도시를 순서대로 출력을 해야하는 부분이 존재하는데, 그래서 그 전에 방문하였던 도시를 저장할 배열이 필요하다. 나..

[JAVA] 백준 4485 : 녹색 옷 입은 애가 젤다지?

문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 해결 방법 다익스트라 알고리즘을 활용하는 다른 문제 입니다. 다익스트라 알고리즘은 A에서 B로 시작점과 끝점이 문제에 주어져있고, 계산해야하는 값(거리나 비용 등)이 음수가 아닐 때 사용할 수 있습니다. 코드는 다른 다익스트라 알고리즘 문제와 비슷합니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java..

[JAVA] 백준 1261 : 알고스팟

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 해결 방법 다익스트라 알고리즘을 사용해서 풀어야 합니다. 다익스트라 알고리즘은 A에서 B로 가는 것의 최단 거리를 구할 때 주로 사용합니다. 이 문제에서는 시작 지점과 끝 지점이 지정되어있고, 구해야 하는 벽을 부순 횟수가 음수로 존재하지 않기 때문에 사용이 가능합니다. 코드는 다익스트라 알고리즘을 그대로 구현한 것이라 따로 설명하진 않겠습니다. 아래 링크의 분이 잘 설명해두셔서 참조 남깁니다. [알고리즘/자바] 다익스트라 알고리즘 (..

[JAVA] 백준 2933 : 미네랄, 18500 : 미네랄2

문제 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 미네랄 2도 같은 코드로 해결 가능. 해결 방법 범위는 크지 않아서 문제에서 주어진대로 구현만 하면 된다. 처음에 문제가 이해가 잘 되지 않아서 내가 이해한 것을 바탕으로 최대한 풀어서 설명하려고 한다. 일단 문제에서 얘기하는 클러스터는..