반응형

문제출처

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


간단한 dfs문제이다. xcode에 에러가 있어서 무슨 문제인가 계속 살펴봤는데 그냥 xcode 문제....

dfs호출시 시작 index와 depth를 인자로 넘겨줘서 끝까지 탐색하는 방법이다.


소스코드

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
//
//  main.cpp
//  BOJ_6603
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAX = 13;
int k;
int num[MAX];
int result[MAX];
 
void dfs(int start, int depth) {
    if(depth == 6)
    {
        for(int i=0; i<depth; i++)
        {
            printf("%d ", result[i]);
        }
        printf("\n");
        
        return;
    }
    
    for(int i=start; i<k; i++)
    {
        result[depth]=num[i];
        dfs(i+1, depth+1);
    }
}
int main(int argc, const char * argv[]) {
    
    while(true)
    {
        scanf("%d", &k);
        if(k==0){
            printf("\n");
            break;
        }
        for(int i=0; i<k; i++)
        {
            scanf("%d", &num[i]);
        }
        dfs(0,0);
        printf("\n");
    }
    return 0;
}
 
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[프로그래머스 42842] 카펫  (2) 2019.01.02
[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
[BOJ 2644] 촌수계산  (0) 2018.12.31
반응형

문제출처

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


DFS로 풀이한 문제 따로 visit배열을 사용하지 않고 dfs를 호출할 때 이미 방문한 곳은 값을 0으로 할당합니다. 때문에 map이 1인 경우만 탐색하면 되며 한개의 단지를 구한 후 dfs가 재호출될때 기존의 단지는 map상에 0이므로 재방문을 하지 않습니다. 


소스코드

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
//
//  main.cpp
//  BOJ_2667
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 25
 
using namespace std;
 
int n, cnt;
vector<int> section;
int map[MAX][MAX];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
 
void init() {
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            int tmp;
            scanf("%1d", &tmp);
            map[i][j]=tmp;
        }
}
 
void dfs(int x, int y) {
    map[x][y]=0;
    cnt++;
    
    for(int i=0; i<4; i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        
        if(nx>=0 && ny>=0 && nx<n && ny<n && map[nx][ny])
            dfs(nx, ny);
    }
}
 
int main(int argc, const char * argv[]) {
    init();
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(map[i][j])
            {
                cnt=0;
                dfs(i, j);
                section.push_back(cnt);
            }
        }
    }
    
    int len = section.size();
    printf("%d\n", len);
    
    sort(section.begin(), section.end());
    for(int i=0; i<len; i++)
        printf("%d\n", section.at(i));
    
    return 0;
}
 
cs



반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 6603] 로또  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
[BOJ 2644] 촌수계산  (0) 2018.12.31
[BOJ 2606] 바이러스  (0) 2018.12.28
반응형

문제 출처

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


단순 bfs구현 문제이다.

ret배열이 0이라면 관계가 없으므로 -1을 출력하고 0이 아니면 해당 값을 출력하도록 했다.

bfs / dfs를 언제 사용하는지 감이 잘 안왔었는데 간단히 정리하면


bfs를 이용하는 경우

1. 시작 지점에서 가장 가까운 것을 구하고 싶은 경우

2. 탐색 범위 자체는 넓지만 어느정도 근처에 구하고 싶은 해가 존재하는 것을 알고 있는 경우

3. 탐색 범위가 굉장히 넒으며 dfs를 사용할 때 스택이 대량으로 사용될 경우 이다.


반면 dfs를 이용하는 경우는

1. 모든 경로를 탐색하고 결과를 확인해야 하는 경우

2. 문자열 등을 탐색할 때 '사전 순서로 앞에오는 것'처럼 앞에서 검색해서 찾는 것이 빠를 경우 이다.


즉, 탐색 범위가 넓은 경우와 전체 탐색을 하지 않아도 될 경우는 bfs를 이용하고 전체 탐색이 필요하거나 순차적으로 찾을 필요가 있는 경우는 dfs를 사용하는 것이 좋다.


소스

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
//
//  main.cpp
//  BOJ_2644
//
//  Created by sw on 31/12/2018.
//  Copyright © 2018 sw. All rights reserved.
//
 
#include<iostream>
#include<queue>
#define MAX 101
 
using namespace std;
int n, src, dest, m, adj[MAX][MAX], ret[MAX];
 
int main(int argc, const char * argv[]) {
    cin >> n >> src >> dest >> m;
    for (int i = 0; i < m; i++) {
        int x = 0, y = 0;
        cin >> x >> y;
        adj[x][y] = adj[y][x] = 1;
    }
    
    queue<int> q;
    q.push(src);
    
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (adj[now][i] == 0 || ret[i] != 0)
                continue;
            ret[i] = ret[now] + 1;
            q.push(i);
        }
    }
    cout << (ret[dest] == 0 ? -1 : ret[dest]) << endl;
    return 0;
}
 
cs





반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2667] 단지번호붙이기  (0) 2018.12.31
[Programmers 43165] 타겟넘버  (0) 2018.12.31
[BOJ 2606] 바이러스  (0) 2018.12.28
[BOJ 2583] 영역구하기  (0) 2018.12.28
[TopCoder 전체탐색] 회문(Palindrome)  (0) 2018.12.20

+ Recent posts

티스토리툴바