STL은 강력하다. 벡터에서 다음 순열과 이전수열을 구하는 알고리즘을 내장하고 있다.

사용법은 next_permutation 함수에 이터레이터의 시작과 끝을 넣어주면 된다. 다음 순열을 구했으면 true 마지막순열이었다면 false를 반환해 while문에 응용할 수 있다.


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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> perm;
int main()
{
    bool last = false;
    int input = 0;
    cin >> input;
    for (int i = 0; i < input; ++i)
    {
        int n_input;
        cin >> n_input;
        perm.push_back(n_input);
    }
    last = next_permutation(perm.begin(), perm.end());
    if (!last)
        cout << -1 << endl;
    else
    {
        for (auto itr = perm.begin(); itr != perm.end(); ++itr)
            cout << *itr << " ";
    }
    
    cout << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 10974: 모든 순열  (0) 2018.07.17
백준 10973: 이전 순열  (0) 2018.07.17
백준 7576: 토마토  (0) 2018.07.16
백준 2146: 다리 만들기  (0) 2018.07.16
백준 2178: 미로 탐색  (0) 2018.07.16

토마토문제 bfs를 사용하면 되는 문제이다. bfs의 개념을 알면 쉽게 풀 수 있으나 주의해야할 부분이 있다면 토마토가 있는 부분을 모두 동시에 큐에 넣어줘야한다는 것. 토마토가 익지 못하는 경우를 판단해줘야 한다는 것 정도다.


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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> a (1002);
int g_c;
int g_r;
int check[1005][1005];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
bool no_tomato = false;
int main()
{
    cin >> g_c >> g_r;
    for (int i = 0;i < g_r; ++i)
    for (int j = 0; j < g_c; ++j)
    {
        int input;
        cin >> input;
        a[i].push_back(input);
    }
    queue<pair<int, int>> q;
    for (int i = 0; i < g_r; ++i)
    for (int j = 0; j < g_c; ++j)
    {
        if (a[i][j] == 1)
        {
            q.push(make_pair(i, j));
            check[i][j] = 1;
        }
    }
 
    while (!q.empty())
    {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (nr >= 0 && nr < g_r && nc >= 0 && nc < g_c)
            if (a[nr][nc] == 0 && check[nr][nc] == 0)
            {
                check[nr][nc] = check[r][c] + 1;
                q.push(make_pair(nr,nc));
            }
        }
    }
    int max_val = 0;
    for (int i = 0; i < g_r; ++i)
    for (int j = 0; j < g_c; ++j)
    {
        max_val = max(max_val, check[i][j]);
        if (check[i][j] == 0 && a[i][j] == 0)
            no_tomato = true;
    }
    if (no_tomato == true)
    {
        cout << -1 << endl;
        return 0;
    }
    cout << max_val  - 1 << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 10973: 이전 순열  (0) 2018.07.17
백준 10972: 다음 순열  (0) 2018.07.17
백준 2146: 다리 만들기  (0) 2018.07.16
백준 2178: 미로 탐색  (0) 2018.07.16
백준 4963: 섬의 개수  (0) 2018.07.16
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> a(101);
int check[102][102];
int dis[102][102];
int dr[4] = { 1, -1, 0, 0 };
int dc[4] = { 0, 0, 1, -1 };
int is_num = 1;
int main()
{
    int n;
    //입력을 받아서 동적배열 a에 값들을 채워넣음
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int input;
            cin >> input;
            a[i].push_back(input);
        }
    }
 
    queue<pair<int, int>> q;
    //섬을 그룹으로 나눈다.
    //bfs 시작, 시작점을 알 수 없으니 모든 곳에서 해봐야함.
    //두가지를 생각해봐야함 섬의 영역과 거리, check은 영역 dis는 거리
    //check를 그룹으로 나누는 bfs
    for (int i = 0; i < n; ++i) 
    for (int j = 0; j < n; ++j)
    {
        if (a[i][j] == 1 && check[i][j] == 0)
        {
            q.push(make_pair(i,j));
            check[i][j] = is_num;
            ++is_num;
        }
        while (!q.empty())
        {
            int r = q.front().first;
            int c = q.front().second;
            q.pop();
            for (int k = 0; k < 4; ++k)
            {
                int nr = dr[k] + r;
                int nc = dc[k] + c;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n)
                if (check[nr][nc] == 0 && a[nr][nc] == 1)
                {
                    check[nr][nc] = check[r][c];
                    q.push(make_pair(nr, nc));
                }
            }
        }
        
    }
    //모든 섬의 외각에서 동시에 넓히기 위해 큐에 넣어 줌
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
    {
        if (a[i][j] == 1)
        {
            q.push(make_pair(i, j));
        }
    }
    //바다 부분을 섬 영역으로 채워가며 거리를 계산하는 bfs
    while (!q.empty())
    {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int nr = dr[k] + r;
            int nc = dc[k] + c;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n)
            if (check[nr][nc] == 0 && a[nr][nc] == 0)
            {
                dis[nr][nc] = dis[r][c] + 1;
                check[nr][nc] = check[r][c];
                q.push(make_pair(nr, nc));
            }                
        }
    }
    int max_val = 10000;
    //최솟값을 찾는 부분
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
    {
        for (int k = 0; k < 4; ++k)
        {
            int nr = dr[k] + i;
            int nc = dc[k] + j;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n)
            {
                if (check[i][j] != check[nr][nc])
                    max_val = min(max_val, dis[i][j] + dis[nr][nc]);
            }
        }
    }
    cout << max_val << endl;
    return 0;
}
cs

디버깅하느라 시간이 좀 걸렸다... 복잡한문제..


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 10972: 다음 순열  (0) 2018.07.17
백준 7576: 토마토  (0) 2018.07.16
백준 2178: 미로 탐색  (0) 2018.07.16
백준 4963: 섬의 개수  (0) 2018.07.16
2667번 : 단지번호붙이기  (0) 2018.07.16
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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> a(101);
int check[102][102];
int dr[4] = { 1, -1, 0, 0 };
int dc[4] = { 0, 0, 1, -1 };
int main()
{
    int n, m;
    //입력을 받아서 동적배열 a에 값들을 채워넣음
    cin >> n >> m;
    cin.get();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            //char로 받는다는 것 주의! 개행문자도 처리해줘야함
            int input = cin.get() - '0';
            a[i].push_back(input);
        }
        cin.get();
    }
 
 
    queue<pair<int, int>> q;
    check[0][0] = 1;
    q.push(make_pair<int>(0, 0));
    //bfs 시작
    while (!q.empty())
    {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int nr = dr[k] + r;
            int nc = dc[k] + c;
            if (nr >= 0 && nr < n && nc >= 0 && nc < m)
            if (check[nr][nc] == 0 && a[nr][nc] == 1)
            {
                check[nr][nc] = check[r][c] + 1;
                q.push(make_pair(nr, nc));
                //이전 check에서 1씩 증가해 나감!
            }
        }
    }
    cout << check[n - 1][m - 1] << endl;
    // 0,0범위부터이므로 1씩 줄여줌!
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 7576: 토마토  (0) 2018.07.16
백준 2146: 다리 만들기  (0) 2018.07.16
백준 4963: 섬의 개수  (0) 2018.07.16
2667번 : 단지번호붙이기  (0) 2018.07.16
백준 1707: 이분 그래프  (0) 2018.07.16

2667번 단지번호 붙이기와 비슷한 맥락의 문제 하지만 8방향이라는 점이 다르다. 나머지 4방향을 추가해주고 입, 출력을 조금 변경해주면 해결할 수 있다.


2667번 코드를 재활용해서 해결하려고 했는데... 조금 시간을 먹었다. 그 이유는 디버깅을 하느라 그랬는데 전역변수의 무서움을 깨달았다. 전역변수와 dfs함수에서 사용되는 변수가 겹쳐서 전역변수가 가려져 답이 이상하게 나왔다. 그리고 케이스마다 벡터와 배열을 초기화하지 않은 것이 문제였다.


플러드필이라고 불리는 이런 문제에는 인접행렬을 이용해 문제를 푼다. 인접행렬을 이용한 dfs의 시간복잡도는 O(접점의 제곱)이니 여기선 O(r*c) r은 행 c는 열이 되겠다.


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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int g_r, g_c;
int num = 0;
vector<vector<int>> a (51);
int check[51][51];
int dr[8] = { 0, 0, 1, -1, 1 ,1, -1, -1};
int dc[8] = { 1, -1, 0, 0, -1, 1, 1, -1};
 
void dfs(int r, int c)
{
    check[r][c] = 1;
    for (int k = 0; k < 8; ++k)
    {
        int nr = dr[k] + r;
        int nc = dc[k] + c;
        if (nr >= 0 && nc >= 0 && nr < g_r && nc < g_c)
            if (check[nr][nc] == 0 && a[nr][nc] == 1)
            {
                dfs(nr, nc);
            }
    }
}
 
int main()
{    
    while (1)
    {
        num = 0;
        cin >> g_c >> g_r;
        if (g_r == 0 && g_c ==0)
            break;
        int input = 0;
        for (int i = 0; i < g_r; ++i)
        {
            for (int j = 0; j < g_c; ++j)
            {
                cin >> input;
                a[i].push_back(input);
            }
        }
        for (int i = 0; i < g_r; ++i)
            for (int j = 0; j < g_c; ++j)
            {
                if (a[i][j] == 1 && check[i][j] == 0)
                {
                    dfs(i, j);
                    num++;
                }
            }
        cout << num << endl;
        for (int i = 0; i < a.size(); ++i)
            a[i].clear();
        for (int i = 0;i < 51; ++i)
        for (int j = 0;j < 51; ++j)
            check[i][j] = 0;
    }    
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 2146: 다리 만들기  (0) 2018.07.16
백준 2178: 미로 탐색  (0) 2018.07.16
2667번 : 단지번호붙이기  (0) 2018.07.16
백준 1707: 이분 그래프  (0) 2018.07.16
백준 11724: 연결요소의 개수  (0) 2018.07.15

dfs, bfs 모두 사용 가능한 문제 나는 dfs를 썻다. 신경써야할 부분은 2차원 배열로 되어 있는 부분에서 정해진 공간을 넘어가지 않기 위해 범위를 설정하는 것과 입력이 공백없이 되어 있어서 cin을 이용해야한다는 것! 탐색보다는 다른부분이 신경쓸게 더 많다.. 비슷한 문제는 솔직히 코드를 카피앤 페이스트하고 싶다. cin.get()은 문자를 입력으로 받아서 1은 사실 31이다 여기서 아스키코드 '0'을 빼주면 실제로 값이 1이된다. 유용한 테크닉인거 같다.


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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n = 0;
int total = 0;
int num = 1;
vector<vector<int>> a (26);
vector<int> ans;
int check[27][27];
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
 
void dfs(int r, int c)
{
    check[r][c] = num;
    ++total;
    for (int k = 0; k < 4; ++k)
    {
        int nr = dr[k] + r;
        int nc = dc[k] + c;
        if (nr >= 0 && nc >= 0 && nr < n && nc < n)
            if (check[nr][nc] == 0 && a[nr][nc] == 1)
            {
                dfs(nr, nc);
            }
    }
}
 
int main()
{    
    cin >> n;
    cin.get();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int input = cin.get() - '0';
            a[i].push_back(input);
        }
        cin.get();
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            if (a[i][j] == 1 && check[i][j] == 0)
            {
                total = 0;
                dfs(i, j);
                num++;
                ans.push_back(total);
            }
        }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); ++i)
        cout << ans[i] << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 2178: 미로 탐색  (0) 2018.07.16
백준 4963: 섬의 개수  (0) 2018.07.16
백준 1707: 이분 그래프  (0) 2018.07.16
백준 11724: 연결요소의 개수  (0) 2018.07.15
백준 1260: DFS와 BFS  (0) 2018.07.15

BFS를 사용해서 풀었다. check 벡터에 0은 방문되지 않은 곳 1은 집합1 2는 집합2로 나누어주고 각 정점에서 탐색을 해주면서 같은 집합으로 이동하는 경우를 발견하면 NO를 출력해주면 된다.


1이후에 2, 2 이후에 1 을 check 벡터에 넣어주기 위해 식을 맨처음 check_num변수를 더하고 모듈로하고 온 갖 썡쑈를해서 계속해서 틀렸습니다를 남발했는데 현재의 값인 x와 다음 값이 temp사이의 관계식을 이용해서 계산하니 정답이 맞았다...


BFS, DFS 뭐로 하든 상관 없겠다. 난 BFS가 더 맘에 든다. 정복해나가는 느낌이어서 


개인적으로 교훈은 내가 세운 식을 너무 믿으면 안될 것 같다. 내가 세운 복잡한 식은 틀리기 마련이다. 문제에서 주어진대로 점화식을 세울려고 노력하자. 



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
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
int main()
{
    //입출력을 받음
    int t_case, vertex, edge, input_1, input_2;
    cin >> t_case;
    //t_case만큼 시도
    for (int i = 0; i < t_case; ++i)
    {
        string result = "YES";
        cin >> vertex >> edge;
        vector<int> check(20001, 0);
        vector<vector<int>> a(20001);
        queue<int> q;
        
        //간선 입력 받기
        for (int i = 0; i < edge; ++i)
        {
            cin >> input_1 >> input_2;
            a[input_1].push_back(input_2);
            a[input_2].push_back(input_1);
        }
        //bfs 활용해서 풀기
        for (int j = 1; j <= vertex; ++j)
        {
            if (check[j] == 0)
            {
                int check_num = 1;
                q.push(j);
                //첫 포인트 체크넘버 설정 by 1
                check[j] = check_num;
                while (!q.empty())
                {
                    int x = q.front(); q.pop();
                    //1과2 를 번갈아 가면서 넣어줌    
                    for (int i = 0; i < a[x].size(); ++i)
                    {
                        int temp = a[x][i];
                        //탐색되지 않은 곳이라면 탐색
                        if (check[temp] == 0)
                        {
                            check[temp] = (check[x] % 2) + 1; //2, 1
                            q.push(temp);
                        }
                        else if (check[temp] == check[x])
                        {
                            //탐색한 곳인데 그곳이 같은 집합에 속한 정점이면
                            result = "NO";
                        }
                    }
                }
            }        
        }
        cout << result << endl;
    }
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 4963: 섬의 개수  (0) 2018.07.16
2667번 : 단지번호붙이기  (0) 2018.07.16
백준 11724: 연결요소의 개수  (0) 2018.07.15
백준 1260: DFS와 BFS  (0) 2018.07.15
백준 1676: 팩토리얼 0의 개수  (0) 2018.07.13

잘 쓴 코드는 주석과 설명이 필요 없다고 하지만 겸손하게 주석은 넣었다!


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
#include <iostream>
#include <vector>
using namespace std;
bool check[1001];
vector<vector<int>> lst(1001);
 
void dfs(int start)
{
    check[start] = true;
    for (int i = 0; i < lst[start].size(); ++i)
    {
        int v = lst[start][i];
        if (check[v] == false)
            dfs(v);
    }
    return;
}
int main()
{
    int vertex, edge;
    cin >> vertex >> edge;
    int input_1, input_2;
    //간선을 2차원 벡터에 저장
    for (int i = 0; i < edge; ++i)
    {
        cin >> input_1 >> input_2;
        lst[input_1].push_back(input_2);
    }
    int link_num = 0;
    for (int i = 1; i <= vertex; ++i)
    {
        //방문되지 않았다면 하나의 연결요소임으로 개수를 늘려준다. 
        if (check[i] == false)
        {
            //dfs로 방문할 수 있는 모든 정점을 방문한다.
            dfs(i);
            link_num++;
        }
    }
    //예상 복잡도 O(V(V+E))
    cout << link_num << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

2667번 : 단지번호붙이기  (0) 2018.07.16
백준 1707: 이분 그래프  (0) 2018.07.16
백준 1260: DFS와 BFS  (0) 2018.07.15
백준 1676: 팩토리얼 0의 개수  (0) 2018.07.13
백준 6588: 골드바흐의 추측  (0) 2018.07.13

깊이우선탐색과 넓이우선탐색의 개념을 잡는 문제, 숫자 순서대로 방문되므로 입력되는 값들을 정렬해주고 또한 간선이 양쪽에 있으니 이 또한 적용해주어야 시작점이 달라졌을 때 답을 올바르게 반영할 수 있다. 벡터를 재귀로 전달해서 그런지 메모리가 상당히 크게나왔다.




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
#include <iostream>
#include <queue>
#include <algorithm>
bool check_bfs[1005];
bool check_dfs[1005];
using namespace std;
 
void dfs(int start, vector<vector<int>> lst)
{
    //방문됬음을 표시
    check_dfs[start] = true;
    cout << start << " ";
    for (int i = 0; i < lst[start].size(); ++i)
    {
        int y = lst[start][i];
        //방문이 되지 않았다면 
        if (check_dfs[y] == false)
            dfs(y, lst);
    }
    return;
}
 
int main()
{
    int vertex, edge, start;
    cin >> vertex >> edge >> start;
    vector<vector<int>> list(vertex + 1);
    int input_1, input_2;
    for (int i = 0; i < edge; ++i)
    {
        cin >> input_1 >> input_2;
        list[input_1].push_back(input_2);
        list[input_2].push_back(input_1);
    }
    for (int i = 0; i < list.size(); ++i)
        sort(list[i].begin(), list[i].end());
    dfs(start, list);
    cout << endl;
    //bfs 시작
    queue<int> q;
    check_bfs[start] = true;
    q.push(start);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        
        cout << x << " ";
        for (int i = 0; i < list[x].size(); ++i)
        {
            if (check_bfs[list[x][i]] == false)
            {
                check_bfs[list[x][i]] = true;
                q.push(list[x][i]);
            }
        }
    }
    cout << endl;
    return 0;
}
cs


저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 1707: 이분 그래프  (0) 2018.07.16
백준 11724: 연결요소의 개수  (0) 2018.07.15
백준 1676: 팩토리얼 0의 개수  (0) 2018.07.13
백준 6588: 골드바흐의 추측  (0) 2018.07.13
백준 1929: 소수구하기(충격의 endl)  (0) 2018.07.13

5의 개수를 세는 것이 핵심적인 문제, 600까지가 조건이므로 5의 세제곱까지만 신경쓰면 되겠다. 


#include <iostream>


int main()

{

int input;

int ans = 0;

std::cin >> input;

for (int i = 1; i <= input; ++i)

{

if (i % 5 == 0)

++ans;

if (i % 25 == 0)

++ans;

        if(i % 125 == 0)

            ++ans;

}

std::cout << ans << std::endl;

return 0;

}

저작자표시 비영리 (새창열림)

'백준 온라인 저지' 카테고리의 다른 글

백준 11724: 연결요소의 개수  (0) 2018.07.15
백준 1260: DFS와 BFS  (0) 2018.07.15
백준 6588: 골드바흐의 추측  (0) 2018.07.13
백준 1929: 소수구하기(충격의 endl)  (0) 2018.07.13
백준 1978: 소수 찾기  (0) 2018.07.13

+ Recent posts

티스토리툴바