백준 문제풀이(JAVA) 검색 결과

해당 글 26건

백준 1761번(JAVA) - 정점들의 거리

import java.util.*; import java.io.*; class Node { int v; int w; Node(int v, int w) { this.v=v; this.w=w; } } public class Main { public static ArrayList[] arr; public static int N; public static int[] Depth; // 깊이 public static int[][] parent;// parent[0][3] 은 3번 노드의 2의0승 부모, //parent[5][3]은 3번 노드의 2의 5승부모, 즉 32번째 부모 public static int[][] length;// length[5][3] 은 3번 노드부터 2의0승 부모까지의 길이 public st..
백준 문제풀이(JAVA)/트리 2023. 11. 4. 17:47

백준 13907번(JAVA)-세금

2차원 DP를 활용한 다익스트라 문제이 import java.util.*; import java.io.*; class Node implements Comparable { int v; int w; int c; Node(int v,int w,int c) { this.v=v; this.w=w; this.c=c; } public int compareTo(Node o) { return w-o.w; } } public class Main { public static int[][] dp; public static int N; public static int S; public static int D; public static void main(String[] args) throws IOException{ // TODO..
백준 문제풀이(JAVA)/다익스트라 2023. 9. 15. 19:59

백준 10217번(JAVA) - KCM Travel, 재채점 후 새로운 풀이

분명히 맞았던 문제인데 갑자기 재채점 되면서 시간초과로 틀렸다. 알고보니 어떤 분이 질문게시판에 예시로 어떤 입력을 보여주면서, 이걸로 하면은 대부분의 코드들이 시간초과가 나온다고 질문글을 올렸고(1년전) 그게 최근에 검토가되서 재채점이 된 것이다. 내 기억이 맞다면 이 문제는 꽤 많은 사람들이 맞춰가지고, 다익스트라 분류로 들어가면 상위권에 노출되던 문제였다. 그런데 재채점 후 저~~ 하위권으로 내려갔을 정도로 재채점 후 많은 분들이 틀렸다 그래서 내 다익스트라를 조금 더 다듬어봤다. import java.util.*; import java.io.*; class Node implements Comparable { int v; int c; int d; Node(int v,int c,int d) { thi..
백준 문제풀이(JAVA) 2023. 6. 19. 19:57

백준 1194번 달이 차오른다, 가자(JAVA)

비트연산, 비트마스킹과 문자만 좀 다룰 줄 알면 쉽게 풀 수 있는 BFS문제 출처 : https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net import java.util.*; import java.io.*; class Node { int y;//y좌표 int x;//x좌표 int count;//여태까지 움직인 횟수 int bit;//가지고 있는 열쇠 Node(int y,int x,int count,int bit) { t..
백준 문제풀이(JAVA)/그래프 탐색 2023. 3. 16. 21:04

백준 11559번-Puyo Puyo(JAVA)

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 개인적으론 골4보단 높아야된다고 생각한다. 골 2~3정도?? 중력으로 뿌요뿌요들이 떨어지는 부분은 스택으로 구현하였다. 한 열 을 기준으로 맨 위 행부터 탐색해서 만약 "." 이 아니라면 스택에 넣어준다. 그리고 그 부분은 "."으로 만들어준다. 그렇게 모든 행을 탐색하고 나서 맨 아래행부터 스택에서 pop을 시켜준다. import java.util.*; import ja..
백준 문제풀이(JAVA)/그래프 탐색 2023. 1. 27. 20:24

백준 16236번 -아기상어

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS이지만 신경써줘야 할게 많아서 까다로운 문제이다. 필자도 몇번의 시도끝에 풀었다. 많은 풀이들이 있지만 나는 나만의 방식으로 풀었다. 먹이의 최단거리는 어떻게 구했는가?? 우선순위 큐를 사용해서 count, y좌표 ,x 좌표 순서로 오름차순으로 정렬했다. 이렇게 되면 같은 거리일때 더 위쪽에 있고, 만약 같은 y좌표라면 더 왼쪽에 있는 좌표를 선택하게 될것이다. 처음 Node를 만들 ..
백준 문제풀이(JAVA)/그래프 탐색 2022. 11. 30. 20:25

백준 3176번(JAVA)

백준 문제중 11438번 LCA2가 있는데, 트리를 타고 올라갈때 한 칸 씩 올라가는게 아니라 2의N승씩 올라가는 빠른 LCA가 있다. 밑에 문제를 풀 줄 안다면 이번 3176번도 손 쉽게 풀 수있다. https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 빠른 LCA탐색 문제는 부모를 2의N승 부모를 저장한다. 예를들어 위 그림과 같은 트리가 있다고 가정해보자. 기존에는 바로 위의 부모만 저장했다. 그래서 ..
백준 문제풀이(JAVA)/트리 2022. 9. 25. 16:56