[백준 알고리즘] Q14226 이모티콘

 

1. Java 구현

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        System.out.println(bfs(Integer.parseInt(new Scanner(System.in).nextLine())));
    }

    private static int bfs(final int s) {
        final Queue<Command> queue = new LinkedList<>();
        final boolean[][] visited = new boolean[1000 + 1][1000 + 1]; // [screen][board]
        queue.add(new Command(1, 0, 0));

        while(!queue.isEmpty()) {
            final Command command = queue.poll();

            if(command.screen == s) {
                return command.cnt;
            }

            if(command.board < 0 || command.screen < 0 || command.board >= visited.length || command.screen >= visited.length || visited[command.screen][command.board]) {
                continue;
            }

            visited[command.screen][command.board] = true;

            queue.add(new Command(command.screen, command.screen, command.cnt + 1));
            queue.add(new Command(command.screen + command.board, command.board, command.cnt + 1));
            queue.add(new Command(command.screen - 1, command.board, command.cnt + 1));
        }

        return 0;
    }

    private static class Command {
        private int screen;
        private int board;
        private int cnt;

        public Command(final int screen, final int board, final int cnt) {
            this.screen = screen;
            this.board = board;
            this.cnt = cnt;
        }
    }
}

2. 코드설명

이 문제 역시 BFS 를 이용해서 풀 수 있다. 그리고 BFS는 역시 Queue 자료구조를 써야한다.

이 문제에서 가장 어려운 것은 방문기록을 visited 를 이용해서 어떻게 처리할 것인가? 이다.

지금까지 풀어왔던 문제에서는 visited 를 boolean 1차원 배열을 이용했다. 왜냐면 방문을 통해 중복제거가 필요한 요소가 한개였기 때문이다.

그러나 여기서는 화면과 클립보드 두개를 함께 고려해야 한다. 그렇기 때문에 2차원 배열을 이용해야한다.

 

이 문제에서는 visted[화면][클립보드] 이것만 잘 정의해놓으면 어렵지 않는 문제이다!