풀이 방법
2배로 갈때와 1칸 이동할때 가중치가 다르다고 생각해서 다익스트라 알고리즘을 사용해서 풀어야 겠다고 생각했다.
Node에 위치와 그 위치에 도달할 때 1초가 걸리는 지 0초가 걸리는지 넣어주었다. 위치에 도달하기 위해 걸리는 총 시간은 sec배열에 넣어서 구현했다.
풀다보니 BFS로도 가능할거 같다는 생각이 들어서 BFS로도 풀어보았다.
BFS에선 Node에 sec를 그 위치에 걸리는 총 시간을 넣어서 sec 배열을 사용하지 않았다.
가중치가 다르긴 하지만 규칙이 있는 가중치라서 BFS로도 가능하게 풀이된 것으로 보인다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
class Node {
private int N;
private int sec;
public Node(int n, int sec) {
N = n;
this.sec = sec;
}
public int getSec() {
return sec;
}
public int getN() {
return N;
}
}
public class Main {
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 K = Integer.parseInt(st.nextToken());
int sec = 0;
Boolean[] visited = new Boolean[100001];
Arrays.fill(visited, false);
Queue<Node> q = new LinkedList<>();
Node node = new Node(N, 0);
q.offer(node);
visited[N] = true;
while (!q.isEmpty()) {
node = q.poll();
N = node.getN();
sec = node.getSec();
if (N == K) {
System.out.println(sec);
return;
}
if (N * 2 <= 100000 && !visited[N * 2]) {
q.offer(new Node(N * 2, sec));
visited[N * 2] = true;
}
if (N - 1 >= 0 && !visited[N - 1]) {
q.offer(new Node(N - 1, sec + 1));
visited[N - 1] = true;
}
if (N + 1 <= 100000 && !visited[N + 1]) {
q.offer(new Node(N + 1, sec + 1));
visited[N + 1] = true;
}
}
}
}
import java.io.*;
import java.sql.Array;
import java.util.*;
class Node implements Comparable<Node> {
private int N;
private int sec;
public Node(int n, int sec) {
N = n;
this.sec = sec;
}
public int getSec() {
return sec;
}
public int getN() {
return N;
}
@Override
public int compareTo(Node other) {
if (this.sec < other.sec)
return -1;
return 1;
}
}
public class Main {
static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
static Boolean[] visited = new Boolean[100001];
static int[] sec = new int[100001];
static int K, N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
Arrays.fill(visited, false);
Arrays.fill(sec, (int) 1e9);
for (int i = 0; i <= 100000; i++) {
graph.add(new ArrayList<Node>());
}
for (int i = 0; i <= 100000; i++) {
if (i != 0 && i * 2 <= 100000)
graph.get(i).add(new Node(i * 2, 0));
if (i + 1 <= 100000)
graph.get(i).add(new Node(i + 1, 1));
if (i - 1 >= 0)
graph.get(i).add(new Node(i - 1, 1));
}
dijkstra(N);
System.out.println(sec[K]);
}
public static void dijkstra(int N) {
PriorityQueue<Node> q = new PriorityQueue<>();
q.offer(new Node(N, 0));
sec[N] = 0;
while (!q.isEmpty()) {
Node node = q.poll();
int index = node.getN();
if (visited[index])
continue;
visited[index] = true;
for (int i = 0; i < graph.get(index).size(); i++) {
int x = sec[index] + graph.get(index).get(i).getSec();
if (x < sec[graph.get(index).get(i).getN()]) {
sec[graph.get(index).get(i).getN()] = x;
q.offer(new Node(graph.get(index).get(i).getN(), x));
}
}
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
뒤집기 II - 1455번 (0) | 2021.10.04 |
---|---|
알바생 강호 - 1758번 (0) | 2021.10.04 |
DFS와 BFS - 1260번 (0) | 2021.10.02 |
저울 - 10159번 (0) | 2021.10.01 |
백도어 - 17396번 (0) | 2021.10.01 |