Algorithm/Java

DFS와 BFS의 기초를 다질 수 있는 문제로서 다양한 풀이 방법을 적용해보았다. 문제 입력 예제 문제 풀이 인접 리스트 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class BOJ1260 { static int n, m, v; static ArrayList[] arr; static boolean[] dfsVisited; static boolean[] bfsVisited; static String dfsOrder; static String bfsOrder; public static void main(String[] args) t..

문제 입력 예제 문제 풀이 입력 예제를 바탕으로 그래프화 해본 결과, 최단 경로를 구하는 방식이나 깊이 우선 탐색을 이용하는 방법으로 풀이가 가능하다는 생각이 들었다. DFS & BFS 둘 다로 풀이할 수 있는 문제이므로 두 알고리즘을 각각 적용하여 풀이해보기로 했다. BFS 위 그래프의 인접행렬과 노드 간 연결 관계(양방향)를 테이블로 표현해보았다. 추가) 아래 그림에서는 인접리스트라고 적었지만 구현은 인접행렬 방식으로 되어 있습니다. 인접행렬과 인접리스트의 차이가 궁금하다면 맨 아래 링크된 글을 참고 바랍니다. 방문 배열값 업데이트 과정은 다음과 같다. import java.util.*; public class BOJ2644 { static int n, m, start, end; static int[..

문제 소개 문제 요약 N개의 도시 인접한 두 도시 사이의 도로의 개수 N-1개 도로 이동 시 1km마다 1L의 기름을 사용 처음 출발 시 기름이 없으므로 첫번째 도시에서 기름을 넣고 출발해야 함 도시 당 하나의 주유소가 위치해있음 (리터당 가격이 다름) 왼쪽 도시에서 오른쪽 도시로 이동하는 데에 드는 최소 주유비용을 구하는 과정을 정리해보았다. 가격이 싼 도시의 주유소에서 많이 넣는 것이 주유비를 최소화할 수 있는 방법이나, 처음 출발 시에는 기름이 없으므로 무조건 첫 번째 도시에서 주유를 하고 가야한다. 다음 도시의 주유소를 이용하는 것이 불가하기 때문에 현재 선택지에서 최선의 선택을 하는 Greedy 알고리즘을 적용하는 것이 하나의 방법이 될 수 있는 것으로 보인다. 풀이 import java.uti..

문제 소개 BFS 풀이 직관적으로 보았을 때, 현재 셀을 기준으로 상하좌우로 이동하며 가능한 경로를 탐색하기 때문에 DFS나 BFS로 해결가능한 문제이다. 방문 조건 중 하나로 1인 칸으로만 이동이 가능하므로 1인 칸을 그래프에서의 하나의 노드로 볼 수 있기 때문이다. 다만 DFS로 풀었을 경우, 재귀적인 특성으로 인해 depth를 다루기가 까다롭다. 때문에 depth 대로 쭉 내려오는 것이 가능한 BFS를 사용하는 것이 더 간단한 풀이가 될 것으로 보인다. BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 바로 다음 깊이로 내려가는 식으로 동작하기 때문이다. 첫번째 출력 예시를 통해 예상되는 실행 결과를 확인해보았다. 시작점으로부터 출발하여 방문 가능한 셀들을 한 칸 씩 이동할때마다 1씩 증가시..