이-모티콘
백준 14226번 문제
https://www.acmicpc.net/problem/14226
14226번: 이모티콘
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만
www.acmicpc.net
1. 문제
2. 풀이
2.1 풀이 방법
주어진 조건에서 1초간 할 수 있는 일은 다음과 같이 3가지가 있다.
● 화면의 이모티콘을 복사해서 클립보드에 붙여 넣기
● 클립보드에 있는 이모티콘 화면에 붙이기
● 화면에 있는 이모티콘 1개 삭제하기
[노드와 분기]
screen은 화면에 나타나는 이모티콘의 개수,
clip은 클립보드에 저장된 이모티콘의 개수,
time은 해당 노드까지 걸리는 시간을 나타낸다.
각 노드는 위의 그림과 같이 주어진 조건하에 다음 노드로 이동할 수 있다.
특정 노드에서 연결된 노드로 이동하는 방법을 알았으니,
이제 다음과 같은 방법을 사용해서 문제의 답을 구할 수 있다.
1. [screen = 1, clip = 0, time = 0]에서 부터 시작해서 각 노드들을 BFS로 탐색한다.
2. 화면에 나타는 이모티콘의 개수가 target과 동일(screen = target)해지는 time을 반환한다.
(BFS로 탐색하기 때문에 가장 빨리 찾아진 노드가 가장 작은 time을 갖는다.)
※ screen과 clip이 같은 노드는 다시 탐색하지 않는다.
[중복 탐색]
위 그림과 같이 특정 screen과 clip을 갖는 노드(노란색)가 탐색되었다고 하자.
그 뒤에 탐색되는 동일한 screen과 clip을 가진 노드(빨간색)는 BFS 탐색 특성상 먼저 탐색된 노드보다 항상 큰 time을 갖는다.
또한 그 이후에 연결된 노드들도 중복된 행위를 반복하는 것이기 때문에 동일한 screen과 clip을 가진 노드가 탐색되었다면 그와 같은 노드를 탐색하는 것은 의미가 없다.
2.2 코드
2.2.1 Node
노드를 나타내는 클래스이다.
[Node]
public static class Node{
//해당 노드까지 걸리는 시간.
int time;
//클립보드에 저장된 이모티콘의 개수.
int clip;
//화면에 나타나는 이모티콘의 개수
int screen;
//노드가 탐색되었는지 판단하는 flag
boolean check = false;
public void setNode(int time, int clip, int screen) {
this.time = time;
this.clip = clip;
this.screen = screen;
this.check = true;
}
}
2.2.2 Main
[Main]
public static void main(String[] args) {
//초기화 시작
Scanner scanner = new Scanner(System.in);
int target = scanner.nextInt();
//항상 clip 또는 screen이 target보다 작은범위에서 답을 구할 수 있다.
int max = target + 1;
/*
[1]
row = clip, col = screen이라하고
해당 row,col(screen, clip)의 node가 탐색되었다면 탐색하지 않는다.
*/
Node[][] nodes = new Node[max][max];
for (int i = 0; i < max; i++) {
for (int j = 0; j < max; j++) {
nodes[i][j] = new Node();
}
}
//초기화 끝
System.out.println(bfs(nodes, target));
}[1] : 동일한 screen과 clip을 갖는 노드를 중복 탐색하지 않기 위해서 이차 배열을 사용한다.
배열의 row를 clip으로, col을 screen으로 보고 해당 위치의 Node가 (check = true) 되었으면 해당 screen과 clip을 갖는
노드가 탐색되었다고 판단한다.
[이차 배열을 사용한 중복 탐색 방지]
위 그림과 같이 row = 1, col = 2의 Node가 check 돼있다면 screen이 2이고 clip이 1인 노드가 탐색되었다고 판단한다.
그런데 이런 이차 배열을 만들 때 그 범위를 어떻게 잡는 것이 좋을까?
예를 들어 target이 15일 때, 이차 배열의 행과 열의 범위를 15로 한다면 이는 screen과 clip을 15까지만 탐색한다는 뜻이 된다.
여기서 이렇게 생각할 수 있다(내가 이렇게 생각함).
이모티콘은 복사-붙여 넣기 방식으로 늘릴 수 있으니 이모티콘을 2의 제곱수인 16으로 만들고 1을 빼면 제일 빠르지 않을까?
이차 배열의 범위를 15로 준다면 16을 탐색할 수없으니 제일 빨라질 수 있는 경우의 수를 탐색하지 못하는 게 아닐까?
이 의문은 screen이 target보다 더 커지는 경우에 답이 있을 수 있기 때문에 이차 배열의 범위를 target만큼 주면 안 되는 거 아닌가? 라고 일반화할 수 있다.
이에 대한 답은 "아니다" 이다.
이 문제에서 target을 만드는 모든 방법은 다음과 같이 표현할 수 있다.
target = screen + clip*x - y
즉, target은 특정 screen에 저장된 clip을 x번 더하고 y만큼 빼는 행위를 통해서 만들어진다.
이때 target을 만드는 시간은
(screen, clip)을 만드는 시간 + x초 + y초가 된다.
예를 들어 위의 이모티콘을 연속적으로 복사-붙여 넣기 해서 16 -> 15을 만드는 방법의 경우
15 = 8 + 8*1 - 1 => 화면의 이모티콘 8개에 클립보드 이모티콘 8개를 붙여서 16을 만들고 화면의 이모티콘을 1개 삭제
로 표현될 수 있다.
이때, 위의 방법으로 15를 만드는데 걸리는 총시간은
(screen = 8, clip = 8을 만드는 시간) + 1초 + 1초가 된다.
그런데 위의 식은 다음과 같이 볼 수 도 있다.
target = screen - y + clip*x
15 = 8 - 1 + 8*1 => 화면의 이모티콘 8개에서 1개를 삭제한 후 클립보드 이모티콘 8개를 붙이기
이에 걸리는 시간은
(screen = 8, clip = 8을 만드는 시간) + 1초 + 1초
위의 15(=target)를 초과해서 target에 가는 방법과 같은 식이기 때문에 당연하게도 걸리는 시간은 같다.
즉, target을 넘어가는 screen을 만든 뒤, 이모티콘을 한 개씩 빼는 것으로 target에 다가가는 방법이 있다면
항상 그와 동일한 시간이 걸리는, screen이 target을 넘어가지 않는 방법이 존재한다.
이 때문에 screen이 target을 넘어가는 경우에 답이 있는 있을 수 도 있다는 걱정을 하지 않아도 된다.
왜냐하면 항상 그와 동일한 시간이 걸리는, screen이 target을 넘어가지 않는 방법이 존재하기 때문이다.
따라서 screen이 target을 넘어가는 경우는 탐색할 필요가 없다.
clip > target의 경우도 이 부등식이 성립하려면 screen > target이 돼야 되기 때문에 clip이 target을 넘어가는 경우도 탐색할 필요가 없다.
따라서 Node의 중복 탐색을 판단하기 위한 이차 배열의 크기는 target이 된다.
2.2.3 bfs
BFS를 사용해서 node를 탐색하는 메서드, screen이 target과 같아지는 경우를 탐색하면 즉시 해당 노드의 time을 반환한다.
[BFS]
//bfs를 사용해서 node를 탐색하는 메서드,
//screen이 target과 같아지는 경우를 탐색하면 즉시 해당 노드의 time을 반환한다.
public static int bfs(Node[][] nodes, int target) {
Queue<Node> queue = new LinkedList<>();
nodes[0][1].setNode(0, 0, 1);
queue.offer(nodes[0][1]);
while (!queue.isEmpty()) {
Node node = queue.poll();
//다음 시간
int nextTime = node.time + 1;
//붙여넣어진 화면
int pastedScreen = node.screen + node.clip;
//복사된 클립보드
int copiedClip = node.screen;
//삭제된 화면
int deletedScreen = node.screen - 1;
//복사&저장
//복사된 clip이 이차배열의 크기보다 작거나, 해당 노드가 탐색되지 않았을 경우 시행한다.
if (copiedClip < nodes.length && !nodes[copiedClip][node.screen].check) {
nodes[copiedClip][node.screen].setNode(nextTime, copiedClip, node.screen);
queue.offer(nodes[copiedClip][node.screen]);
}
//붙여넣기
//붙여넣어진 screen이 이차배열의 크기보다 작거나, 해당 노드가 탐색되지 않았거나, clip에 이모티콘이 1개 이상일 경우 시행된다.
if (pastedScreen < nodes[0].length && !nodes[node.clip][pastedScreen].check && node.clip != 0) {
if (pastedScreen == target) {
return nextTime;
}
nodes[node.clip][pastedScreen].setNode(nextTime, node.clip, pastedScreen);
queue.offer(nodes[node.clip][pastedScreen]);
}
//삭제
//이모티콘이 삭제된 화면의 이모티콘이 0이상이거나, 해당 노드가 탐색되지 않았을 경우 시행한다.
if (deletedScreen >= 0 && !nodes[node.clip][deletedScreen].check) {
if (deletedScreen == target) {
return nextTime;
}
nodes[node.clip][deletedScreen].setNode(nextTime, node.clip, deletedScreen);
queue.offer(nodes[node.clip][deletedScreen]);
}
}
return -1;
}
3. 전체 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class 이모티콘_14226 {
public static class Node{
//해당 노드까지 걸리는 시간.
int time;
//클립보드에 저장된 이모티콘의 개수.
int clip;
//화면에 나타나는 이모티콘의 개수
int screen;
//노드가 탐색되었는지 판단하는 flag
boolean check = false;
public void setNode(int time, int clip, int screen) {
this.time = time;
this.clip = clip;
this.screen = screen;
this.check = true;
}
}
//bfs를 사용해서 node를 탐색하는 메서드,
//screen이 target과 같아지는 경우를 탐색하면 즉시 해당 노드의 time을 반환한다.
public static int bfs(Node[][] nodes, int target) {
Queue<Node> queue = new LinkedList<>();
nodes[0][1].setNode(0, 0, 1);
queue.offer(nodes[0][1]);
while (!queue.isEmpty()) {
Node node = queue.poll();
//다음 시간
int nextTime = node.time + 1;
//붙여넣어진 화면
int pastedScreen = node.screen + node.clip;
//복사된 클립보드
int copiedClip = node.screen;
//삭제된 화면
int deletedScreen = node.screen - 1;
//복사&저장
//복사된 clip이 이차배열의 크기보다 작거나, 해당 노드가 탐색되지 않았을 경우 시행한다.
if (copiedClip < nodes.length && !nodes[copiedClip][node.screen].check) {
nodes[copiedClip][node.screen].setNode(nextTime, copiedClip, node.screen);
queue.offer(nodes[copiedClip][node.screen]);
}
//붙여넣기
//붙여넣어진 screen이 이차배열의 크기보다 작거나, 해당 노드가 탐색되지 않았거나, clip에 이모티콘이 1개 이상일 경우 시행된다.
if (pastedScreen < nodes[0].length && !nodes[node.clip][pastedScreen].check && node.clip != 0) {
if (pastedScreen == target) {
return nextTime;
}
nodes[node.clip][pastedScreen].setNode(nextTime, node.clip, pastedScreen);
queue.offer(nodes[node.clip][pastedScreen]);
}
//삭제
//이모티콘이 삭제된 화면의 이모티콘이 0이상이거나, 해당 노드가 탐색되지 않았을 경우 시행한다.
if (deletedScreen >= 0 && !nodes[node.clip][deletedScreen].check) {
if (deletedScreen == target) {
return nextTime;
}
nodes[node.clip][deletedScreen].setNode(nextTime, node.clip, deletedScreen);
queue.offer(nodes[node.clip][deletedScreen]);
}
}
return -1;
}
public static void main(String[] args) {
//초기화 시작
Scanner scanner = new Scanner(System.in);
int target = scanner.nextInt();
//항상 clip 또는 screen이 target보다 작은범위에서 답을 구할 수 있다.
int max = target + 1;
/*
row = clip, col = screen이라하고
해당 row,col(=clip, screen)의 node가 탐색되었다면 탐색하지 않는다.
*/
Node[][] nodes = new Node[max][max];
for (int i = 0; i < max; i++) {
for (int j = 0; j < max; j++) {
nodes[i][j] = new Node();
}
}
//초기화 끝끝
System.out.println(bfs(nodes, target));
}
}
댓글