[알고리즘][X] 이모티콘
2024. 1. 21. 17:10ㆍ알고리즘 풀이/Java
https://www.acmicpc.net/problem/14226
참고해서 푼 풀이
- Queue interface의 구현체로 LinkedList가 있다는 사실을 알게 되었다.
- Queue interface의 사용법(add, offer, remove, poll)을 배웠다. remove는 error throw하지만 poll은 하지 않는다.
- 중요한 건 알고 있는 알고리즘을 어떻게 문제에 적용하는가이냐를 배웠다.
- bfs에 visited 개념이 들어간다. 안들어가면 빙빙 돌기 때문이다. 여기서 기초가 중요하다는 것을 배웠다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int S = scanner.nextInt();
int minTime = bfs(S);
System.out.println(minTime);
}
private static int bfs(int S) {
boolean[][] visited = new boolean[1001][1001];
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(0, 1, 0));
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.total == S) {
return node.time;
}
if (!visited[node.total][node.total]) {
queue.offer(new Node(node.total, node.total, node.time + 1));
visited[node.total][node.total] = true;
}
if (node.clipBoard != 0 && node.total + node.clipBoard <= S && !visited[node.clipBoard][
node.total + node.clipBoard]) {
queue.offer(new Node(node.clipBoard, node.total + node.clipBoard, node.time + 1));
visited[node.clipBoard][node.total + node.clipBoard] = true;
}
if (node.total >= 1 && !visited[node.clipBoard][node.total - 1]) {
queue.offer(new Node(node.clipBoard, node.total - 1, node.time + 1));
visited[node.clipBoard][node.total - 1] = true;
}
}
return -1;
}
private static class Node {
int clipBoard;
int total;
int time;
public Node(int clipBoard, int total, int time) {
this.clipBoard = clipBoard;
this.total = total;
this.time = time;
}
}
}
Reference
https://moonsbeen.tistory.com/236
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘][X] 숨바꼭질 (0) | 2024.01.23 |
---|---|
[알고리즘][X] 배열 복원하기 (1) | 2024.01.23 |
[알고리즘] 소용돌이 예쁘게 출력하기 (0) | 2024.01.19 |
[알고리즘] 창용 마을 무리의 개수 (1) | 2024.01.07 |
[알고리즘] 숫자 배열 회전 (0) | 2024.01.01 |