Algorithm/BaekJoon

[JAVA] 백준 11657 : 타임머신

문제 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 해결 방법 벨만-포드 알고리즘을 사용해야 하는 문제이다. 한 정점에서 다른 모든 정점의 최단 경로를 탐색해야 하는데 Cost가 음인 경우 사용 가능하다. 최단 경로를 나타내는 배열을 최댓값으로 초기화 해준 다음 배열을 사용해서 탐색을 진행한다. 정점의 수 - 1 만큼 반복문을 통해 최단 경로를 탐색해주고, 한 번 더 탐색하였을 때 또 최단 경로가 바뀐다고 하면 음의 사이클이 존재한다는 뜻이다. 여기..

[JAVA] 백준 1240 : 노드사이의 거리

문제 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 해결 방법 가중치가 있는 트리의 탐색 문제의 기본이다. class를 이용해서 다음 방문할 위치와 거리를 입력해두고 탐색하면서 거리를 계속 더 해주면 된다. 탐색은 BFS를 사용했다. 간선을 입력할 때 양쪽으로 이동이 가능하게끔 쌍방향으로 리스트에 넣어주어야 한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java..

[JAVA] 백준 8972 : 미친 아두이노

문제 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 해결 방법 다 풀고 나서 보니 BFS 방법을 이용해서 푸신 분들도 있었다. 그 분들에 비하면 내 코드가 속도가 느리긴 하지만, 이런 코드도 있다 정도로 봐주면 좋겠다. 문제의 1~5번을 순서대로 구현했고, 방향은 dx, dy 배열을 통해 입력해두었다. 입력의 젤 마지막에 종수가 움직이는 방향이 주어지는데, 주어질 때마다 moveI 함수를 실행시켜 전체 맵을 변경시켜주었다. moveI 함수는 처음에 입력받은 값에 따라 종수 아두이노를 움직이고, 종수 아두이..

[JAVA] 백준 11967 : 불켜기

문제 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 해결 방법 루모스 ~ 기본적인 탐색 문제에서 불을 켜고, 불이 켜진 방만 이동이 가능한 조금 응용된 문제이다. 각 방에 있는 스위치를 나타내기 위해서 ArrayList 배열을 사용해서 리스트에 불을 켤 수 있는 곳의 좌표를 넣어 두었고, light와 visit을 활용해서 불이 켜져 있는지 여부와 방문 여부를 체크하였다. 탐색은 BFS를 사용했는데 불을 켤 수 있는 방이 존재하는지 여부는 리스트가 비었는지 ..

[JAVA] 백준 13335 : 트럭

문제 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 해결 방법 처음엔 큐를 사용해서 구현을 하려다가 그냥 리스트로 구현을 해도 무관해보여서 리스트로 구현을 했다. Truck 클래스를 통해서 무게와 다리에 머문 시간 값을 가질 수 있게 해주었고, 다리에서 머문 시간이 w와 동일하면 리스트에서 제거해주는 방식을 사용했다. 리스트에서 값을 제거하면 index 값이 한 칸씩 앞으로 당겨지기 때문에 i--를 통해서 맞추어주었고, 다음 순서의 트럭이 어떤 트럭인지 알기위해..