[알고리즘][X] 이모티콘

https://www.acmicpc.net/problem/14226

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

[백준]14226: 이모티콘 - JAVA