"꾸준하게, 지속하자 "

처음에는 2차원 평면상의 이동이 아니라서 DP로 풀어야 하나.. 하고 끙끙댔는데, 알고보니 +1,-1, *2 의 이동가능 범위(계층이동)의 1차원 수직선상의 이동으로 BFS를 이용하면 쉽게 풀리는 문제였다. 큐에 한계층 이동했을때를 현재 좌표에 반영해서 넣기 곤란했는데, 새로 움직인 좌표를 저장하는 nexti[ ]라는 배열을 만들어서 쉽게 해결하였다. 앞으로 좌표를 수직선이나 평면에 표현할 수 있고, 이동함+최솟값 조건의 문제는 DP가 아닌 BFS부터 생각해서 풀어야겠다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[]..

우선 어떤 알고리즘을 풀어서 해를 낼수 있겠다. 이런 느낌은 5초만에 바로 올정도로 접근법은 쉽지만, 구체적인 해답 경로를 찾기에는 어려웠다. 아니, 어렵다기 보다는 신박? 했다 해야하나... 우선 기존 BFS문제와는 조금 결이 달랐다. 기존 문제는 각문제마다 조건이나 상황이 다 다르겠지만, '어느 지점까지 도착할지 최솟값을 구하여라' 이런 류가 대부분이였다. 그러나 이 문제는 한 계층마다 같은 값을 더해준다는 느낌(한번 이동을 수행할때마다)은 BFS문제들과 같은데, 2가지 내 머릿속의 문제점을 해결하지 못하여서 쉽게 코드를 짜지 못하고 있었다. 내가 문제를 풀면서 마주했던 의문점. 1.어느곳이 마지막 도착점인지, 또한 무엇보다 모든 토마토가 다 익었는지 판단후 도대체 무슨 값이 모든 바구니가 다 익었을..

우선 문제를 보자마자 그래프 탐색 알고리즘을 이용하여 "연결요소"의 개수를 파악한 다음 그걸 리스트에 담고, 리스트를 정렬해준 다음, 차례로, 리스트 사이즈출력, 리스트요소들 하나씩 출력 해주면 끝난다. 풀이법을 생각해내는데 5분도 걸리지 않았지만.... 실제 정답을 내는데 디버깅 포함 1시간 걸린거 같다... 내가 실수한 부분은, 이 문제는 "최단거리"나, "백트레킹" 등, 그래프 탐색에 있어서 특수한 조건이 없기 때문에, DFS또는 BFS중 아무거나 사용 가능하다. 이유는 두 기법 모두, 연결된 노드를 전부 방문할수 있고, 그에 맞춰서 카운트 값을 올려줄수 있기 때문이다. 어제 쓴 포스트에서는 BFS를 이용해서 풀었기에, DFS로 풀어볼까 하면서 코드를 짰더니... 계속 리스트 사이즈 1, 값은 48..

전형적인 그래프 탐색 문제이며, "최단" 거리+미로의 탈출을 구하여야 함으로 BFS를 써야 한다. 최단 거리를 구하는 문제에서, DFS가 아닌 BFS를 쓰는 이유는 한가지 계층(똑같은 길이나 방법)을 이용해서 한번 이동을 한 거리가 모두 같음이, 자연스럽게 구현이 되기 때문이다. 또한 같은 계층으로써 방문한 노드가 목적지랑 같을시, 계층 한번이동할때(큐에 넣을때) 넣어준 카운트 값으로 쉽게 최단거리를 출력할 수 있다. 또한 미로의 탈출은 깊이우선 탐색을 하게되면, 해답을 찾지못해도, 계속 깊이가 끝날때까지 탐색을 하기에, 비효율 적이다. 그래서 난, BFS를 통해 이문제 풀이법을 구현해 보았다. 그러나 내가 이전 포스트에서 쓴 촌수문제에서, 큐에 넣을때(한번 계층이동이 이루어질때) 바로 카운트값을 더해주..

객체 조립기는 이전 포스트에서 내가 DI가 필요한 이유에 대해서 설명할 때, 객체생성에 사용할 클래스를 변경하기 위해(의존을 하는 클래스는 변경하지 않고) 객체를 주입하는 코드 한 곳 만 변경하는것이 DI의 장점이라고 하였다. 그렇다면 이 '한 곳'에 실제 객체를 생성하는 곳이 필요한데 그것이 바로 객체조립기이다. 백준 11725번. 그래프 구현 방법중 인접리스트의 각 배열에 저장된 리스트 요소들의 정렬에 대한 고찰. ->일단 순서를 생각한다는 것 자체가 넌센스이다. 왜냐? 인접리스트와 인접행렬 이라는 방법을 자체가 [루트노드]가 주어진 그래프를 나타내는 방법이 아니라, 단지 [노드]와 [노드]사이의 연결관계를 표현한 것이기 때문이다. ->즉, 리스트배열에 저장된 리스트요소들의 정렬순서는, dfs나 bf..