반응형
BFS를 활용하는 문제이다.
그러나 일반적인 BFS를 사용한다면 틀린 답을 출력할 것이다. 왜냐하면 클립보드라는 개념을 이문제에선 가지고 있는데 S개의 아이콘을 만드는데 걸리는 시간을 T라고 한다면, 같은 S개를 만들더라도 클립보드의 수에 따라 각 각 다른 T를 가지게 된다.
이 이유는 그래프에서 예를 찾을 수 있는데, 정점 A에서 B를 가고 싶을때, 간선1을 선택해서 가는 경우랑 간선2를 선택해서 가는경우가 있다 가정하자. 같은 B를 도달했더라도 다른 간선을 선택하여 왔기때문에 다른 경우의 수라 생각할 수 있다.
즉, 문제로 다시 돌아와본다면 클립보드의 수에 따라 같은 S개를 만들더라도 다른 T시간을 가질 수 있기 때문에 시간을 저장하는 배열 visit를 2차원의 배열의 형태로 작성하였다. 즉 visit[현재이모티콘개수][현재클립보드수]로 구현하였고, 이를 이용하여 BFS를 사용하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
package online.base;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main_bj_14226_이모티콘 {
static int dest;
static int[][] visit;
static Queue<Imo> queue;
static int answer;
static class Imo{
int num,clip,time;
Imo(int n,int c, int t){
num=n;clip=c;time=t;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
dest=Integer.parseInt(br.readLine());
visit=new int[1001][1001];
queue=new LinkedList<>();
answer=0;
bfs();
// answer=Integer.MAX_VALUE;
// for(int i=0;i<=1000;i++) {
// if(visit[dest][i]!=0 && visit[dest][i]<answer) {
// answer=visit[dest][i];
// }
// }
System.out.println(answer);
}
static void bfs() {
while(!queue.isEmpty()) {
Imo cur= queue.poll();
answer=cur.time;
break;
}
//1번 클립보드에 복사
}
//2번 클립보드에 있는 것을 화면에
}
//3번 이모티콘 중 하나 삭제
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
package algostudy3;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main_bj_14226_이모티콘 {
static int N;
static Queue<Node> queue;
static int[][] visit;
static int answer;
static class Node {
int num;
int copy;
public Node(int num, int copy) {
this.num = num;
this.copy = copy;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
visit = new int[1001][1001]; //visit[num][copy];
queue = new LinkedList<>();
answer = 0;
bfs();
System.out.println(answer);
}
static void bfs() {
queue.offer(new Node(1, 0));
visit[1][0] = 0;
while (!queue.isEmpty()) {
Node cur = queue.poll();
if (cur.num == N) {
answer = visit[cur.num][cur.copy];
break;
}
//복사
int copy = cur.num;
if (1 <= copy && copy <= 1000 && visit[cur.num][copy] == 0) {
visit[cur.num][copy] = visit[cur.num][cur.copy] + 1;
queue.offer(new Node(cur.num, copy));
}
//붙여넣기
int addNum = cur.num + cur.copy;
if (1 <= addNum && addNum <= 1000 && visit[addNum][cur.copy] == 0) {
visit[addNum][cur.copy] = visit[cur.num][cur.copy] + 1;
queue.offer(new Node(addNum, cur.copy));
}
//삭제
int minusNum = cur.num - 1;
if (1 <= minusNum && minusNum <= 1000 && visit[minusNum][cur.copy] == 0) {
visit[minusNum][cur.copy] = visit[cur.num][cur.copy] + 1;
queue.offer(new Node(minusNum, cur.copy));
}
}
}
}
|
반응형
'Algorithm' 카테고리의 다른 글
[BOJ] 13023. ABCDE (0) | 2020.04.17 |
---|---|
[BOJ] 1260. DFS와 BFS (0) | 2020.04.17 |
[BOJ] 15658. 연산자 끼워넣기(2) (0) | 2020.04.14 |
[BOJ] 14501. 퇴사 (0) | 2020.04.14 |
[BOJ] 1753. 최단경로 (0) | 2020.04.12 |