728x90
반응형
weight가 제 각각일 경우 dijkstra로 최솟값을 구할 수 있고,
1로 일정할 경우엔 bfs로 최솟값을 구할 수 있다.

이 문제는 범주가 3개로 나뉜다.
- 화면에 이모티콘 붙여넣기
화면 이모티콘 개수 + 클립보드 이모티콘 개수
- 화면에 이모티콘 삭제
화면 이모티콘 개수 - 1
- 화면에 이모티콘 복사하기
클립보드 이모티콘 개수 = 화면 이모티콘 개수
화면 이모티콘과 클립보드 이모티콘 개수를 따로 기록해줘야하므로
pair를 이용해서 queue에 집어넣었다.
//백준 이모티콘
#include <iostream>
#include <queue>
using namespace std;
int weight[1001][1001];
bool visited[1001][1001];
int answer = 0;
void initWeight(){
for(int i = 0; i <= 1000; i++){
for(int j = 0; j <= 1000; j++){
weight[i][j] = 0;
}
}
}
void initVisited(){
for(int i = 0; i <= 1000; i++){
for(int j = 0; j <= 1000; j++){
visited[i][j] = false;
}
}
}
void bfs(int s){
queue<pair<int,int>> q;
q.push({1,0});
while(!q.empty()){
pair<int,int> node = q.front();
q.pop();
if(node.first == s){
answer = weight[node.first][node.second];
return;
}
if(!visited[node.first][node.first]){
weight[node.first][node.first] = weight[node.first][node.second] + 1;
visited[node.first][node.first] = true;
q.push({node.first, node.first});
}
int imojiNumAfterPaste = node.second + node.first;
if(imojiNumAfterPaste <= 1000 && !visited[imojiNumAfterPaste][node.second]){
weight[imojiNumAfterPaste][node.second] = weight[node.first][node.second] + 1;
visited[imojiNumAfterPaste][node.second] = true;
q.push({imojiNumAfterPaste, node.second});
}
int imojiNumAfterAbandon = node.first - 1;
if(imojiNumAfterAbandon >= 2 && !visited[imojiNumAfterAbandon][node.second]){
weight[imojiNumAfterAbandon][node.second] = weight[node.first][node.second] + 1;
visited[imojiNumAfterAbandon][node.second] = true;
q.push({imojiNumAfterAbandon, node.second});
}
}
}
int main(void){
int s;
cin >> s;
bfs(s);
cout << answer;
}
https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102905.cpp
jeongdaeun98/algorithm
백준, 프로그래머스. Contribute to jeongdaeun98/algorithm development by creating an account on GitHub.
github.com
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 퇴사 (0) | 2020.10.30 |
---|---|
[algorithm] 백준 - 연산자 끼워넣기 & 연산자 끼워넣기 2 (0) | 2020.10.30 |
[algorithm] 백준 - N과 M(10) (0) | 2020.10.30 |
[algorithm] 백준 - N과 M(9) (0) | 2020.10.30 |
[algorithm] 백준 - ABCDE (0) | 2020.10.29 |