알고리즘 (22) 썸네일형 리스트형 백준 - 10026번 적록색약 - java https://www.acmicpc.net/problem/10026 접근법 기본적인 bfs로 풀이함 그래프 자체를 두가지 버전으로 만들어서, 동일한 bfs탐색 함수를 각각 타게해서 출력시킴 처음에 메모리초과가 떠서 확인해보니 방문처리하는 시점 이 잘못되어있었다. 인접한 4방향을 탐색할 때, 그 즉시 방문처리를 해야 의미없이 queue에 offer하지 않게된다 소스 import java.io.*; import java.util.*; public class Main { static int N; static boolean[][] VISIT; static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public static void main(String[] args).. 백준 - 1753번 최단경로 - java https://www.acmicpc.net/problem/1753 접근법 최단경로를 다루고 음수의 가중치가 없으니 기본적인 다익스트라 알고리즘이용 그리고 우선순위 큐를 이용하여 가중치가 작은것 먼저 처리되게하여 시간 단축 소스 package dijkstra; import java.util.*; import java.io.*; public class B1753 { static int V; static int E; static ArrayList[] graph; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String.. 백준 - 1238번 파티 - java https://www.acmicpc.net/problem/1238 접근법 최단거리 문제이므로 다익스트라 알고리즘을 적용하면 좋다 기본적인 다익스트라 알고리즘을 적용해서 각각 시작지점별로 단방향을 적용해서 최소거리를 구한다 dist테이블이 완성되면, dist[i][x] + dist[x][i] 의 합으로 i -> x / x -> i 의 값을 계산한다 그 합 중 최대값을 출력하면 정답 소스 import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static ArrayList[] graph; static int[][] dist; public static void main(Stri.. 백준 - 2667번 단지번호붙이기 - java https://www.acmicpc.net/problem/2667 접근법 DFS나 BFS나 상관없이 가능해보임 1. 지도에서 1인데, 방문하지 않은 지점을 맞이하면 2. 그 Point부터 BFS 혹은 DFS 탐색 3. 방문할때마다 visit 배열 마킹해가며 해당 Point로 시작한 경우 단지의 크기를 count해줌 4. 함수의 return 값을 단지의 크기로 하고, 그 값을 자료구조에 담음 5. 출력할땐 정렬시키고 출력 소스 import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { s.. 백준 - 1260번 DFS와 BFS - java https://www.acmicpc.net/problem/1260 중요한 테스트 케이스 입력 3 2 1 1 3 2 1 출력 1 2 3 1 2 3 접근법 기본적인 DFS, BFS 풀려고 했는데, 기존에 주어진 간선 데이터를 정렬해줘야 원하는 순서대로 탐색이 이루어진다 for(int i = 0; i e[i][1]) { int temp = e[i][1]; e[i][1] = e[i][0]; e[i][0] = temp; } } 입력받은 간선을 먼저 앞에 값이 더 크다면 자리를 바꿔주고 Arrays.sort(e, (o1, o2) -> { if(o1[0] == o2[0]) return Integer.compare(o1[1], o2[1]); else return.. 백준 - 2805번 나무 자르기 - java https://www.acmicpc.net/problem/2805 더보기 추가적인 테스트 케이스 @paa0609 님 2 11 10 10 정답 : 4 3 1 1 2 2 정답 : 1 @wjsqjawns님 4 10 1 4 5 7 정답: 2 5 2000000000 900000000 900000000 900000000 900000000 900000000 정답: 500000000 1 1000000000 1000000000 정답: 0 1 1 1000000000 정답: 999999999 출처: https://joey09.tistory.com/113 [joie de vivre] 접근법 이분탐색으로 min = 0, max = 최대값으로 지정해놓고 반씩 잘라가며 탐색 범위가 크므로 변수를 int형으로 하면 오버플로우나서 에.. 이전 1 2 3 다음
