'알고리즘 풀이/BFS' 카테고리의 글 목록

알고리즘 풀이/BFS

백준 2251 물통

2018. 8. 1. 01:16

<링크>

https://www.acmicpc.net/problem/2251

<소스코드>

#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int isVisited[201][201][201];
vector<int> ans;
typedef struct status {
    int h[3];
} status;
queue<status> q;
void bfs();
int cap[3];
int main()
{
    for (int i = 0; i < 3; ++i)
        scanf("%d", &cap[i]);
    bfs();
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); ++i)
        printf("%d ", ans[i]);
}
void bfs()
{
    isVisited[0][0][cap[2]] = 1;
    q.push({ 0,0,cap[2] });
    while (!q.empty())
    {
        status cur = q.front();
        q.pop();
 
        if (cur.h[0] == 0)
            ans.push_back(cur.h[2]);
        for (int i = 0; i<3; ++i)
            for (int j = 0; j < 3; ++j)
            {
                if (cur.h[i] == 0)
                    continue;
                if (i != j)
                {
                    int tmp[3];
                    for (int k = 0; k < 3; ++k)
                        tmp[k] = cur.h[k];
                    if (cap[j] - tmp[j] <= tmp[i])
                    {
                        tmp[i]-=cap[j] - tmp[j];
                        tmp[j] = cap[j];
                    }
                    else
                    {
                        tmp[j] = tmp[j] + tmp[i];
                        tmp[i] = 0;
                    }
                    if (!isVisited[tmp[0]][tmp[1]][tmp[2]])
                    {
                        isVisited[tmp[0]][tmp[1]][tmp[2]] = 1;
                        q.push({ tmp[0],tmp[1],tmp[2] });
                    }
                }
                
            }
    }
}

Colored by Color Scripter

<풀이>

1. 물을 옮길때, 두 가지 특성을 고려한다.

A는 A통의 총량이고, a는 현재 A통에 있는 물의 양

B는 B통의 총량이고 ,b는 현재 B통에 있는 물의 양이라했을때

A->B로 물을 옮긴다고하면

B-b <= a 일때 : b=B, a= a-(B-b)

B-b > a 일때 : b=b+a, a=0

이렇게 된다.

●B통에 넣을수있는 물의 양이 a보다 같거나 작을때는, B에는 물이 꽉차게되고 a는 그만큼만 줄어든다.

A B
7  5 ...//총량
5  2 ...//현재량

A->B로 물을 부으면, 5-2=3보다 5가 크므로 b=5, a= 5-(5-2) = 2가 된다.

●B통에 넣을수있는 물의 양이 a보다 클 때에는, A의 물은 0이될때까지 붓게되고, b는 a만큼 늘어난다.

A B
7 8 ...//총량
3 2 ...//현재량

A->B로 물을 부으면, 8-2 =6이 3보다 크므로, a=0, b= 2+3 = 5가 된다.

2. A, B, C가 있으면 옮길수 있는 방향은 다음과 같이 6가지이다.

A->B

A->C

B->A

B->C

C->A

C->B

각각 물을 옮겨보고 이미 A,B,C에 남은양이 또 나오면 가지를 뻗어나가지 않는다.

8,0,2가 한번 나왔는데 또 8,0,2를 볼필요는 없기 때문이다.

3차원배열로 체크했다. 각 통의 물의 총량은 200이 최대이기 때문에

[200][200][200] 배열을 만들어도 메모리가 터지지 않는다.

8,0,2가 뜨면 [8][0][2]=1 이런식으로 체크했다.

3. 다른 BFS문제들과 다르게 최단횟수 등을 구하는게아니고

A가 0일 때, C의 가능한 양을 구하는 것이기 때문에

그냥 싹다 탐색한다.

아무리 심해도 200*200*200이 걸릴 것이다.

그럼 시간도 터지지 않는다.

저작자표시

'알고리즘 풀이 > BFS' 카테고리의 다른 글

백준 1525 퍼즐 (0)	2018.07.31
백준 9019 DSLR (0)	2018.07.31
백준 1963 소수 경로 (2)	2018.07.30
백준 1697 숨바꼭질 (1)	2018.07.29
KOITP 보물찾기 (0)	2018.07.23

백준 1525 퍼즐

2018. 7. 31. 11:13

<링크>

https://www.acmicpc.net/problem/1525

<소스코드>

#include<stdio.h>
#include<queue>
#include<set>
#include<string>
#include<iostream>
using namespace std;
queue<string> q;
set<int> isVisited;
int to[4] = { -1,1,-3,3 };
int bfs(string);
int main()
{
    string start;
    int n;
    for (int i = 0; i < 9; ++i) {
        scanf("%d", &n);
        start += n + '0';
    }
    printf("%d",bfs(start));
 
}
int bfs(string s)
{
    int depth = 0;
    q.push(s);
    isVisited.insert(stoi(s));
    while (!q.empty())
    {
        int size = q.size();
        for (int i = 0; i < size; ++i)
        {
            string cur = q.front();
            q.pop();
            if (cur.compare("123456780")==0)
                return depth;
 
            int zero;
            for (int j = 0; j < 9; ++j) //0의위치를 알아내고
                if (cur[j] == '0')
                {
                    zero = j; break;
                }
            for (int j = 0; j < 4; ++j)
            {
                if (j < 2)
                    if ((zero + to[j]) / 3 != zero / 3) continue;
                if (zero + to[j] >= 0 && zero + to[j] < 9)
                {                    
                    string toStr = string(cur);
                    swap(toStr[zero + to[j]], toStr[zero]);
                    int toNum = stoi(toStr);
                    if (isVisited.find(toNum) == isVisited.end())
                    {
                        isVisited.insert(toNum);
                        q.push(toStr);
                    }
                }
            }
        }
        ++depth;
    }
    return -1;
}

Colored by Color Scripter

<풀이>

1. 방문했는지 안했는지 여부를 set을 이용해 구현했다. 판때기에 있는 숫자들을 한줄로 쫙 깐다음에 하나의 정수로 표현한다.

1 2 3

4 5 6

7 8 0

: 123456780

0 1 3

2 4 6

5 8 7

: 13246587

2. 하나의 노드는 string으로 표현했다.

3. string상에서 '0'의 위치를 찾아내고 그 상하좌우에 있는 수와 자리를 바꾼뒤, bfs를 이어간다.

상,하는 -3, +3을 하면 된다.

좌,우는 -1, +1을 하되, 같은 라인에 있는지 확인해야한다.

index / 3이 같으면 같은 라인에 있는것이다.

string상에서의 인덱스 : 012345678 

판떼기 상에서의 인덱스 :
012 : /3 =0
345 : /3 =1
678 : /3 =2

4. java 라이브러리를 통해 구현한다면

HashSet의 contains메소드를 쓰면될것같다.

저작자표시

'알고리즘 풀이 > BFS' 카테고리의 다른 글

백준 2251 물통 (0)	2018.08.01
백준 9019 DSLR (0)	2018.07.31
백준 1963 소수 경로 (2)	2018.07.30
백준 1697 숨바꼭질 (1)	2018.07.29
KOITP 보물찾기 (0)	2018.07.23

백준 9019 DSLR

2018. 7. 31. 08:23

<링크>

https://www.acmicpc.net/problem/9019

<소스코드>

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
#include<stdio.h>
#include<queue>
#include<string>
#include<math.h>
#include<stack>
#include<string.h>
using namespace std;
void bfs(int, int);
void trace(pair<int,int>[], int);
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int A, B;
        scanf("%d%d", &A, &B);
        bfs(A, B);
        printf("\n");
    }
}
void bfs(int A, int B)
{
    int isVisited[10000] = { 0, };
    pair<int, int> before[10000];
    queue<int> q;
    isVisited[A] = 1;
    before[A] = { -1,-1 };
    q.push(A);
    while (!q.empty())
    {
        int n = q.front();
        q.pop();
        if (n == B) {
            trace(before, B); return;
        }
        int to[4];
        to[0] = n * 2 % 10000;
        to[1] = n == 0 ? 9999 : n - 1;
        to[2] = n % 1000 * 10 + n / 1000;
        to[3] = n % 10 * 1000 + n / 10;
        for (int i = 0; i < 4; ++i)
            if (!isVisited[to[i]])
            {
                isVisited[to[i]] = 1;
                before[to[i]] = { i,n };
                q.push(to[i]);
            }
    }
}
void trace(pair<int,int> before[],int n)
{
    stack<int> st;
    while (before[n].first!=-1)
    {
        st.push(before[n].first);
        n = before[n].second;
    }
    while (!st.empty())
    {
        switch (st.top())
        {
        case 0:printf("D"); break;
        case 1:printf("S"); break;
        case 2:printf("L"); break;
        case 3:printf("R"); break;
        }
        st.pop();
    }
}
 
Colored by Color Scripter
cs

<풀이>

1. 나올 수 있는 숫자는 0~9999이다.

2. bfs를 해서 A에서 B까지 몇 번만에 가냐가 중요한게 아니고 가는 경로를 기록해야한다.

처음엔 그냥 연산자만 기록하면서 가려했는데 'D' 연산 때문에 애매해질 것 같았다.

예를 들어

D연산을 통해 100이라는 숫자가 되었다면

이전 숫자는 50일 수도 있고 5050일 수도 있기 때문이다.

3. before[10000] 배열을 만들어서 내 이전의 숫자와 연산을 저장했다.

어차피 한 번 방문한 노드는 다시 보지않기 때문에 겹칠일도 없고

before에 기록된 모든 숫자들은 다 최단거리로 온거니깐 믿고 참조하면 된다.

1234 →L 2341 →L 3412

before[1234] = {-1,-1}
before[2341] = {1234 , L}
before[3412] = {2341 , L}

4. B부터 시작해서 before[ ]를 계속 참조하며 A가 나올때까지 stack에 넣는다.

5. 싹다 pop하면 정순서가 나온다.

저작자표시

'알고리즘 풀이 > BFS' 카테고리의 다른 글

백준 2251 물통 (0)	2018.08.01
백준 1525 퍼즐 (0)	2018.07.31
백준 1963 소수 경로 (2)	2018.07.30
백준 1697 숨바꼭질 (1)	2018.07.29
KOITP 보물찾기 (0)	2018.07.23

백준 1963 소수 경로

2018. 7. 30. 10:33

<링크>

https://www.acmicpc.net/problem/1963

<소스코드>

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
#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#include<string.h>
using namespace std;
void eratos();
void bfs(int,int);
vector<int> isPrime(10000,1);
int main()
{
    eratos();
    int T,N,K;
    scanf("%d", &T);
    while (T--) 
    {
        scanf("%d%d", &N, &K);
        bfs(N,K);
    }
}
void bfs(int S,int D)
{
    queue<int> q;
    vector<int> isVisited(10000, 0);
    q.push(S);
    int depth = 0;
    while (!q.empty())
    {
        int s = q.size();
        for (int i = 0; i < s; ++i)
        {
            int c = q.front();
            q.pop();
            if (c == D) {
                printf("%d\n", depth); return;
            }
            string num = to_string(c);
            for (int j = 0; j < 4; ++j)
            {
                string tmp = string(num);
                for (int k = '0'; k <= '9'; ++k)
                {
                    tmp[j] = k;
                    int to = stoi(tmp);
                    if (isPrime[to] && !isVisited[to] && to >= 1000)
                    {
                        isVisited[to] = 1;
                        q.push(to);
                    }
                }
            }
        }
        ++depth;
    }
    printf("Impossible\n"); 
    return;
}
void eratos()
{
    for (int i = 2; i <= 100; ++i)
    {
        if(isPrime[i])
        for (int j = i * 2; j <= 9999; j += i)
        {
            isPrime[j] = 0;
        }
    }
}
Colored by Color Scripter
cs

<풀이>

각 자리마다 번호를 0~9까지 바꿔가면서 탐색한다.

소수이면서 && 방문 안했고 && 1000이상일때만 큐에 넣는다.

한 자리만 번호를 바꿔야하므로 구현하기 귀찮아서 string을 이용했다.

소수인지 판가름하기도 좀더 빠르게 하려고 에라토스테네스의 체를 이용했다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1. 그냥다 소수라고 가정하고 배열 만듬 (전부 소수라고 체크)

2. 2부터 루트N까지 소수라고 체크되어있으면 배수는 다 제거

저작자표시

'알고리즘 풀이 > BFS' 카테고리의 다른 글

백준 2251 물통 (0)	2018.08.01
백준 1525 퍼즐 (0)	2018.07.31
백준 9019 DSLR (0)	2018.07.31
백준 1697 숨바꼭질 (1)	2018.07.29
KOITP 보물찾기 (0)	2018.07.23

백준 1697 숨바꼭질

2018. 7. 29. 21:47

<링크>

https://www.acmicpc.net/problem/1697

<소스코드>

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
#include<stdio.h>
#include<queue>
using namespace std;
void check(int);
int bfs();
queue<int> q;
int N, K;
int isVisited[100001];
int main()
{
    scanf("%d%d", &N, &K);
    printf("%d", bfs());
}
int bfs()
{
    q.push(N);
    int depth = 0;
    while (!q.empty())
    {
        int s = q.size();
        for (int i = 0; i < s; ++i)
        {
            int cur = q.front();
            q.pop();
            if (cur == K)
                return depth;
            check(cur+1);
            check(cur-1);
            check(cur*2);
        }
        ++depth;
    }
}
void check(int to)
{
    if (to >= 0 && to <= 100000 && !isVisited[to])
    {
        isVisited[to] = 1;
        q.push(to);
    }
 
}
Colored by Color Scripter
cs

<풀이>

현재 위치에서부터 BFS를 한다.

1. 한번 봤던 노드는 다시 보지않는다.

5라는 좌표는는 이미 봤던 좌표이고 5까지 가는 거리는 0이다. 나중에 4에서 +1을통해 5로 가던, 6에서 -1을 통해 5로 가던 어떤방식으로든 0보다는 작을 수 없다. 즉, 한 번 방문했던 좌표를 또 방문하는 건 삥 돌아오는 것이라는 뜻이다. 따라서 bfs가지를 뻗어나갈 때 방문했던 노드는 제외시켜버린다.

2. 1의 규칙 때문에 큐에 어떤 숫자가 들어왔다는 것은 그 숫자는 처음 나온 것이라는 말과 같다. 따라서 해당 숫자까지의 depth가 최단거리이다. 목표좌표가 뜨면 그 순간의 depth가 답이 된다.

3. 기존의 bfs방식인 while(!q.empty()) 만으로는 depth를 알 수 없다. 그냥 발견하면 끝이기 때문이다.

그렇기 때문에 while 안에서 현재의 큐 size를 얻어내고, 그만큼 for문을 돌리면 하나의 for문이 곧 한 depth가 된다.

depth를 재는 방식은 다른 방법도있지만 개인적으로 이게 제일 편한것같다.

저작자표시

'알고리즘 풀이 > BFS' 카테고리의 다른 글

백준 2251 물통 (0)	2018.08.01
백준 1525 퍼즐 (0)	2018.07.31
백준 9019 DSLR (0)	2018.07.31
백준 1963 소수 경로 (2)	2018.07.30
KOITP 보물찾기 (0)	2018.07.23

PREV 1 2 NEXT

들짐승 프로그래밍