[코드트리] 화면에 출력 (BFS) - JAVA

알고리즘 스터디 - BFS

https://www.codetree.ai/training-field/search/problems/output-to-screen/description?page=1&pageSize=20&tags=BFS&order=tier

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

# 문제

 

# 예제

입력

2

 

출력

2

 

 

# 필요개념

이 문제처럼 연산 수가 필요할 때에는 큐에 넣는 객체에 연산개수를 포함시켜야 한다. 그래서 화면 문자수, 클립보드 문자수, 연산 수를 담은 배열을 만들어 큐에 넣어주었다.

 

가장 고민이 되었던 부분은 방문여부 배열을 어떻게 만들어야하는가에 대한 부분이었다. 요구하는 최대 문자 수는 1000개이기 때문에 1001 x 1001 크기의 배열을 만들었다.

 

이차원배열은 arr[i][j] 형태가 되는데 이때 i자리에는 화면에 있는 문자 개수, j자리에는 클립보드에 있는 문자 개수를 넣어 방문여부를 확인할 수 있도록 하였다.

 

이 부분 외에는 다른 bfs 문제들과 크게 다른 게 없었다!

 

 

# Code

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

public class Main {

    static int goal;
    static Queue<int[]> queue = new LinkedList<>();
    static boolean[][] isVisited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        goal = Integer.parseInt(br.readLine());
        System.out.println(bfs());
    }

    public static int bfs() {
        queue.add(new int[] {1, 0, 0}); // 화면문자수, 클립보드문자수, 연산수
        isVisited = new boolean[1001][1001];
        isVisited[1][0] = true; // [화면문자수][클립보드 문자수]로 채워넣기

        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            int screen = now[0];
            int clipboard = now[1];
            int count = now[2];

            if (screen == goal) return count;

            // 복사 연산
            if (screen > 0 && !isVisited[screen][screen]) { // 복사하면 화면문자수 == 클립보드 문자수
                isVisited[screen][screen] = true;
                queue.add(new int[] {screen, screen, count + 1});
            }

            // 붙여넣기 연산
            if (clipboard > 0 && screen + clipboard <= 1000 && !isVisited[screen + clipboard][clipboard]) {
                isVisited[screen + clipboard][clipboard] = true;
                queue.add(new int[] {screen + clipboard, clipboard, count + 1});
            }

            // 삭제 연산
            if (screen > 1 && !isVisited[screen - 1][clipboard]) {
                isVisited[screen - 1][clipboard] = true;
                queue.add(new int[] {screen - 1, clipboard, count + 1});
            }
        }
        return -1;
    }
}

 

# 결과