반응형

문제 링크: https://www.acmicpc.net/problem/2331

 

2331번: 반복수열

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

www.acmicpc.net

<문제 풀이> DFS

이문제는 dfs로 수열을 계속 구하다가 반복 횟수가 2 이상이면 종료하고 반복 횟수가 1인 수열의 개수를 세면 되는 간단한 문제입니다.

 

그런데 문제는 배열의 범위를 설정하는 것입니다.

 

문제에서 A <=9999이고 P <=5라고 했으니깐

처음 시작되는 수의 자릿수의 최대는 4자리입니다.

 

A = x1x2x3x4라고 하면

x1^5 <= 9^5 = 59049

x2^5 <= 9^5 = 59049

x3^5 <= 9^5 = 59049

x4^5 <= 9^5 = 59049

 

따라서 

x1^5 + x2^5 + x3^5 +x4^5 <= 236196 

 

위를 통해서 A로 만들 수 있는 다음 수는 아무리 커도 6자리를 넘지 못합니다.

 

그러면 만약에 6자리가 모두 9로 이루어졌다고 가정하고 다시 계산해보겠습니다.

 

A = x1x2x3x4x5x6라고 하면

x1^5 <= 9^5 = 59049

x2^5 <= 9^5 = 59049

x3^5 <= 9^5 = 59049

x4^5 <= 9^5 = 59049

x5^5 <= 9^5 = 59049

x6^5 <= 9^5 = 59049

 

따라서

x1^5 + x2^5 + x3^5 +x4^5  + x5^5 + x6^5 <= 354294

 

위를 통해서 6자리로 최대 6자리까지만 만들 수 있으니깐, 수의 최대 자릿수는 6자리를 넘지 못한다는 걸 알 수 있습니다.

 

 

 

 

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int arr[1000000];
 
int a, p;
 
int pow(int x, int n) {
    int temp = x;
    for (int i = 0; i < n - 1; i++) {
        x *= temp;
    }
    return x;
}
 
void dfs(int a) {
    int res = 0;
    while (a) {
        int r = a % 10;
        res += pow(r, p);
        a = a / 10;
    }
    if (arr[res] < 2) {
        arr[res]++;
        dfs(res);
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> a >> p;
    arr[a]++;
    dfs(a);
    int cnt = 0;
    for (int i = 1; i <= 1000000; i++) {
        if (arr[i] == 1)cnt++;
    }
    cout << cnt;
 
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1167번] 트리의 지름  (0) 2021.12.16
[백준 1967번] 트리의 지름  (0) 2021.12.13
[백준 16920번] 확장 게임  (0) 2021.12.08
[백준 11967번] 불켜기  (0) 2021.12.04
[백준 3197번] 백조의 호수  (0) 2021.12.02
반응형

문제 링크: https://www.acmicpc.net/problem/16920

 

16920번: 확장 게임

구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위

www.acmicpc.net

<문제 풀이> BFS 알고리즘

라운드마다 각 플레이어 별로 BFS를 돌리면 되는데, i번 플레이어의 최대 이동 횟수를 큐가 비었는지를 검사하는 while문에 같이 넣고 1씩 감소시켜주면 됩니다.

+ 최대 이동 횟수를 while문에 같이 넣어주면 플레이어의 모든 성을 최대 이동 횟수까지 움직여볼 수 있음

+ while문을 한번 돌 때 큐 안에는 플레이어의 각 성에서 움직인 거리가 같은 정점들로 구성되어 있습니다.

<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
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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
#define X first 
#define Y second 
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0 , -1, 0};
vector<pair<int, int> > player[10]; 
int res[10];
int s[10]; 
char board[1000][1000];
int n, m, p;
 
void bfs() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] != '.' && board[i][j] != '#') {
                player[board[i][j] - '0'].push_back({ i, j });
            }
        }
    }
    queue< pair<int, int > > Q[10];
    for (int i = 1; i <= p; i++) {
        for (auto castle : player[i]) {
            Q[i].push({ castle.X, castle.Y });
            res[i]++;
        }
    }
 
    while (true) { //라운드 시작
        bool success = false;
        for (int i = 1; i <= p; i++) { //1번 플레이부터 시작
            int s_len = s[i]; //i번 플레이어의 최대 이동 횟수
            while (!Q[i].empty() && s_len--) { // i번 플레이어 BFS 
                int Q_size = Q[i].size();
                for(int j=0; j<Q_size; j++){
                    auto cur = Q[i].front(); Q[i].pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || ny < 0 || nx >= n || ny >= m)continue;
                        if (board[nx][ny] == '.') { // 성을 건설할 수 있으면
                            Q[i].push({ nx, ny });
                            board[nx][ny] = board[cur.X][cur.Y];
                            res[i]++;
                            success = true;
                        }
                    }
                }
            }
 
        }
        if (!success) break;
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m >> p;
    for (int i = 1; i <= p; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
    bfs();
   
    for (int i = 1; i <= p; i++) {
        cout << res[i] << ' ';
    }
  
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1967번] 트리의 지름  (0) 2021.12.13
[백준 2331번] 반복수열  (0) 2021.12.12
[백준 11967번] 불켜기  (0) 2021.12.04
[백준 3197번] 백조의 호수  (0) 2021.12.02
[백준 4963번] 섬의 개수  (0) 2021.11.25
반응형

문제 링크: https://www.acmicpc.net/problem/11967

 

11967번: 불켜기

(1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으

www.acmicpc.net

<문제 풀이> BFS

(1, 1)에서 동서남북으로 BFS를 진행하면 되는데,

 

큐에서 꺼낼 때 현재 위치에서 불을 켤 수 있는 모든 방의 불을 켜고, 불이 켜진 방을 현재까지 왔던 경로를 이용해서 들어갈 수 있다면 그 방의 좌표를 큐에 넣으면 됩니다. 

 

현재까지 왔던 경로를 이용해서 불이 켜진 방에 들어갈 수 있는지를 확인하는 방법은 불이 켜진 방의 동서남북을 확인해서 이전에 방문한 적이 있다면 들어갈 수 있는 방이 됩니다.

 

왜냐하면 (1, 1)에서 부터 한 칸씩 이동하기 때문에 (x, y) 정점에 방문 체크가 되어 있다는 건 (x, y)까지 경로가 존재한다는 것입니다.

 

그래서 동서남북 방문체크만 하고 바로 큐에 넣으면 됩니다.

 

<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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0 , -1, 0};
 
vector<pair<int, int>> avail[101][101];
bool visited[101][101]; 
bool on[101][101]; 
int cnt = 0;
int n, m;
void bfs() {
    queue<pair<int, int>> Q;
    Q.push({ 1, 1 });
    visited[1][1] = true;
    on[1][1] = true;
    cnt++;
    for (auto room : avail[1][1]) {
        if (!on[room.X][room.Y]) {
            on[room.X][room.Y] = true;
            cnt++;
        }
    }
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (auto& room : avail[cur.X][cur.Y]) {
            if (!on[room.X][room.Y]) { //cur의 모든 스위치 누르기
                on[room.X][room.Y] = true;
                cnt++;
                for (int dir = 0; dir < 4; dir++) {
                    int nx = room.X + dx[dir];
                    int ny = room.Y + dy[dir];
                    if (nx < 1 || ny < 1 || nx> n || ny >n)continue;
                    if (visited[nx][ny]) { //불을 켠 방을 이동할 수 있으면
                        Q.push({ room.X, room.Y }); // 다음에 불을 켠 방에서 탐색 시작
                        visited[room.X][room.Y] = true;
                        break;
                    }
                }
            }
        }
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 1 || ny < 1 || nx> n || ny >n)continue;
            if (!on[nx][ny] || visited[nx][ny]) continue;
            Q.push({ nx, ny });
            visited[nx][ny] = true;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        avail[x][y].push_back({ a, b });
    }
    bfs();
    cout << cnt;
 
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2331번] 반복수열  (0) 2021.12.12
[백준 16920번] 확장 게임  (0) 2021.12.08
[백준 3197번] 백조의 호수  (0) 2021.12.02
[백준 4963번] 섬의 개수  (0) 2021.11.25
[백준 1600번] 말이 되고픈 원숭이  (0) 2021.11.25
반응형

문제 링크: https://www.acmicpc.net/problem/3197

 

3197번: 백조의 호수

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

www.acmicpc.net

<문제 풀이> BFS

하루가 지날 때마다 모든 물을 확인해서 얼음을 녹이고 백조의 처음 시작 위치에서 BFS를 돌리면

얼음을 녹이는데 O(RC), 백조 BFS O(RC)

->O(R^2 * C^2)이 되기 때문에 시간 초과가 나게 됩니다.

 

그래서 시간을 단축하는 방법은

1. 하루가 지날 때 마다 빙판을 녹일 물을 탐색하는데 이미 확인했던 물은 무시

2. 물 주위에 빙판은 다음에 물이 되니깐 빙판을 물로 바꾸고 다음에 물의 탐색을 그 빙판이 있던 'X' 위치에서 시작합니다.

-> 다음 물의 시작 위치를 저장하고 있어야 되기 때문에 임시 큐가 필요합니다. (tempWater)

 

그리고 하루가 지날 때마다 백조 한 마리를 BFS로 움직여보면 되는데

1. 하루가 지날 때 마다 백조를 움직일 때 이미 방문했던 물은 무시

->이미 방문했던 물을 무시해도 되는 이유는 백조의 경로가 중요하지 않기 때문입니다.

->빙판 때문에 막혀서 못만났으니깐 백조를 처음 위치에서 다시 시작할 필요 없이 빙판을 만난 직전의 위치에서 시작하면 됩니다. 

2. 백조가 다른 백조를 만나면 종료

3. 백조의 다음 위치가 빙판 'X'이면 다음 날에 현재 위치부터 다시 백조 BFS 진행

->다음 백조의 시작 위치를 저장하고 있어야 되기 때문에 임시 큐가 필요합니다.(tempSwan)

<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
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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
char board[1500][1500];
bool visited[1500][1500];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int r, c;
int res = 0;
void bfs() {
    queue<pair<int, int> > swan;
    queue<pair<int, int>> tempSwan;
    queue<pair<int, int> > water;
    queue<pair<int, int> > tempWater;
    bool found = false;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (board[i][j] == '.') {
                water.push({ i, j });
            }
            else if (!found && board[i][j] == 'L') {
                swan.push({ i, j });
                visited[i][j] = true;
                found = true;
                water.push({ i, j });
            }
            else if (found && board[i][j] == 'L') {
                water.push({ i, j });
            }
        }
    }
    while (true) {
        while (!tempSwan.empty()) { //백조의 다음 시작 위치를 백조 큐에 넣음
            swan.push(tempSwan.front());
            visited[tempSwan.front().X][tempSwan.front().Y] = true;
            tempSwan.pop();
        }
        while (!swan.empty()) { //백조 이동 BFS
            auto cur = swan.front(); swan.pop();
            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                if (visited[nx][ny]) continue;
                if (board[nx][ny] == '.') {
                    visited[nx][ny] = true;
                    swan.push({ nx, ny });
                }
                else if (board[nx][ny] == 'X') {
                    tempSwan.push({ cur.X, cur.Y });
                }
                else if (board[nx][ny] == 'L') {
                    return;
                }
            }
        }
        res++;
        while (!water.empty()) { //얼음 녹이기 BFS
            auto cur = water.front(); water.pop();
            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                if (visited[nx][ny]) continue;
                if (board[nx][ny] == 'X') {
                    board[nx][ny] = '.';
                    tempWater.push({ nx, ny });
                }
            }
        }
        while (!tempWater.empty()) { //물의 다음 시작 위치는 얼음이 녹은 위치
            water.push(tempWater.front());
            tempWater.pop();
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
    bfs();
    cout << res;
    return 0;
}
 
 cs
반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 16920번] 확장 게임  (0) 2021.12.08
[백준 11967번] 불켜기  (0) 2021.12.04
[백준 4963번] 섬의 개수  (0) 2021.11.25
[백준 1600번] 말이 되고픈 원숭이  (0) 2021.11.25
[백준 17071번] 숨바꼭질 5  (0) 2021.11.25
반응형

문제 링크:https://www.acmicpc.net/problem/4963

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

 

<문제 풀이> BFS

8방향 BFS를 돌리고 큐가 빌 때마다 섬의 개수를 카운트하면 됩니다.

 

<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
62
63
64
65
66
67
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
int w, h;
int board[50][50];
bool visited[50][50];
 
int dx[8] = {0 ,-1, -1, -1, 0, 1, 1, 1};
int dy[8] = { 1, 1, 0,-1,-1,-1, 0, 1};
 
int bfs() {
    queue<pair<int, int> > Q;
    int res = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (!visited[i][j] && board[i][j] == 1) {
                Q.push({ i, j });
                visited[i][j] = true;
                while (!Q.empty()) {
                    auto cur = Q.front(); Q.pop();
                    for (int dir = 0; dir < 8; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || ny < 0 || nx >= h || ny >= w)continue;
                        if (board[nx][ny] == 0 || visited[nx][ny])continue;
                        Q.push({ nx, ny });
                        visited[nx][ny] = true;
                    }
                }
                res++;
            }
        }
    }
    return res;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    while (true) {
        cin >> w >> h;
        if (w == 0 && h == 0) break;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin>> board[i][j];
            }
        }
        cout << bfs()<< '\n';
        fill(&board[0][0], &board[49][50], 0);
        fill(&visited[0][0], &visited[49][50], 0);
    }
 
 
    return 0;
}
 
 cs
반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 11967번] 불켜기  (0) 2021.12.04
[백준 3197번] 백조의 호수  (0) 2021.12.02
[백준 1600번] 말이 되고픈 원숭이  (0) 2021.11.25
[백준 17071번] 숨바꼭질 5  (0) 2021.11.25
[백준 12851번] 숨바꼭질2  (0) 2021.11.22
반응형

문제 링크: https://www.acmicpc.net/problem/1600

 

1600번: 말이 되고픈 원숭이

첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있

www.acmicpc.net

<문제 풀이> BFS

 

어떤 위치에 도달했을 때 지금까지 말처럼 몇 번을 이동해서 왔는지를 좌표와 함께 저장하는 클래스를 두고

BFS를 돌리면 되는데  다음 좌표인 nx, ny에 도달했을 때 방문 체크를 k개를 해야 합니다.

nx, ny까지 말처럼 이동한 횟수가 0일 때

nx, ny까지 말처럼 이동한 횟수가 1일 때

                   .

                   .

nx, ny까지 말처럼 이동한 횟수가 k일 때

 

 

그리고 현재 좌표인 cx, cy에서 지금까지 말처럼 이동한 횟수가 k보다 작을 경우엔

나이트 이동 방향 8개 + 동서남북 4방향을 push 하고

k보다 크거나 같은 경우엔 동서남북 4방향만 push 하면 됩니다.

 

말이 목적지에 도착하면

 

말처럼 0번 이동해서 올 경우

말처럼 1번 이동해서 올 경우

                  .

                  .

말처럼 k번 이동해서 올 경우

k + 1가지 경우의 최솟값을 return 하면 됩니다.

 

 

<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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
int h_dx[8] = { -2 ,-1, 1, 2, -2, -1, 1, 2 };
int h_dy[8] = { -1 ,-2, -2, -1, 1, 2, 2, 1 };
int dx[4] = { 0,-1, 0 , 1 };
int dy[4] = { 1, 0, -1 , 0 };
int board[200][200];
int visited[200][200][31];
 
int k, w, h;
int res = INT_MAX;
class pos {
public:
    int x;
    int y;
    int t; //말처럼 이동한 횟수
    pos(int x, int y, int t) : x(x), y(y), t(t) {
    }
};
 
int bfs() {
    queue<pos> Q;
    Q.push({ 0, 0, 0 });
    visited[0][0][0] = 1;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (cur.x == h - 1 && cur.y == w - 1) { // 목적지에 도착
            for (int i = 0; i <= 30; i++) {
                if (visited[cur.x][cur.y][i]) {
                    res = min(res, visited[cur.x][cur.y][i]);
                }
            }
            return res - 1;
        }
        if (cur.t < k) {
            for (int dir = 0; dir < 8; dir++) {
                int nx = cur.x + h_dx[dir];
                int ny = cur.y + h_dy[dir];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                if (board[nx][ny] == 1 || visited[nx][ny][cur.t + 1]) continue;
                Q.push({ nx, ny, cur.t + 1 });
                visited[nx][ny][cur.t + 1] = visited[cur.x][cur.y][cur.t] + 1;
            }
 
        }
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
            if (board[nx][ny] == 1 || visited[nx][ny][cur.t]) continue;
     
            Q.push({ nx, ny, cur.t });
            visited[nx][ny][cur.t] = visited[cur.x][cur.y][cur.t] + 1;
 
        }
    }
    return -1; // 말이 목적지에 도착을 못함
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> k>>w >> h;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> board[i][j];
        }
    }
    cout << bfs();
 
    return 0;
}
 
 cs

 

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 3197번] 백조의 호수  (0) 2021.12.02
[백준 4963번] 섬의 개수  (0) 2021.11.25
[백준 17071번] 숨바꼭질 5  (0) 2021.11.25
[백준 12851번] 숨바꼭질2  (0) 2021.11.22
[백준 13913번] 숨바꼭질4  (0) 2021.11.21
반응형

문제 링크: https://www.acmicpc.net/problem/17071

 

17071번: 숨바꼭질 5

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

<문제 풀이> BFS

수빈이가 정점 n에 있을 때 시간을 t라고 하면 동생의 위치는 (등차수열의 합 공식을 사용해서 구하면)

k + t*(t+1)/2에 있습니다.

 

수빈이의 위치와 시간을 저장하는 큐를 만들고 BFS를 돌리고

큐에서 pop을 할 때  t초 후 동생과 수빈이가 n에서 만나는지를 확인하면 됩니다.

 

그런데 n 제한이 50만이기 때문에 여기서 모든 정점을 큐에 넣으면 시간 초과, 메모리 초과가 나게 됩니다.

적절하게 방문 체크를 해서 이미 큐에 넣은 정점은 큐에 다시 넣지 않게 해야 됩니다.

 

문제의 입력을 트리 형태로 그려보면 수빈이가 정점 n을 t초에 방문했을 때 짝수 초 후에 그 정점을 다시 방문할 수 있다는 것을 알 수 있습니다. 

(-1 -> +1 하면 제자리)

 

그러면 BFS를 진행하면 정점 n일 때 레벨 t을 알 수 있으니깐 t초 일 때 동생의 위치 n을 구해서

수빈이가 위치 n을 짝수 초에 방문했는지, 홀수 초에 방문했는지를 visited 배열로 체크하면 됩니다.

(만약 수빈이가 홀수 초에만 n에 방문하고 동생이 짝수 초에만 n에 방문하면 서로 만날 수 없음)

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
int n, k; 
bool visited[500001][2];
 
int bfs() {
    queue<pair<int, int> > Q;
    Q.push({ n, 0 });
    visited[n][0] = true;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (k + cur.Y * (cur.Y + 1) / 2 > 500000) {
            return -1;
        }
        if (visited[k + cur.Y * (cur.Y + 1) / 2][cur.Y % 2]) {
            return cur.Y;
        }
        if (2 * cur.X <= 500000 && !visited[2 * cur.X][(cur.Y + 1) % 2]) {
            Q.push({2 * cur.X, cur.Y + 1 });
            visited[2 * cur.X][(cur.Y + 1) % 2] = cur.Y + 1;
        }
        if (cur.X + 1 <= 500000 && !visited[cur.X + 1][(cur.Y + 1) % 2]) {
            Q.push({cur.X + 1, cur.Y + 1 });
            visited[cur.X + 1][(cur.Y + 1) % 2] = cur.Y + 1;
        }
        if (cur.X - 1 >= 0 && !visited[cur.X - 1][(cur.Y + 1) % 2]) {
            Q.push({cur.X - 1, cur.Y + 1 });
            visited[cur.X - 1][(cur.Y + 1) % 2] = cur.Y + 1;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> k;
    cout << bfs();
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 4963번] 섬의 개수  (0) 2021.11.25
[백준 1600번] 말이 되고픈 원숭이  (0) 2021.11.25
[백준 12851번] 숨바꼭질2  (0) 2021.11.22
[백준 13913번] 숨바꼭질4  (0) 2021.11.21
[백준 6593번] 상범 빌딩  (0) 2021.11.19
반응형

문제 링크: https://www.acmicpc.net/problem/12851

 

12851번: 숨바꼭질 2

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

 

<문제 풀이> BFS
https://www.acmicpc.net/problem/1697

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

1697번 문제와 비슷한데

1697번 문제에서는 큐에 push를 할 때 방문 체크를 해줬는데 이문제에서는 큐에서 pop 할 때 방문 체크를 해야 합니다.

왜냐하면 push를 할 때 방문 체크를 해버리면 같은 레벨에서 n=k을 만족하는 정점을 다시 넣을 수 없기 때문입니다.

 

1. 큐에서 pop 할 때 방문 체크

2. n=k을 만족하는 정점의 level 보다 더 큰 level을 가진 정점을 만나면 종료

3. n=k을 만족하는 정점을 최초로 찾았을 때 level 저장

->두 번째 부터는 개수만 카운트

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
int n, k; 
int visited[100001];
int res = 0;
int level = -1;
void bfs() {
    queue<pair<int, int> >Q;
    Q.push({n, 0});
    
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        visited[cur.X] = true;
        if (level != -1 && cur.Y > level) return;
 
        if (level == -1 && cur.X == k) { //최초 발견
            level = cur.Y;
            res++;
        }
        else if (level != -1 && cur.X == k) {//2회 이상 발견
            res++;
        }
        if (2 * cur.X <= 100000 && !visited[2 * cur.X]) {
            Q.push({ 2 * cur.X, cur.Y + 1});
        }
        if (cur.X - 1 >= 0 && !visited[cur.X - 1]) {
            Q.push({cur.X - 1, cur.Y + 1 });
 
        }
        if (cur.X + 1 <= 100000 && !visited[cur.X + 1]) {
            Q.push({cur.X + 1, cur.Y + 1 });
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> k;
 
    bfs();
    cout << level <<'\n';
    cout << res;
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1600번] 말이 되고픈 원숭이  (0) 2021.11.25
[백준 17071번] 숨바꼭질 5  (0) 2021.11.25
[백준 13913번] 숨바꼭질4  (0) 2021.11.21
[백준 6593번] 상범 빌딩  (0) 2021.11.19
[백준 5014번] 스타트링크  (0) 2021.11.19

+ Recent posts

티스토리툴바