그래프 이론65 [백준] 25688: 빠른 무작위 숫자 탐색 - JAVA https://www.acmicpc.net/problem/25688 풀이1부터 6까지의 숫자를 모두 방문해야하는 문제였다. 비트연산을 이용해 방문한 숫자를 저장했다. 현재 마주친 숫자의 정보와 새로 만난 숫자를 or연산을 통해 하나라도 1이면 1로 되게 했다. 해당 정보를 들고 다음 칸으로 이동한다. 방문처리는 삼차원배열로하여 마주친 숫자까지 고려하여 처리했다. 메모리: 14236KB시간: 132ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int r; int c; int move; int key; public Node(int.. 2024. 5. 17. [프로그래머스] 미로탈출 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이미로를 탈출하는데 레버에 먼저 들리고 출구로 가야한다. 즉, 출발지 -> 레버, 레버 -> 출구 2차례 그래프 탐색으로 최솟값을 구하면 된다. bfs탐색을 통해 두 함수의 최솟값을 구해줬다. 메모리: 77.3MB시간: 0.42ms언어: Java 11import java.util.*;class Solution { static class Point { int r; i.. 2024. 5. 17. [백준] 23352: 방탈출 - JAVA https://www.acmicpc.net/problem/23352 풀이상하좌우로 움직일 수 있는데 가장 긴 경로의 시작과 끝의 합을 구해야 한다. N x M 배열을 입력받고, 0이 아니면 bfs탐색을 한다. bfs탐색할 때 경로의 시작값을 함께 파라미터로 넘겨 진행했다. 더이상 갈 곳이 없을 때 지금까지의 최장 길이와 비교하여 답을 갱신해주었다. 메모리: 268784KB시간: 568ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int r; int c; int dist; public Node(int r, int c, int dist) {.. 2024. 5. 17. [백준] 9370: 미확인 도착지 - JAVA https://www.acmicpc.net/problem/9370 풀이목적지까지 최단경로에 (g-h)나 (h-g) 도로를 거치는지 확인하는 문제이다. 목적지를 t, 출발지를 s라고 한다면 (s-t)의 거리가 (s-g) + (g-h) + (h-t), (s-h) + (h-g) + (g-t) 두 거리 중 작은 값과 같다면 g-h 도로를 지났다고 확인할 수 있다. 따라서 다익스트라 알고리즘을 사용하여 s부터의 거리 배열, g부터의 거리, h부터의 거리 3개의 배엻을 구한다. (s-t) 거리가 다른 두 거리 중 작은 값과 같다면 출력한다. 메모리: 63248KB시간: 676ms언어: Java 11import java.util.*;import java.io.*;public class Main { static.. 2024. 5. 17. [백준] 1956: 운동 - JAVA https://www.acmicpc.net/problem/1956 풀이v개의 정점과 e개의 간선이 주어진다. 출발점에서 다시 출발점으로 돌아오는 사이클이 있는지, 있다면 최솟값을 구하는 문제이다. 모든 정점에서 다른 모든 정점까지의 최단경로가 필요하다. -> 플로이드 워셜 알고리즘을 사용한다. 원래 알고있던 플로이드 워셜에서는 거리를 저장할 이차원배열을 만들고, 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화를 했었다. 하지만 이 문제에서는 자기 자신에서 자기 자신으로 돌아와야하므로 다른 값들과 마찬가지로 INF로 초기화하였다. 그리고나서 플로이드 워셜 알고리즘을 통해 i정점에서 k를 거쳐 j로 이동하는 최솟값을 갱신해주면 자기 자신으로 다시 돌아오는 거리도 갱신된다. `dist[i][i]` 중 .. 2024. 5. 17. [백준] 6087: 레이저 통신 - JAVA https://www.acmicpc.net/problem/6087 풀이목적지까지 가야하는데 방향전환을 하려면 거울을 써야한다. 거울을 최소로 쓰면서 목적지에 도달해야 한다. 거울을 쓴 개수가 적은것 부터 탐색하기 위해 우선순위큐를 사용했다. 방문처리를 쓴 거울의 개수로 하는 int 이차원배열로 했었는데 메모리초과가 발생했다. 삼차원배열로 방향까지 체크를 해서 어느 방향일때 최소인지 확인하였더니 해결됐다. 메모리: 15720KB시간: 172ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node implements Comparable { int r; int c; i.. 2024. 5. 17. [백준] 19238: 스타트 택시 - JAVA https://www.acmicpc.net/problem/19238 풀이빈칸과 벽이 있는 지도가 주어진다. 택시의 시작위치와 승객의 출발지와 도착지가 주어진다. 택시는 한칸 이동할 때 연료 1씩 소모하며, 승객을 태우고 이동하여 목적지에 도달하였다면 승객을 태우고 이동한 만큼의 2배 연료를 획득한다. 이동하는 중에 연료가 다 떨어지면 끝난다. bfs탐색을 통해 택시로부터 승객까지 최소 위치를 구했고, 다시 bfs탐색으로 승객을 목적지까지 이동시켰다. 택시가 승객에 도착하거나, 목적지에 도착했을 때, 연료 체크를 하여 도중에 0이 되었는지 확인했다. 메모리: 22748KB시간: 220ms언어: Java 11import java.util.*;import java.io.*;public class Main {.. 2024. 5. 16. [백준] 14461: 소가 길을 건너간 이유 7 - JAVA https://www.acmicpc.net/problem/14461 풀이격자로 이루어진 땅을 건너가야하는데 세칸을 이동할 때 마다 격자에 써있는 만큼의 풀을 먹어야 한다. 한칸을 이동할 때는 T만큼의 비용이 든다. 격자 칸마다 다른 가중치가 있다. 즉, 다익스트라를 이용해 문제를 풀면 된다. 3칸을 이동하는 방법은 ABA 처럼 갔던 칸에 다시 방문하는 방법이 있고, ABC처럼 다른 칸에 갈 수도 있다. 이러한 방법들을 적어보니 16가지가 된다. 이차원 배열로 만들어 사용했다.static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 3, 0 }, { -3, 0 }, { 0, 3 }, { 0, -3 }, { 2, 1 },.. 2024. 5. 16. [백준] 1525: 퍼즐 - JAVA https://www.acmicpc.net/problem/1525 풀이3x3 표의 퍼즐을 맞추는데 최소 이동 횟수를 구하는 문제였다. 빈칸은 0으로 주어지고 0의 상하좌우에 있는 숫자를 0위치로 이동시킨다. 0을 기준으로 상하좌우를 탐색하여 숫자를 바꿔주고, 그렇게 만들어진 배치를 방문처리하였다. 이때 방문처리를 String으로 하였는데, 메모리제한때문이었다. 숫자들을 이어붙여 String으로 만들었고, String의 indexOf 메서드를 이용하여 위치를 찾아 좌표를 구했다. Map에 String과 이동횟수를 저장하며 방문처리를 해줬고, "123456780"이 된다면 퍼즐의 완성이므로 Map에서 이동횟수를 꺼내어 출력했다. 메모리: 122456KB시간: 1048ms언어: Java 11import ja.. 2024. 5. 15. [백준] 14867: 물통 - JAVA https://www.acmicpc.net/problem/14867 풀이용량이 정해진 물통을 주어진 용량으로 맞춰야 한다. 할 수 있는 동작은 정해져있는데 1. 물통 x에 물을 가득 채운다. 2. 물통 x의 물을 모두 버린다. 3. 물통 x의 물을 물통 y에 붓는다. 위의 세가지를 통해 용량을 맞출 때 최소 작업 수를 구해야 한다. 두 개의 물통을 0, 0상태에서 시작하여 bfs탐색을 통해 정해진 양을 맞추면 return했다. 이때 방문처리를 하기 위해 class를 만들어 set으로 체크하였다. set의 contains 메서드를 이용할 때 객체의 경우 비교하기 위해서는 class에 equals와 hashcode를 오버라이드해야 했다. 이 점만 알고 있다면 크게 어려운 것 없는 문제였다. 메모리: 146.. 2024. 5. 14. 이전 1 2 3 4 5 6 7 다음