전체 글

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..

최근 C로 하는 과제들이 있어서 vi를 사용하는 시간이 꽤 많아졌는데, vim에서도 자동완성 플러그인들이 있는지 검색했다가 꽤 활용도가 높아보여 환경을 설정하게 되었다. 이러한 설정 과정들을 간략하게 정리해보려고 한다. https://github.com/VundleVim/Vundle.vim#about GitHub - VundleVim/Vundle.vim: Vundle, the plug-in manager for Vim Vundle, the plug-in manager for Vim. Contribute to VundleVim/Vundle.vim development by creating an account on GitHub. github.com https://github.com/ycm-core/YouCo..

문제 입력 예제 문제 풀이 입력 예제를 바탕으로 그래프화 해본 결과, 최단 경로를 구하는 방식이나 깊이 우선 탐색을 이용하는 방법으로 풀이가 가능하다는 생각이 들었다. 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씩 증가시..

문제 소개 DFS 맨 아랫줄까지 제한된 방향 수의 연산을 반복적으로 실행해야 될 것으로 파악되어 재귀적인 방법을 떠올렸다. 가능한 모든 경우의 수를 살펴보고자 DFS로의 접근을 시도하였다. def dfs(i, j, total_sum): if i == test_cases - 1: total_sum = max(total_sum, arr[i][j]) else: left = dfs(i + 1, j, total_sum) right = dfs(i + 1, j + 1, total_sum) route1 = arr[i][j] + left + total_sum route2 = arr[i][j] + right + total_sum total_sum = max(route1, route2) return total_sum tes..

문제 You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. i..

앞서 다익스트라 알고리즘에 대한 개념을 익혀보았으니 최단 거리 구하는 문제들을 몇 가지 살펴보자 방식 1. Priority Queue 모듈을 사용 BOJ 1753 import sys from queue import PriorityQueue input = sys.stdin.readline # 노드, 에지 개수 V, E = map(int, input().split()) # 출발 노드 K = int(input()) # 거리 리스트 (노드 갯수보다 한 개 많게 설정(노드 1부터 시작하게끔)) distance = [sys.maxsize] * (V+1) # 충분히 큰 값으로 초기화 # 방문 여부 저장 리스트 visited = [False] * (V+1) # 에지 데이터 저장 인접 리스트 (그래프) myList = ..