개발일지

4485번 이전 다익스트라 문제들은 인접 리스트를 사용하여 풀었지만 해당 문제는 인접 행렬을 사용하였다 // 인접 행렬과 최단 경로 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; public class baekjoon4485 { static int n; // 동굴의 크기 static int[][] graph; // 동굴 내 도둑 루피 정보를 담은 이차원 배열 static boolean[][] visited; // 방문 여부 확인 static int[] dx = {-1, 1, 0, 0};..

1939번 bfs와 이진 탐색을 함께 사용하는 문제이다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class baekjoon1939 { static int n; // 섬의 개수 (정점) static int m; // 다리의 개수 (간선) static boolean[] visited; // 방문 여부 체크 static ArrayList[] lists; // 인접리스트 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..

10282번 2번(a) 컴퓨터가 1번(b) 컴퓨터에 의존 = 1번(b) 컴퓨터가 감염되면 5초 후 2번(a) 컴퓨터도 감염 3번(a) 컴퓨터가 2번(b) 컴퓨터에 의존 = 2번(b) 컴퓨터가 감염되면 5초 후 3번(a) 컴퓨터도 감염 > 2번 컴퓨터가 해킹 당해 감염된다면 3번 컴퓨터도 감염된다 (1번 컴퓨터는 해당 없음) // 컴퓨터의 개수 = 정점의 개수 // 의존성의 개수 = 간선의 개수 // 의존성으로 감염되는데 걸리는 시간 = 가중치 // 단방향 : 컴퓨터 a가 b를 의존한다 > b가 감염되면 a도 감염된다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.u..

1327번 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class baekjoon1327 { static int n; // 순열의 개수 static int k; // 뒤집어야할 문자 개수 static char [] arr; // 순열에 들어가는 수 배열 static char [] copy; // 순열에 들어가는 수 배열을 복사한 배열 static String arr_str; // 순열에 들어가는 수 배열을 오름차순 정렬 후 문자열로 만든 것 static String copy_str; // 순열에 들어가는 수 배열을 문자열로 만든 것 pu..

최소 신장 트리 신장 트리는 그래프의 모든 정점을 연결하는 사이클이 없는 트리이다 최소 신장 트리는 신장 트리 중 정점들을 연결하는 간선들의 합이 최소가 되는 트리이다 최소 신장 트리를 구하는 알고리즘에는 프림 알고리즘과 크루스칼 알고리즘이 있다 프림 알고리즘 시작 정점을 기준으로 가장 작은 가중치를 가진 간선을 선택하여 트리를 확장 크루스칼 알고리즘 간선의 가중치를 기준으로 오름차순 정렬 후 가중치가 가장 작은 간선부터 선택하여 선택한 간선의 두 정점이 연결되어 있지 않으면 연결 1922번 프림 알고리즘은 다익스트라 알고리즘과 유사하다 // 모든 컴퓨터를 연결하는데 필요한 최소 비용 // n = 컴퓨터의 수 = 정점의 개수 // m = 연결할 수 있는 선의 수 = 간선의 개수 // 프림 알고리즘 사용 ..

1504번 INF의 값을 INTEGER.MAX_VALUE로 설정할 경우 더하는 과정에서 오버플로우가 발생하므로 주의해야 한다 // 정점의 개수 = n // 간선의 개수 = e // 1번 정점에서 n번 정점으로 최단 거리로 이동 (시작점 1) // 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동 가능 // 주어진 두 정점(v1, v2)을 반드시 거치면서 최단 경로로 이동 // (1번 > v1) + (v1 > v2) + (v2 > n번) // (1번 > v2) + (v2 > v1) + (v1 > n번) // 두 가지 경우를 모두 고려한 후 그 중 작은 값이 정답 // 경로가 없을 때에는 -1을 출력 import java.io.BufferedReader; import java.io.IOExcept..

7576번 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // 1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 들어있지 않음 // 보관 후 하루 지나면 익은 토마토의 상하좌우에 있는 익지 않은 토마토가 익는다 (bfs 사용) // 익은 토마토의 개수가 여러개인 경우도 있으므로 동시 출발 > 큐 사용 public class baekjoon7576 { // 이동할 4가지 방향 정의 (상하 / 좌우가 겹치지 않게) sta..

10026번 // 적록색약인 경우 초록색과 빨간색을 구분하지 못함 = 하나의 구역으로 본다 // 적록색약인 경우 dfs, 적록색약이 아닌 경우 dfs 나눠서 생각? import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class baekjoon10026 { static String [][] grid; // 색칠한 그림을 이차원 배열로 나타낸 것 static boolean [][] visited; // 방문 여부 static int n; // 이동할 4가지 방향 정의 (상하 / 좌우가 겹치지 않게) static int[] dx = {-1, 1, 0, 0}; static int[] d..

다익스트라 알고리즘 : 최단 경로 탐색 알고리즘 최단 거리는 여러 개의 최단 거리로 이루어져 있다 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다 ex) 1번 노드부터 다른 모든 노드로 가는 최단 시간 경로 1916번 // 도시의 개수 = 노드 개수 (n) // 버스의 개수 = 간선 개수 (m) // 비용 = 가중치 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.String..

10250번 나머지와 몫을 활용하는 문제로 나머지가 0이 될 때만 주의해주면 된다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Solution { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int test = Integer.parseInt(br.readLine()); StringBuilder sb = new ..