<링크>

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;
        }
    }
}
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

<링크>

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);
    }
 
}
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

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<vector>
using namespace std;
vector<int> num(13);
vector<int> v;
int N;
void dfs(int, int);
int main()
{
    while (1)
    {
        scanf("%d", &N);
        if (N == 0)
            break;
        for (int i = 1; i <= N; ++i)
            scanf("%d", &num[i]);
        dfs(1, 0);
        printf("\n");
    }
}
void dfs(int i, int len)
{
    if (len == 6) {
        for (int i = 0; i < 6; ++i)
            printf("%d ", v[i]);
        printf("\n");
        return;
    }
    if (i > N)
        return;
    v.push_back(num[i]);
    dfs(i+1, len + 1);
    v.pop_back();
    dfs(i+1, len);
}
cs


<풀이>

조합을 만들 때는

num[i]를 조합에 넣는다, 안넣는다로 따진다.

순열처럼 for문을 쓰지 않고 재귀를 돌려도 된다.

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int i, int len)
{
    if (len <= ?) {
        ;
    }
    if (i > N)
        return;
    v.push_back(num[i]);
    dfs(i+1, len + 1);
    v.pop_back();
    dfs(i+1, len);
}
cs


이렇게 하면 len의 조건을 수정해서 좀 더 유연하게 쓸 수 있다.

로또같은 경우는 len==6일때 출력하는 방식이었다.


위코드에서 기저점을 len<=3 으로 바꾸면,

길이가 3 이하인 조합을 중복없이 알아낼 수 있다.

예를들어

<N=6, num={1,2,3,4,5,6}>
len=3이하일때 만들수있는 조합
1
1 2
1 2 3
1 2 4
1 2 5
1 2 6

1 3
1 3 4
1 3 5
1 3 6

1 4
1 4 5
1 4 6

1 5
1 5 6

1 6

2
2 3
2 3 4
...

위와같은 조합들로 처리하고싶을 때 편리하다.


관련문제 : 백준 15686 치킨배달

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


넣는다, 안넣는다 방식으로 재귀호출하면

i가 한도끝도없이 이어지게되므로 i가 N을 초과하면 리턴해줘야한다.


저작자표시

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

백준 10971 외판원 순회 2  (0) 2018.07.28
백준 10819 차이를 최대로  (0) 2018.07.27
백준 10974 모든 순열  (2) 2018.07.24
KOITP 큰수만들기  (0) 2018.07.23
백준 11724 연결 요소의 개수 :: 들짐승  (0) 2018.07.23

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<algorithm>
using namespace std;
int adj[11][11];
int isVisited[11];
int ans = 20000000;
int N;
void dfs(int, int, int);
int main()
{
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            scanf("%d",&adj[i][j]);
    isVisited[1] = 1;
    dfs(1, 0, 0);
    printf("%d", ans);
}
void dfs(int node, int cost, int depth)
{
    if (depth == N-1 && adj[node][1])
    {
        ans = min(ans, cost + adj[node][1]);
        return;
    }
    for (int i = 1; i <= N; ++i)
        if (adj[node][i] && !isVisited[i])
        {
            isVisited[i] = 1;
            dfs(i, cost + adj[node][i], depth + 1);
            isVisited[i] = 0;
        }
 
}
cs


<풀이>

순열문제랑 똑같이 풀었다.
시작은 1이고, N개의 노드를 모두 탐색하는 데 나올 수 있는 순열을 구한다.


12345
13245
...
15234
...
15432


물론 순열에 들어있다는건 그 순서대로 연결이 되어있다는 뜻이다.
인접행렬을 보면서 인접된 노드들을 체크하며 dfs를 했다.
마지막에 현재까지 본 노드 개수가 N개이고, 마지막노드에 1이 연결되어있다면
답을 갱신하였다.


시간복잡도는 N!인데
N이 10이라서 괜찮다.

저작자표시

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

백준 6603 로또  (0) 2018.07.29
백준 10819 차이를 최대로  (0) 2018.07.27
백준 10974 모든 순열  (2) 2018.07.24
KOITP 큰수만들기  (0) 2018.07.23
백준 11724 연결 요소의 개수 :: 들짐승  (0) 2018.07.23

<링크>

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

백준 10819 차이를 최대로



<소스코드>

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
#include<stdio.h>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
int N;
int isVisited[9];
vector<int> v;
vector<int> seq;
int ans;
void check();
void dfs();
int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        int num;
        scanf("%d", &num);
        v.push_back(num);
    }
    dfs();
    printf("%d", ans);
}
void dfs()
{
    if (seq.size() == N)
        check();
    for (int i = 0; i < N; ++i)
    {
        if (!isVisited[i])
        {
            isVisited[i] = 1;
            seq.push_back(v[i]);
            dfs();
            isVisited[i] = 0;
            seq.pop_back();
 
        }
    }
}
void check()
{
    int sum = 0;
    for (int i = 0; i < N - 1; ++i)
        sum += abs(seq[i] - seq[i + 1]);
    ans = max(ans, sum);
}
cs


<풀이>

순열 문제랑 똑같다. 벡터 push_back(), pop_back() 이용하면서 하면된다.

2018/07/24 - [알고리즘 풀이/DFS] - 백준 10974 모든 순열



저작자표시

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

백준 6603 로또  (0) 2018.07.29
백준 10971 외판원 순회 2  (0) 2018.07.28
백준 10974 모든 순열  (2) 2018.07.24
KOITP 큰수만들기  (0) 2018.07.23
백준 11724 연결 요소의 개수 :: 들짐승  (0) 2018.07.23

+ Recent posts

티스토리툴바