본문 바로가기

알고리즘/백준126

[Java] BOJ 1194번 달이 차오른다, 가자. 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 BFS와 비트마스킹을 사용하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public stati.. 2021. 5. 25.
[Java] BOJ 2887번 행성 터널 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 크루스칼 알고리즘을 이용해서 해결했습니다. 시간초과를 해결하기위해 우선 x축, y축, z축 각각 정렬을 시켜 간선리스트를 구한 후에 그 간선 리스트를 정렬하게 했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arr.. 2021. 5. 21.
[Java] BOJ 1916번 최소비용 구하기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 다익스트라를 사용하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.PriorityQueue; import java.ut.. 2021. 5. 21.
[Java] BOJ 12865번 평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 DP를 이용하여 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int N, K; public static int[][] objects;.. 2021. 5. 18.
[Java] BOJ 3190번 뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 문제에 주어진 조건에 맞추어 재귀 함수를 만들어 해결했습니다. 이때, 방향을 바꾸는 시간은 시작하고나서부터 X초가 지난 뒤라는 점을 주의해야 하고 뱀은 먼저 머리가 움직이고 꼬리가 움직인다는 점을 주의해야 합니다. 또한, 문제에서 1, 1부터 시작하는 점도 주의해야합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java... 2021. 5. 17.
[Java] BOJ 16930번 달리기 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net 풀이 출발점에서 도착지에 도착할 때까지 BFS를 수행하게 하여 해결했습니다. 이때, BFS를 수행할때, 최대 K개의 칸을 이동할 수 있으므로 1칸 ~ K개의 칸까지의 모든 경우를 전부 큐에 담에 BFS를 돌리게 해야 합니다. 또한, visited 배열을 Integer.MAX_VALUE 즉, 가장 큰 값으로 초기화하고 최솟값을 저장하기 때문에 이미 방문을 했더라도 방문 횟수가 더 크다면 중지시키고 작다면 방문을 할 수 있게 해주어야 합니다. 코드 impo.. 2021. 5. 16.

티스토리툴바