Difference between r1.1 and the current
@@ -4,18 +4,156 @@
* [https://www.acmicpc.net/problem/1697|숨바꼭질]
= 참가자 =
= 코드 =
== 15이원준 ==
== 곽정흠 ==
== 15이원준 ==
== 박인서 ==
== 곽정흠 ==
= 참가자 =
* 15이원준
* 박인서 * [곽정흠]
= 코드 =
== 15이원준 ==
{{{
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;
int main(){
int arr[100001] = {0,};
int N, M, ans;
queue<pair<int, int>> que;
cin>> N >> M;
if(N >= M){
cout<< N - M << endl;
return 0;
}
que.push(make_pair(N, 0));
while(que.front().first != M){
int n, dep;
n = que.front().first;
dep = que.front().second;
que.pop();
if(n-1 >= 0 && !arr[n-1]){
arr[n-1] = 1;
que.push(make_pair(n - 1, dep + 1));
}
if(n+1 <= 100000 && !arr[n+1]){
arr[n+1] = 1;
que.push(make_pair(n + 1, dep + 1));
}
if(n * 2 <= 100000 && !arr[n*2]){
arr[n*2] = 1;
que.push(make_pair(n * 2, dep + 1));
}
}
cout<< que.front().second << endl;
}
}}}
== 박인서 =={{{
#include <iostream>
#include <queue>
typedef std::pair<int, int> pair_int;
std::queue<pair_int> q;
bool visit[200001];
int main()
{
int s, e;
std::cin >> s >> e;
if (s < e) {
q.push(pair_int(s, 0));
while (q.front().first != e) {
pair_int tq = q.front();
if (tq.first < e && !visit[tq.first * 2])
q.push(pair_int(tq.first * 2, tq.second + 1)), visit[tq.first * 2] = true;
if (tq.first < e && !visit[tq.first + 1])
q.push(pair_int(tq.first + 1, tq.second + 1)), visit[tq.first + 1] = true;
if (tq.first > 0 && !visit[tq.first - 1])
q.push(pair_int(tq.first - 1, tq.second + 1)), visit[tq.first - 1] = true;
q.pop();
}
std::cout << q.front().second;
}
else std::cout << s - e;
return 0;
}
}}}
== 곽정흠 ==
{{{
#include <stdio.h>
#define MAX_QUEUE 100000
#define MAX_NODE 100001
int distance[MAX_NODE];
int queue[MAX_QUEUE];
int first = 0, last = 0;
void add(int tmp) {
if (last == MAX_QUEUE) {
last = 0;
queue[last++] = tmp;
}
else {
queue[last++] = tmp;
}
}
int delete(void) {
if (first == MAX_QUEUE - 1) {
first = 0;
return queue[MAX_QUEUE-1];
}
else {
return queue[first++];
}
}
int bnf(int n, int k) {
int tmp = delete();
if (tmp == k) {
return 1;
}
if (tmp * 2 <= k+1) {
if (distance[tmp * 2] > distance[tmp] + 1) {
distance[tmp * 2] = distance[tmp] + 1;
add(tmp * 2);
}
}
if (distance[tmp + 1] > distance[tmp] + 1) {
distance[tmp +1] = distance[tmp] + 1;
add(tmp + 1);
}
if (tmp - 1 >= 0&&distance[tmp-1]>distance[tmp]+1) {
distance[tmp -1] = distance[tmp] + 1;
add(tmp - 1);
}
return 0;
}
int main() {
int n, k;
for (int i = 0; i < MAX_NODE; i++) {
distance[i] = MAX_NODE;
}
scanf("%d%d", &n, &k);
distance[n] = 0;
add(n);
while (bnf(n, k) == 0) {
}
printf("%d\n", distance[k]);
return 0;
}
}}}
= 아이디어 === 15이원준 ==
== 박인서 ==
* 기본적인 아이디어는 Queue를 이용한 BFS이다.
* 단 너무 숫자가 커지면 안되므로, 200000이 넘어가면 제한을 한다.
* 그리고 뒤로 갈 경우 갈 수 있는 방법은 -1밖에 없으므로 그 것을 예외 처리 해준다.
== 곽정흠 ==
3.1. 15이원준 ¶
#include<iostream> #include<cmath> #include<algorithm> #include<queue> #include<utility> using namespace std; int main(){ int arr[100001] = {0,}; int N, M, ans; queue<pair<int, int>> que; cin>> N >> M; if(N >= M){ cout<< N - M << endl; return 0; } que.push(make_pair(N, 0)); while(que.front().first != M){ int n, dep; n = que.front().first; dep = que.front().second; que.pop(); if(n-1 >= 0 && !arr[n-1]){ arr[n-1] = 1; que.push(make_pair(n - 1, dep + 1)); } if(n+1 <= 100000 && !arr[n+1]){ arr[n+1] = 1; que.push(make_pair(n + 1, dep + 1)); } if(n * 2 <= 100000 && !arr[n*2]){ arr[n*2] = 1; que.push(make_pair(n * 2, dep + 1)); } } cout<< que.front().second << endl; }
3.2. 박인서 ¶
#include <iostream> #include <queue> typedef std::pair<int, int> pair_int; std::queue<pair_int> q; bool visit[200001]; int main() { int s, e; std::cin >> s >> e; if (s < e) { q.push(pair_int(s, 0)); while (q.front().first != e) { pair_int tq = q.front(); if (tq.first < e && !visit[tq.first * 2]) q.push(pair_int(tq.first * 2, tq.second + 1)), visit[tq.first * 2] = true; if (tq.first < e && !visit[tq.first + 1]) q.push(pair_int(tq.first + 1, tq.second + 1)), visit[tq.first + 1] = true; if (tq.first > 0 && !visit[tq.first - 1]) q.push(pair_int(tq.first - 1, tq.second + 1)), visit[tq.first - 1] = true; q.pop(); } std::cout << q.front().second; } else std::cout << s - e; return 0; }
3.3. 곽정흠 ¶
#include <stdio.h> #define MAX_QUEUE 100000 #define MAX_NODE 100001 int distance[MAX_NODE]; int queue[MAX_QUEUE]; int first = 0, last = 0; void add(int tmp) { if (last == MAX_QUEUE) { last = 0; queue[last++] = tmp; } else { queue[last++] = tmp; } } int delete(void) { if (first == MAX_QUEUE - 1) { first = 0; return queue[MAX_QUEUE-1]; } else { return queue[first++]; } } int bnf(int n, int k) { int tmp = delete(); if (tmp == k) { return 1; } if (tmp * 2 <= k+1) { if (distance[tmp * 2] > distance[tmp] + 1) { distance[tmp * 2] = distance[tmp] + 1; add(tmp * 2); } } if (distance[tmp + 1] > distance[tmp] + 1) { distance[tmp +1] = distance[tmp] + 1; add(tmp + 1); } if (tmp - 1 >= 0&&distance[tmp-1]>distance[tmp]+1) { distance[tmp -1] = distance[tmp] + 1; add(tmp - 1); } return 0; } int main() { int n, k; for (int i = 0; i < MAX_NODE; i++) { distance[i] = MAX_NODE; } scanf("%d%d", &n, &k); distance[n] = 0; add(n); while (bnf(n, k) == 0) { } printf("%d\n", distance[k]); return 0; }