https://www.acmicpc.net/problem/17485 접근법DFS기존에 접근했던 방식은 DFS, 백트래킹을 사용하여 문제를 풀이했다. 하지만, 문제에서 주어진 방향은 3개고, N과 M의 최댓값이 1,000이기 때문에 최악의 케이스엔 3^(1000*1000)이 나오기 때문에 당연히 시간초과가 발생한다. 엠로 코테에서도 3^(200*200)이 나왔기 때문에 시초가 발생할 것이다. DP다른 사람들의 풀이를 보면, DP를 사용하여 풀이하였다.DP[i][j][n]: (i,j)위치에서 n방향으로 도달했을 때의 최소 비용n = 0 (왼쪽 아래 방향)n = 1 (바로 위)n = 2 (오른쪽 아래 방향)  이 그림을 보면, 5로 도달하는데 3가지 케이스가 있음을 알 수 있다.그리고 중요한 조건이 우주선은 ..

boj 7576 토마토BFS를 여러 지점에서 돌려야 할 때를 어떻게 할것인가?배열에서 익은 토마토에 해당하는 좌표에서 BFS를 돌렸더니 최소 일수를 구할 수 없었다. BFS 특성 상 한 좌표에서 시작해 끝까지 돌기 때문이다. 따라서, 익은 토마토에 해당하는 좌표를 모두 큐에 넣고 한번에 돌려준다면 동시에 BFS를 돌려서 최소 일수를 구할 수 있다. boj 7579 토마토3차원 배열에서의 BFS?상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수이렇게 주어질 때,board = new int[h][n][m];형태가 되어야 할 것이다.나머지 로직은 앞의 토마토 문제와 동일하다.

https://www.acmicpc.net/problem/2531 문제 유형슬라이딩 윈도우투 포인터 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class boj2531 { static int n, d, k, c; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer s..

https://www.acmicpc.net/problem/11000 문제 유형정렬우선순위 큐 풀이import java.io.*;import java.util.*;public class boj11000 { static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); PriorityQueue pq = new PriorityQueue((a,b) -> { if (a[0] == b..

https://www.acmicpc.net/problem/14889 문제 유형브루트 포스 백트래킹 풀이public class boj14889 { static int n; static int [][] board; static boolean [] visited; static int res = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); board = ne..

https://www.acmicpc.net/problem/2922 문제 유형브루트 포스백트래킹 풀이public class boj2922 { static long res = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine(); dfs(0, 0, 0, input.contains("L"), input, 1); System.out.println(res); } public static void dfs(..

https://www.acmicpc.net/problem/14620 문제 유형브루트포스백트래킹 코드 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class boj14620 { static int n; static int [][] board; static boolean[][] visited; static int[] dx = {1, 0, -1, 0, 0}; static int[] dy = {0, 1, 0, -1, 0}; static int res = Integer.MAX_VALUE; p..

https://www.acmicpc.net/problem/17179  문제생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤 케이크를 준비했다. 롤 케이크에는 장식이 존재해서 특정 위치에서만 자를 수 있다. 주성이는 롤 케이크 조각을 파티에 올 친구의 수 만큼 준비하고 싶어서, 가장 작은 조각의 크기를 미리 알아보기로 했다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 그래서 몇 개의 수를 목록에 적어, 각 수만큼 조각을 만들었을 때 가장 작은 조각의 길이의 최댓값을 구하려고 한다.예를 들어 70cm의 롤 케이크에 자를 수 있는 지점이 5군데(10cm, 20cm, 35cm, 55cm, 60cm)가 있다고 하자...

https://www.acmicpc.net/problem/1976   사용 알고리즘DFS유니온 파인드 풀이 DFSimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;import java.util.StringTokenizer;public class Main { /* 1. 여행 계획 처음부터 BFS를 돌리면서 체크 */ static int n, m; static List> graph = n..

https://www.acmicpc.net/problem/1717 알고리즘 유형그래프유니온 파인드 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class boj1717 { static int n, m; static int [] parent; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..