숨바꼭질 1679번
내가 떠올린 풀이 해설
BFS를 응용해서 푸는 문제였다. BFS()를 호출한 후 BFS에서 arr 배열을 최대 크기 배열로 생성한 후 Queue에 n을 add한다. Queue가 비어있을 때까지 반복한다. now 값에 Queue에서 poll 한 값을 대입하고 for문을 i가 3보다 작을 때까지 반복한다. 1초 후에 now - 1, now + 1, now * 2로 움직여야한다. 만약 next가 k와 같다면 arr[now]를 리턴해준다. 또한 만약 next가 0보다 크거나 같고 next가 100001보다 작아야하고 arr[next]가 0일 때 arr[next]에 arr[now] + 1을 대입한다. 그리고 Queue에 next를 add한다.
정확한 풀이
import java.util.*;
public class Baek1697 {
static int n;
static int k;
static int[] arr;
static Queue<Integer> que = new LinkedList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
if (n >= k) {
System.out.println(n - k);
} else {
System.out.println(BFS());
}
}
private static int BFS() {
arr = new int[100001];
que.add(n);
arr[n] = 1;
while(!que.isEmpty()) {
int now = que.poll();
for(int i = 0; i < 3; i++) {
int next;
if (i == 0) {
next = now - 1;
}
else if (i == 1) {
next = now + 1;
}
else {
next = now * 2;
}
if (next == k) {
return arr[now];
}
if (next >= 0 && next < 100001 && arr[next] == 0) {
arr[next] = arr[now] + 1;
que.add(next);
}
}
}
return 0;
}
}
파티 1238번
내가 떠올린 풀이 해설
이 문제를 푸는데 시간이 오래 걸렸다. 다익스트라에서 조금만 응용하면 되는 문제였다. 1~N을 출발점으로 파티 마을 X까지의 거리를 다익스트라로 구한다. 그리고 반대로 파티 마을 X를 출발점으로 다익스트라를 돌려서 각 마을까지의 거리를 구했다. 그리고 이 두 값을 마을마다 더해주면 오고 가는 거리가 나오는데 이 값들 중 최댓값을 구하면 된다. time 배열은 파티 마을까지 오고 가는 거리의 값이다. 1~N 마을을 출발지로 다익스트라를 돌린 후 X까지의 거리를 time에 더해준다. 그 후 X를 출발지로 각 마을까지 거리를 구하여 time에 더해준다. 그 이후 time의 값들 중 최대값을 출력한다. 그 다음 dijkstra를 호출하고 다익스트라 메서드에서 우선순위 큐에 시작 정점을 넣어준다. 시작 지점의 가중치는 0이다. visit, distance를 초기화하고 distance에는 -1을 넣어준다. 우선순위 큐가 빌 때까지 while문을 반복한다. 현재 정점에 방문하지 않았을 때 연결된 정점들에 대해 검사를 시작한다. 연결된 정점의 가중치가 -1이거나 연결된 정점의 가중치가 현재 정점의 가중치와 현재 간선의 가중치의 합보다 클 때 값을 업데이트한다. 업데이트 후 다음 정점을 우선순위 큐에 넣어준다. Circle 클래스는 정점의 번호와 가중치를 가진다. 우선순위 큐의 타입으로 이용하기 위해 Comparable을 implements 해준다. 정렬 기준은 가중치의 오름차순이다.
참고 블로그
https://jellyinghead.tistory.com/79
[백준 1238] 파티 (자바)
난이도 : 골드 3 다익스트라 알고리즘을 이용해 풀었습니다. 2020/11/02 - [문제풀이/자바] - [백준 1753] 최단경로 (자바) [백준 1753] 최단경로 (자바) https://www.acmicpc.net/problem/1753 1753번: 최단경로..
jellyinghead.tistory.com
정확한 풀이
import java.util.*;
import java.io.*;
public class Baek1238 {
static int[] distance;
static boolean[] visit;
static ArrayList<Circle>[] list;
static PriorityQueue<Circle> que = new PriorityQueue<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
visit = new boolean[n + 1];
list = new ArrayList[n + 1];
distance = new int[n + 1];
for(int i = 1; i <= n; i++) {
list[i] = new ArrayList<Circle>();
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
list[u].add(new Circle(v, w));
}
int time[] = new int[n+1];
for(int i = 1; i <= n; i++) {
dijkstra(i);
time[i] += distance[x];
}
dijkstra(x);
for(int i = 1; i <= n; i++)
time[i] += distance[i];
int max = 0;
for(int i = 1; i <= n; i++)
max = Math.max(max, time[i]);
System.out.println(max);
}
private static void dijkstra(int x) {
que.offer(new Circle(x, 0));
visit = new boolean[visit.length];
distance = new int[distance.length];
Arrays.fill(distance, -1);
distance[x] = 0;
while(!que.isEmpty()) {
Circle current = que.poll();
int c_v = current.vertex;
if(visit[c_v]) {
continue;
}
visit[c_v] = true;
for(int i = 0; i < list[c_v].size(); i++) {
Circle tmp = list[c_v].get(i);
int next = tmp.vertex;
int value = tmp.value;
if(distance[next] == -1 || distance[next] > distance[c_v] + value) {
distance[next] = distance[c_v] + value;
que.add(new Circle(next, distance[next]));
}
}
}
}
}
class Circle implements Comparable<Circle> {
int vertex, value;
Circle(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
@Override
public int compareTo(Circle o) {
return value - o.value;
}
}
오늘의 회고
오늘은 BFS와 다익스트라 문제를 풀었습니다. 두 문제 모두 조금만 응용해서 푸는 문제였고, 너무 오랫만에 BFS와 다익스트라 문제를 풀어서 시간이 오래걸렸습니다. 다른 개념들도 까먹지않게 여러 개념의 문제들을 풀어야할 것 같습니다. 조금만 화이팅하자
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| 백준) DP, DFS (0) | 2022.08.27 |
|---|---|
| 백준) HashMap (0) | 2022.07.23 |
| 백준) 우선순위 큐, DP (0) | 2022.07.18 |
| 백준) 수학(피타고라스), 이분 탐색 (0) | 2022.07.16 |
| 백준) 수학, 이분 탐색 (0) | 2022.07.13 |
