[백준] 14226번 이모티콘 (Java)

백준 14226 이모티콘

BFS를 활용한 문제다. BFS 탐색이기 때문에 먼저 방문했던 노드가 비용이 더 적을 수 밖에 없다. 즉, DP 리스트가 아니라 방문했던 노드인지만 확인하면 된다. 같은 값을 방문했더라도 값을 복사한 경우는 시간이 1초 증가하기 때문에 방문한 노드와 현재 복사된 값까지 고려해서 boolean 배열을 만들어야 한다.

1. BFS 탐색이기 때문에 한 번 방문했던 노드를 다시 방문하는 것은 최솟값이 될 수 없다.
2. 현재 값이 target보다 크다면 붙여넣거나, 1을 더할 필요가 없다.
3. 값이 같아도 복사한 값이 다르다면 다른 경우로 보아야 한다.

• taget을 만나면 값을 출력하고 프로그램 종료
• 방문했는지 확인할 boolean 2차원 배열 isVisit

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        try {
            int n;
            int [] tmp;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            Queue <int[]> q = new LinkedList<>();
            n = Integer.parseInt(br.readLine());
            boolean [][]isVisit = new boolean [1025][1025];
            
            q.add(new int[] {1, 0, 0});
            
            // BFS
            while(!q.isEmpty()){
                tmp = q.poll();
                // 종료
                if(tmp[0] == n){
                    System.out.println(tmp[2]);
                    System.exit(0);
                } else {
                    if(tmp[0] < n){
                        if (tmp[1] != tmp[0] && !isVisit[tmp[0]][tmp[0]]){
                            q.add(new int [] {tmp[0], tmp[0], tmp[2] + 1});
                            isVisit[tmp[0]][tmp[0]] = true;
                        }
                        if(tmp[0] + tmp[1] <= 1024 && tmp[1] != 0 && !isVisit[tmp[0] + tmp[1]][tmp[1]]){
                            q.add(new int [] {tmp[0] + tmp[1], tmp[1], tmp[2] + 1});
                        }
                    }
                    if (tmp[0] - 1 > 2 && !isVisit[tmp[0] - 1][tmp[1]]){
                        q.add(new int [] {tmp[0] - 1, tmp[1], tmp[2] + 1});
                        isVisit[tmp[0] - 1][tmp[1]] = true;
                    }
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}