[BOJ - JAVA] 14226 - 이모티콘 (BFS)

# 주소

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

14226번: 이모티콘

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;
public class Main{
    static int n,m;
    static int[] arr;
    static boolean[] visit;
    static int time = 0;
    static int x;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[2001];
        visit = new boolean[2001];
        System.out.println(dfs(1));
    }
    public static int dfs(int x){
        Queue<Points> queue = new LinkedList<>();
        queue.offer(new Points(x,0, 0));
        visit[x] = true;
        while (!queue.isEmpty()) {
            Points now = queue.poll();
            if(n == now.x){
                return now.cnt;
            }
            if(now.x + now.state < 2001 && now.state != 0 && !visit[now.x + now.state]){
                queue.offer(new Points(now.x + now.state, now.cnt + 1, now.state));
                visit[now.x + now.state] = true;
            }
            if(now.x - 1 >= 0 && !visit[now.x-1]){
                queue.offer(new Points(now.x - 1, now.cnt+1, now.state));
                visit[now.x-1] = true;
            }
            if(true){
                queue.offer(new Points(now.x, now.cnt + 1, now.x));
            }
        }
        return 0;
    }
}
class Points{
    int x;
    int cnt;
    int state;
    Points(int x, int cnt, int state){
        this.x = x;
        this.cnt = cnt;
        this.state = state;
    }
}

처음에 제출한 저의 코드입니다.

예제에 있는 모든 입출력문은 통과하는데, 자꾸만 38%에서 멈추네요.

그래서 하... 뭐지.. 또 뭐가 문제지.. 하며 서칭을 하는 찰나 조금이나마 깨닫은게 있습니다..

어떤 점에 늦게 도착해도(정답이 아닌) 클립보드에 저장된 이모티콘의 수가 더 많으면 그게 더 빠를 수 있었습니다.

음... 직관적으로 이해하기 어렵죠??? 저도 그래요.

그러니까 클립보드에 따로 저장된 것이 무엇인지에 따라 1차원으로 풀지, 2차원으로 풀지 나뉘게 됩니다.

단순히 1,2,3번 순서에 따라 붙여넣기하고, 개수를 한개 차감하고, 몇 개 더하고 이런 문제였다면 1차원 visit배열로 풀면 쉽게 풀립니다만 1번 명령이 클립보드에 복사를 할 수 있다고 했으므로 클립보드의 상태에 따라 더 빠르게 정답 코드에 근접할 수 있다는 얘기입니다.

저도 얘기해놓고 무슨 얘긴지 모르겠어서 쉽게 정리하자면.. 1차원으로 풀기에는 함정이 많다!! 이렇게 생각해보도록 합시다.

(나중에 또 오면서 제가 썼던 코드 계속 복습해야겠어요. 난이도는 안높은데 배열을 2차원으로 나누어야 하는 근거에 대해 확실히 어렵게 받아들여지기도 하네요.)

 

그래서 정답을 제출할 땐

import java.awt.*;
import java.util.*;
public class Main{
    static int n,m;
    static int[] arr;
    static boolean[][] visit;
    static int time = 0;
    static int x;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[2001];
        visit = new boolean[2001][2001];
        System.out.println(dfs(1));
    }
    public static int dfs(int x){
        Queue<Points> queue = new LinkedList<>();
        queue.offer(new Points(x,0, 0));
        visit[x][1] = true;
        while (!queue.isEmpty()) {
            Points now = queue.poll();
            if(n == now.x){
                return now.cnt;
            }
            if(now.x + now.state < 2001 && now.state != 0 && !visit[now.x + now.state][now.state]){
                queue.offer(new Points(now.x + now.state, now.cnt + 1, now.state));
                visit[now.x + now.state][now.state] = true;
            }
            if(now.x - 1 >= 0 && !visit[now.x-1][now.state]){
                queue.offer(new Points(now.x - 1, now.cnt+1, now.state));
                visit[now.x-1][now.state] = true;
            }
            if(true){
                queue.offer(new Points(now.x, now.cnt + 1, now.x));
            }
        }
        return 0;
    }
}
class Points{
    int x;
    int cnt;
    int state;
    Points(int x, int cnt, int state){
        this.x = x;
        this.cnt = cnt;
        this.state = state;
    }
}

다음과 같이 제출해야 합니다.

Points라는 class를 따로 생성해서 제네릭에 받아오고 현재의 점 상태를 계속 변화시켜주면 되겠습니다...

감사합니다.