[백준/12851] 이모티콘 (골드 4) JAVA

package task.imoticon14226;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int target = Integer.parseInt(br.readLine());

        int result = BFS(target);
        System.out.println(result);


    }

    public static class Scenario {
        int count;
        int clipBoard;
        int time;

        public Scenario(int count, int clipBoard, int time) {
            this.count = count;
            this.clipBoard = clipBoard;
            this.time = time;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Scenario scenario = (Scenario) o;
            return count == scenario.count && clipBoard == scenario.clipBoard;
        }

        @Override
        public int hashCode() {
            return Objects.hash(count, clipBoard);
        }
    }

    public static int BFS(int target) {
        int start = 1;
        Set<Scenario> visited = new HashSet<>();
        Deque<Scenario> deque = new ArrayDeque<>();
        int error = -99;
        // 이모티콘 개수, 클립보드에 존재하는 수, time
        deque.offer(new Scenario(start,0,0));
        visited.add(new Scenario(start,0,0));

        while (!deque.isEmpty()) {
            Scenario poll = deque.poll();

            if (poll.count == target) {
                return poll.time;
            }

            // 조건 1 구현 : 화면에 있는 이모티콘 모두 복사해서 클립보드에 저장
            if (!visited.contains(new Scenario(poll.count, poll.count, poll.time+1)) ) {
                deque.offer(new Scenario(poll.count, poll.count, poll.time+1));
                visited.add(new Scenario(poll.count, poll.count, poll.time+1));
            }

            // 조건 2 구현 : 클립보드의 모든 이모티콘 화면으로
            if (!visited.contains(new Scenario(poll.count + poll.clipBoard, 0, poll.time+1)) &&
                    poll.count + poll.clipBoard < target + 2 && poll.clipBoard > 0) {
                deque.offer(new Scenario(poll.count + poll.clipBoard, poll.clipBoard, poll.time+1));
                visited.add(new Scenario(poll.count + poll.clipBoard, poll.clipBoard, poll.time+1));
            }

            // 조건 3 구현 : 화면에서 이모티콘 하나 빼기
            if (!visited.contains(new Scenario(poll.count-1, poll.clipBoard, poll.time+1)) && poll.count - 1 > 0 ) {
                deque.offer(new Scenario(poll.count-1, poll.clipBoard, poll.time+1));
                visited.add(new Scenario(poll.count-1, poll.clipBoard, poll.time+1));
            }

        }
        // 형식상 그냥 return 해놓음. 안될 경우에 대한 설명이 문제에는 없어서...
        return error;
    }
}

• hash & equals 개념을 잘 알아야한다. 일반 배열로 구현시 동등성체크(contains)에서 모두 false가 나올 것이다. List로 구현해도 좋다 -> 컬렉션은 해당 사항이 잘 구현되었을 테니 나의 경우는 따로 객체를 만들었다.(인텔리제이로 구현 10초컷 객체로 만들면 BFS 메서드에서 봤을 때 이해가 쉬운 코드가 된다.)

• 조건은 3가지다. 앞 경우로부터 자식 3개가 생성되는데 이는 조건부이다. 그러므로 일단 if를 때려박고 조건 통과시 deque, visited를 업데이트 하는 코드를 작성한다.

• 조건을 생각하자. 이모티콘 수는 음수가 될 수 없을 것이고, 이모티콘 수가 목표 수 + 1 보다 커지면 최적해에서 벗어난다. 해당 사항을 조건식에 잘 쓰면 이 문제는 끝이다.

• 간단한 주석을 잘 활용하자. 코드를 적다가 다시 되돌아볼 때 유용하다. 너무 장황하겐 말고.

• 중복을 제거한다는 개념에서 DP적인 개념이 사용된다. 중복제거를 하지 않을 경우 시간초과가 발생하므로 유의해서 풀자.

• 실제로 배열로 먼저 풀었다가 contains가 제대로 동작하지 않는 것을 알고 시나리오 클래스를 따로 만들어 진행했다. List로 하면 코드는 더 줄어들긴 할듯.(숏코딩이 목적은 아니니깐)