은비블로그

https://www.acmicpc.net/problem/7576[풀이과정]일수 구하는 게 힘들었다. bfs()의 day 값을 토마토 객체의 day값으로 갱신하면 마지막의 가장 큰 값의 day가 반환된다. int반환 bfs 함수 작성은 처음이었다.  [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;/*M*N 상자익은 토마토의 인접한 익지 않은 토마토는 하루 뒤 익게 됨인접하다란 상하좌우 네 방향을 의미모든 토마토가 익는 최소 일수 */public class Main { static BufferedReader br = new BufferedReade..

https://www.acmicpc.net/problem/1753[코드]package boj;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;/*방향그래프가 주어지면 시작점에서 다른 모든 정점으로의 최단 경로를 구하기모든 간선치의 가중치는 10 이하의 자연수 */public class Main_1753_최단경로 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static StringBuilder s..

https://www.acmicpc.net/problem/11779[풀이과정]그냥 최소비용을 구하는 것이 아니라 경로까지 구하는 문제였다.경로를 구할 때 처음엔 배열 인덱스를 순서로 해서 넣을까 하다가 불가능한 것 같아서 엄청 고민했다.그러다 현재 도시 번호를 인덱스로 두고 이 도시에 오는 바로 이전 번호를 값으로 계속 갱신하면 기존 다익스트라 방식 그대로 하면서 복잡한 코드가 필요없을 것 같아 실행했다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Priorit..

https://www.acmicpc.net/problem/1092[풀이과정]처음에 복잡도가 N*M인 코드를 작성했는데 틀렸다. 왜 틀렸는지 아직도 잘 모르겠음..가장 중요했던 건 내림차순으로 정렬하는 것인 것 같다. 가장 큰 수들끼리 비교해서 옮기지 못 하면 -1 반환하고, 아니면 계산했는데,만약 크레인 무게 제한이 20 10 10일 때, 박스 무게가 20 20 10인 경우를 가정했을 때 20 10 / 20 이렇게 두 번 옮겨져야 한다. 그럼 박스를 가리키는 idx를 어떻게 앞으로 옮길지 엄청 고민했는데, 박스를 삭제하면 되는 일이었다. 옮겨진 박스를 삭제하면서 while문에서 초기화를 0으로 해주면 저절로 남겨진 박스 중 가장 무거운 박스를 가리키게 된다.  [코드]import java.io.Buffe..

https://www.acmicpc.net/problem/9205[풀이과정]모든 편의점을 들려야 한다고 생각했다.편의점을 들리지 않고도 페스티벌에 도착할 수도 있으므로 갈 수 있는 최적의 경로를 찾는 방식으로 해결해야 했다.BFS를 통해서 갈 수 있는 경로를 탐색하며 페스티벌에 도착하면 happy를 출력했다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;/*상근이네(출발), 맥주 한 박스(20개), 50미터 당 한 병씩, 페스티벌(도착)맥주를 더 구매할 수도 있지만 소지할 수 있는 맥주는 최대 20병 */public class Main { st..

https://www.acmicpc.net/problem/1245 [풀이과정]쉬운 문제인데 문제 이해를 이상하게 해서 엄청 헤맸다.DFS를 사용했고 모든 시작점을 산봉우리라고 가정한 후 탐색했다.시작점의 인접격자 중 시작점보다 값이 큰 곳이 있으면 산봉우리가 아니므로 isTop을 false로 바꿔주었고높이가 같은 곳이 있으면 같은 산봉우리로 취급되므로 dfs를 돌려주었다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/* N*M의 농장. 산봉우리가 총 몇 개인지 세야 한다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인..

https://www.acmicpc.net/problem/1504[풀이과정]처음엔 모든 경우의 수를 탐색하며 V1, V2를 방문하는지 체크하는 방식으로 하려 했다. 하지만 이미 방문한 노드와 간선을 재방문할 수 있다는 부분에서 그렇게 진행하면 무한루프가 발생할 것 같아 방식을 바꾸었다.i ) 1부터 V1까지의 최단 거리 + V1부터부터 V2까지의 최단 거리 + V2부터 N까지의 최단 거리ii ) 1부터 V2까지의 최단 거리 + V2부터부터 V1까지의 최단 거리 + V1부터 N까지의 최단 거리 중 더 작은 값이 최단 경로이고만일 경로가 없다면 초기에 설정해둔 INF 값보다 큰 값이 도출되므로 -1을 반환하면 된다. [코드]import java.io.BufferedReader;import java.io.IO..

https://www.acmicpc.net/problem/4803 [풀이과정]DFS 문제였다. 탐색을 하며 사이클이 존재하는지 여부를 체크하는 것이 중요.처음엔 이미 방문한 노드를 재방문했을 때 사이클이 발생한다고 했는데 여기서 오류가 생겼다.이미 방문한 노드 중엔 현재 주변을 탐색 중인 노드가 포함이었는데 이때는 제외했어야 했다. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;import java.util.ArrayList;public class Main { static BufferedReader br = new Buf..

음의 가중치가 없는 그래프의한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘 [시간복잡도]O((V+E)logV)이지만열결 그래프라면 O(ElogV)까지 줄일 수 있다.일반적으로는 우선순위 큐를 이용하는 것이 낫다고 한다. [매커니즘]1 ) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택2 ) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신 [초기화]A노드에서 A노드로 가는 가는 지점이 가장 짧다.라고 정의 [알고리즘 적용]방문하지 않은 노드 중 가장 비용이 적은 노드를 선택하며 값 갱

https://www.acmicpc.net/problem/11404 [문제풀이]플로이드 워셜 알고리즘 문제였다.플로이드 워셜 알고리즘이란 모든 정점에서 모든 정점까지의 최단 거리를 구하는 것으로,초기 그래프를 행과 열이 같은 곳을 제외하고 매우 큰 값으로 저장하여 최솟값으로 갱신하며 최단 거리를 찾는 알고리즘이다. 출력 할 때 INF으로 남은 값을 0으로 초기화해주어야 했는데 그 부분을 놓쳤다. 좀 더 꼼꼼하게 풀자!  [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*n개의 도시.한 도시에서 출발하여 다른 도시에 도착하는 m..