Dev.baelanche

빠른 시간이므로 BFS 로 접근해야한다. 시간이 지날때마다 사람의 이동, 불의 이동이 이루어지므로 큐를 따로 만들어 사용한다. 처음에는 사람 이동 -> 불 이동 순으로 구현했었는데 예제는 모두 통과하는데도 틀리다고 나왔다. 문제에 불이 옮겨옴과 동시에 이동할 수 있다는 구문을 보고 불 이동 -> 사람 이동 으로 순서를 바꾸었더니 통과했다. 불이 먼저 이동해서 사람 위치를 차지하면 사람이 안움직일줄 알았는데 이미 큐에 담겨있어서 움직일 수 있었다. # # . # # # # . # # 사람 사람 . 불 불 사람 # # # 불 사람 # # # 불 왜 틀렸는지에 대한 예제를 생각해냈다. 사람, 불은 빨간 위치에서 시작하고 현재 3칸씩 이동한 상황이다. 사람 -> 불 순으로 이동하면 사람이 (3, 3) 으로 이동..

최단 시간을 구해야하므로 BFS 로 접근한다. 지나갈 수 있는 길을 탐색하면 되는데 배열이 3차원이라는 데에 주의해야 한다. S . . . . # # # # # # # # # # . # # # . # # # # # # # # # # . # # . . # # . # # # . # # # # # # . # # # . . . # # # # E 예제로 풀이해보자. 왼쪽부터 1, 2, 3층이다. S . . . . # # # # # # # # # # . # # # . # # # # # # # # # # . # # . . # # . # # # . # # # # # # . # # # . . . # # # # E 한칸 이동했을때이다. 가까운 동서남북상하로 이동했다. S . . . . # # # # # # # # # # ..

dp 배열에 사탕의 최대값을 저장하면서 풀면된다. 1 2 3 4 0 0 0 5 9 8 7 6 오른쪽, 아래, 대각선으로 이동하므로 가장자리의 줄은 더해서 채워준다. 1 3 6 10 1 0 0 5 10 8 7 6 나머지 칸들은 [i-1][j-1], [i-1][j], [i][j-1] 중 최대값을 저장한다. 1 3 6 10 1 3 6 15 10 18 25 31 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int a[][] = new int[n][m]; int dp[][] = new int[n][m]; f..

BFS 로 인접노드 탐색을 하는 문제다. 나이트는 날일 자로 이동하기 때문에 이 부분만 기억하고 풀면된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); int mx[] = {-1, 1, 2, 2, 1, -1, -2, -2}; int my[] = {2, 2, 1, -1, -2, -2, -1, 1}; while(t-->0) { int l = sc.nextInt(); boolean visited[][] = new boolean[l][l]; int jump[][] = new int[l][l]; Queue q = new LinkedList(); ..

BFS 로 인접노드탐색을 하면 된다. DFS 로도 구현을 할 수는 있는데 노드 레벨 순서대로 타는 것이 아니기 때문에 시간이 너무 오래걸리게 된다. public class Main { static int n; static int m; static int a[][] = new int[100][100]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); for(int i=0; i

BFS 로 노드 a 에서 b 까지의 레벨을 구하는 문제이다. 너비 탐색 기법을 쓸 줄만 안다면 충분히 풀 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[][] = new int[101][101]; boolean visited[] = new boolean[101]; Queue q = new LinkedList(); int a = sc.nextInt(); int b = sc.nextInt(); int m = sc.nextInt(); while(m-->0) { int x = sc.nextInt(); int y = sc...

예제로 풀이해보겠다. a[0] a[1] a[2] a[3] a[4] a[5] 점수 10 20 15 25 10 20 점수 배열이다. a[0] a[1] a[2] a[3] a[4] a[5] 첫번째 경우 10 20 15 25 10 20 두번째 경우 10 20 15 25 10 20 마지막 계단은 반드시 밟아야 하므로 뒤에서 되돌아오는 식으로 점화식을 구현해야 한다. dp[5] = dp[2] + a[4] + a[5]; dp[5] = dp[3] + a[5]; 중 큰 값을 선택한다. 두번째 경우에서 a[1] 을 썼는지 a[2] 를 썼는지 확인할 수 없으므로 dp[3]만 사용한다. 식으로 나타내면 dp[i] = max(dp[i-3] + a[i-1] + a[i], dp[i-2] + a[i]); 가 되겠다. 이런식으로 구현하..

간단한 dp 문제이다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 아래 인덱스는 위에 인접해 있는 인덱스 중 큰것을 골라 더해간다. 7 3+7 8+7 8+3+7 1+8+7 0+8+7 2+8+3+7 7+8+3+7 4+1+8+7 4+1+8+7 4+2+8+3+7 5+7+8+3+7 2+7+8+3+7 6+4+1+8+7 5+4+1+8+7 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]; 점화식은 위와 같다. dp[i][0] 일때는 -1의 인덱스로 접근할 수 있으므로 이것만 유의하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ..