그래프 이론65 [백준] 16169: 수행 시간 - JAVA https://www.acmicpc.net/problem/16169 풀이컴퓨터마다 계급이 있어서 i번 컴퓨터가 동작하기 위해서는 i-1번 컴퓨터들이 먼저 동작을 해야한다. 위상정렬을 이용해 구현했다. 컴퓨터들의 정보를 저장하고, 계급의 오름차순으로 i번과 i+1을 연결시키는 연결리스트로 저장했다. 위상정렬을 위한 배열도 저장하여 이 값이 0인 것부터 큐에 넣어 처리해주었다. 메모리: 14148KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Computer { int idx; int rank; int speed; public Compu.. 2024. 5. 19. [백준] 1039: 교환 - JAVA https://www.acmicpc.net/problem/1039 풀이정수 N의 i번 위치와 j번 위치의 숫자를 바꿀 수 있다. 이 행위를 K번 반복할 때 최댓값을 구해야 한다. 위치를 바꿀 때 바꾼 수가 0으로 시작하면 안된다. n번 수행했을 때 나온 수를 방문처리 하기 위해 이차원 배열로 방문처리했다. bfs탐색을 통해 숫자와 바꾼 횟수를 저장해가면 진행했다. 메모리: 54616KB시간: 244ms언어: Java 11import java.io.*;import java.util.*;public class Main { static final int MAX = 1_000_001; static int answer; static class Node { int num; .. 2024. 5. 18. [백준] 2150: Strongly Connected Component - JAVA https://www.acmicpc.net/problem/2150 풀이SCC는 정점들의 부분집합이며, 그 부분집합에 들어있는 서로 다른 두 정점 u, v에 대해 u에서 v로 가는 경로, v에서 u로 가는 경로가 모두 존재하는 경우를 말한다. 간선의 정보가 주어질 때, SCC의 개수와 그 안의 정점들을 출력해야 한다. SCC를 구하는 방법으로 코사라주 알고리즘과 타잔 알고리즘이 있다. - 코사라주 알고리즘 방향 그래프, 역방향 그래프, 스택을 사용하여 SCC를 구한다. 방향 그래프와 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한다. 1. 방향 그래프의 모든 정점에 대해 dfs를 수행하여 끝나는 순서대로 스택에 삽입한다. 2. 아직 방문하지 않은 정점이 있는 경우 다시 DFS를 수행한다... 2024. 5. 18. [백준] 24042: 횡단보도 - JAVA https://www.acmicpc.net/problem/24042 풀이1 ~ N 까지 영역이 있고 각 영역을 잇는 횡단보도를 통해 건널 수 있다. M개의 횡단보도가 켜지는 순서대로 주어진다. 즉, 첫번째 횡단보도는 0, M, 2M... 시간에 켜지고, 두번쨰 횡단보도는 1, M + 1, 2M + 1... 시간에 켜진다. 켜지는 시간을 가중치로하여 다익스트라 알고리즘을 수행하면 된다. 현재 시간보다 다음 건널 횡단보도에 적힌 시간이 작다면 더 커질때까지 M을 더해야 한다. `long nextCost = curr.cost + ((next.cost - curr.cost) % M + M) % M + 1;` 위 식으로 계산할 수 있었다. 메모리: 222712KB시간: 1292ms언어: Java 11import.. 2024. 5. 18. [백준] 20160: 야쿠르트 아줌마 야쿠르트 주세요 - JAVA https://www.acmicpc.net/problem/20160 풀이야쿠르트 아줌마의 판매 경로 10개가 주어진다. 아줌마가 해당 위치에 도착하기 전에 가있어야 아쿠르트를 살 수 있다. 먼저 내 시작위치로부터 각 위치까지 얼마나 걸리는지 다익스트라를 통해 구했다. 야쿠르트 아줌마의 시간을 누적해가면서 경로대로 움직였다. 아줌마의 현재위치부터 다익스트라를 통해 다음 위치까지 시간을 구했고, 해당 시간이 `Integer.MAX_VALUE`이면 그 다음 위치를 보는 식으로 구현했다. `ans`를 갱신하여 정점의 번호가 가장 낮은 것이 정답. 메모리: 68732KB시간: 920ms언어: Java 11import java.util.*;import java.io.*;public class Main { s.. 2024. 5. 18. [백준] 2637: 장난감 조립 - JAVA https://www.acmicpc.net/problem/2637 풀이X, Y, K가 주어지는데 X를 만드는데 부품 Y가 K개 필요하다는 뜻이다. 다른 부품으로 만들어지지 않는 기본 부품이 몇개씩 필요한지 구하는 문제이다. 완제품의 번호는 N으로 주어져있다. 따라서, N부터 탐색하면 된다. 위상정렬을 이용했는데 X를 만드는데 Y가 필요하다면 Y의 위상정렬 배열에 +1해줬다. N부터 시작하여 연결된 부품의 위상을 빼가면서 0이 되면 큐에 추가하는 식으로 구현했다. 메모리: 15960KB시간: 148ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int from; i.. 2024. 5. 17. [프로그래머스] 블록 이동하기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이두 점의 좌표, 방향, 시간을 Node클래스에 담아서 진행했다. 방문처리는 가로를 0, 세로를 1로 놓고 3차원 배열로 처리했다. 이동했을 때 두 점이 모두 방문한 곳이라면 진행시키지 않았다. 귀찮은 구현문제였다. 메모리: 69MB시간: 5.70ms언어: Java 11import java.util.*;class Solution { static class Node { int x1.. 2024. 5. 17. [백준] 1189: 컴백홈 - JAVA https://www.acmicpc.net/problem/1189 풀이(R-1, 0)에서 (0, C-1)로 이동한다. T는 가지 못하는 부분이고, 한번 지나친 곳은 다시 방문하지 않는다. 이동거리가 K인 경우의 수를 구하는 문제이다. 따라서 방문처리를 하며 dfs탐색을 했다. 각각의 경우에 따른 방문처리가 서로 영향을 주어서는 안되기 때문이다. 이동 거리를 1씩 늘려가면서 다음 칸으로 이동했고, 이동 거리가 K가 됐을 때, 도착점에 도달하였을 때 사이클을 종료시켰다. 메모리: 14584KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[][] vector = { { 1, 0 }, { 0, 1.. 2024. 5. 17. [백준] 2668: 숫자고르기 - JAVA https://www.acmicpc.net/problem/2668 풀이사이클을 찾는 문제이다. `arr[i] -> arr[arr[i]]`이런식으로 뽑힌 정수를 인덱스로 하는 숫자를 다시 봐야한다. 처음 시작한 숫자와 같은 숫자가 나오면 사이클이 완성된다. dfs탐색을 통해 뽑힌 정수를 인덱스로 하여 탐색했고 처음 숫자가 나왔을 때 list에 넣었다. 메모리: 14216KB시간: 128ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[] arr; static ArrayList list; static boolean[] visit; public static void main(String[] ar.. 2024. 5. 17. [백준] 5972: 택배 배송 - JAVA https://www.acmicpc.net/problem/5972 풀이1부터 N까지 이동해야하는데 길마다 지불해야할 비용이 있다. 즉, 다익스트라 알고리즘을 이용해 최솟값을 구해준다. ArrayList로 연결된 지점과 비용을 저장하고 dist배열을 만들고 최댓값으로 초기화해준다. 현재칸과 연결된 칸의 비용을 보면서 dist[다음칸]이 (`dist[현재칸] + 비용`)보다 크다면 더 작은 비용으로 이동할 수 있다는 것이므로 갱신해준다. 메모리: 41024KB시간: 484ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node implements Comparable { int v; .. 2024. 5. 17. 이전 1 2 3 4 5 6 7 다음