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

문제

14226번: 이모티콘

 

알고리즘

너비우선탐색 (BFS)

 

풀이

이모티콘 복사, 붙여넣기, 하나 삭제 모두 1초가 걸리므로 BFS를 이용해 세 연산을 하며 S 개에 도달했을 때 시간을 출력한다.

 

하지만 화면에 있는 이모티콘 수가 같더라도, 클립보드에 복사된 이모티콘 수가 다를 수 있다.

따라서 큐에 현재 화면에 있는 이모티콘 수, 걸린 시간 뿐만 아니라 클립보드의 이모티콘 수도 저장해야하며

방문 체크를 위한 배열 또한 visited[화면에 있는 이모티콘 수][클립보드의 이모티콘 수] 형태의 2차원으로 관리한다.

 

큐에 삽입할 객체 정보는 다음과 같다.

static class Status {
	int value, clip, time;

	public Status(int value, int clipNum, int time) {
		this.value = value;
		this.clip = clipNum;
		this.time = time;
	}
}

---

 

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장

화면에 있는 이모티콘 수는 동일하지만,

클립보드에 있는 이모티콘 수가 화면에 있는 이모티콘 수로 변하고, 시간이 1 증가한다.

if (cur.value != cur.clip) {
	queue.add(new Status(cur.value, cur.value, cur.time + 1));
}

 

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기

 

화면에 있는 이모티콘 수가 클립보드 수많큼 증가하고, 시간이 1 증가한다.

if (cur.value + cur.clip <= MAX_SIZE && !visited[cur.value + cur.clip][cur.clip]) {
	visited[cur.value + cur.clip][cur.clip] = true;
	queue.add(new Status(cur.value + cur.clip, cur.clip, cur.time + 1));
}

 

3. 화면에 있는 이모티콘 중 하나를 삭제한다.

화면에 있는 이모티콘 수가 1 감소하고, 시간이 1 증가한다.

if (cur.value - 1 >= 0 && !visited[cur.value - 1][cur.clip]) {
	visited[cur.value - 1][cur.clip] = true;
	queue.add(new Status(cur.value - 1, cur.clip, cur.time + 1));
}

 

* S가 최소 2이며, 1부터 시작한 이모티콘 수를 증가시키려면 반드시 복사를 해야하므로

복사한 상태에서 시작하면 "클립보드가 비어있는 상태에는 붙여넣기를 할 수 없다"는 조건을 신경쓰지 않아도 된다. (queue.add(new Status(1, 1, 1)))

 

코드

package baekjoon.m12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_14226 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final int MAX_SIZE = 1_000;

		int S = Integer.parseInt(br.readLine());
		boolean[][] visited = new boolean[MAX_SIZE * 2 + 1][MAX_SIZE * 2 + 1];

		Queue<Status> queue = new LinkedList<>();
		queue.add(new Status(1, 1, 1));
		visited[1][1] = true;
		
		while (!queue.isEmpty()) {
			Status cur = queue.poll();

			if(cur.value == S) {
				System.out.println(cur.time);
				break;
			}
			
			if (cur.value != cur.clip) {
				queue.add(new Status(cur.value, cur.value, cur.time + 1));
			}

			if (cur.value + cur.clip <= MAX_SIZE && !visited[cur.value + cur.clip][cur.clip]) {
				visited[cur.value + cur.clip][cur.clip] = true;
				queue.add(new Status(cur.value + cur.clip, cur.clip, cur.time + 1));
			}

			if (cur.value - 1 >= 0 && !visited[cur.value - 1][cur.clip]) {
				visited[cur.value - 1][cur.clip] = true;
				queue.add(new Status(cur.value - 1, cur.clip, cur.time + 1));
			}
		}
	}

	static class Status {
		int value, clip, time;

		public Status(int value, int clipNum, int time) {
			this.value = value;
			this.clip = clipNum;
			this.time = time;
		}
	}
}