BFS로 최단 시간 구하기

백준 14226번을 BFS로 Java를 이용해 풀어봤다. 방문 여부 체크가 관건이었는데 솔직히 내 풀이가 왜 틀린 건지 잘 모르겠다...

다른 풀이들을 살펴보면 모두 방문 체크를 boolean[화면에 찍힌 개수][클립보드에 저장된 개수] 형태로 체크해준다. 나는 int[1001] 형태로 더 작은 방문시간 값이 나올 때마다 갱신해주는 형태로 했다.
서로 다른 형태로 해준 것 외에는 로직 자체는 동일한데 어째서 이차원 boolean배열로 해야하는지 잘 모르겠다. 왜 클립보드에 저장된 개수까지 고려한 이차원 배열을 사용해야 하는 것인지 고민해봤는데... 내 머리가 부족한 것인지 잘 모르겠다...

어쨌든 내 방식대로 어떻게든 맞혀보려고 한참 삽질하다가 결국 포기하고 그냥 이차원 boolean 배열로 방문체크 해줬더니 바로 맞기는 했다... 찝찝하다... ㅆ...

---

방문체크 여부를 서로 다르게 한 것만 제외하고는 로직 자체는 간단하다. 주어진 세 가지 연산을 수행하고 각 연산마다 큐에 넣어줄 조건을 만족시키면 큐에 추가해주고 주어진 입력값을 만나면 return해주면 된다.

복사 연산

이미 화면에 있는 개수와 클립 보드에 있는 개수가 동일하면 굳이 복사를 해줄 필요가 없다. 복사를 해도 되기는 하지만 그러면 최단 시간을 만족시키지 못하니 큐에 넣어줄 조건으로 부적절하다. 또한 visited[화면에 찍힌 개수][화면에 찍힌 개수] 가 이미 방문된 전력이 있다면 큐에 넣어줄 필요가 없다. 더 일찍이 누군가가 다녀간 것이기 때문이다.

/** 복사 */
      if(curScreen!=curClip && !visited[curScreen][curScreen]){
         q.add(new int[]{curScreen, curScreen, curTime + 1});
          visited[curScreen][curScreen] = true;
      }

붙여넣기 연산

붙여넣기를 하려면 일단 클립 보드에 뭔가 있어야 하니까 클립 보드가 비어있는지 확인해주고, 붙여넣기 할 경우에 화면에 찍힐 개수가 1000개 이하이며 방문 전적이 없으면 큐에 추가해주면 된다

/** 붙여넣기 */
      if (curClip!=0 && curScreen+curClip<1001 && !visited[curScreen+curClip][curClip]) { 
          q.add(new int[]{curClip + curScreen, curClip, curTime + 1});
          visited[curClip + curScreen][curClip] = true;
      }

삭제 연산

삭제를 하려면 적어도 화면에 1개 이상 남아야 있어야 하며, 방문 전적이 없으면 큐에 추가해주면 된다.

/** 삭제 */
      if (curScreen >= 1 && !visited[curScreen-1][curClip]) {
          q.add(new int[]{curScreen - 1, curClip, curTime + 1});
          visited[curScreen-1][curClip] = true;
      }

---

아래는 내가 제출한 코드다.

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

public class boj14226 {
    static int S,answer;
    static boolean[][] visited = new boolean[2002][2002];
    static Queue<int[]> q = new LinkedList<>();

    static void bfs(){
        q.add(new int[]{1,0,0});
        visited[1][0] = true;

        while(!q.isEmpty()){
            int size = q.size();

            for(int i=0; i<size; i++){
                int[] cur = q.poll();
                int curScreen = cur[0];
                int curClip = cur[1];
                int curTime = cur[2];

                if(curScreen==S) {
                    answer = curTime;
                    return;
                }

                /** 복사 */
                if(curScreen!=curClip && !visited[curScreen][curScreen]){
                    q.add(new int[]{curScreen, curScreen, curTime + 1});
                    visited[curScreen][curScreen] = true;
                }

                /** 붙여넣기 */
                if (curClip!=0 && curScreen+curClip<1001 && !visited[curScreen+curClip][curClip]) {
                    q.add(new int[]{curClip + curScreen, curClip, curTime + 1});
                    visited[curClip + curScreen][curClip] = true;
                }

                /** 삭제 */
                if (curScreen >= 1 && !visited[curScreen-1][curClip]) {
                    q.add(new int[]{curScreen - 1, curClip, curTime + 1});
                    visited[curScreen-1][curClip] = true;
                }
            }
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        S = Integer.parseInt(stk.nextToken());

        bfs();
        System.out.println(answer);
    }
}

내 풀이대로 다시 시도해봤지만 또 틀렸다...

오늘 배운 것

배운 거라고 하기에 애매하다. 왜 꼭 이차원 boolean으로 방문 체크 해줘야 했는지 잘 모르겠다. ㅆ