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

 

17244번: 아맞다우산

경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출

www.acmicpc.net

챙겨야 하는 물건은 최대 5개이므로 bfs + 비트마스킹이 가능합니다.

visit[x][y][bit]: 좌표 (x, y)에 도착했을 때 찾은 물건의 비트가 bit인 경우의 방문 처리입니다.

비트를 어떻게 할지 고민하다가 chk배열을 사용하여 해당 좌표에 있는 물건의 비트를 정해주었습니다.

나가는 문에 도착했을 때 모든 물건을 찾았을 때만 t를 출력합니다.

 

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 <queue>
#define MAX 50
using namespace std;
typedef pair<pair<int, int>, int> pii;
 
queue<pii> q;
char list[MAX][MAX];
bool visit[MAX][MAX][1 << 5];
int chk[MAX][MAX];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, bit;
 
void bfs() {
    for (int t = 1; !q.empty(); t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int cnt = q.front().second;
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
                int ncnt = cnt;
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (list[nx][ny] == 'X') {
                    int b = chk[nx][ny];
 
                    ncnt |= b;
                }
                if (list[nx][ny] == '#' || visit[nx][ny][ncnt]) continue;
 
                if (list[nx][ny] == 'E' && ncnt == bit) {
                    cout << t << '\n';
                    return;
                }
 
                q.push({ {nx,ny}, ncnt });
                visit[nx][ny][ncnt] = true;
            }
        }
    }
}
 
void input() {
    int cnt = 0;
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
            if (list[i][j] == 'S') {
                q.push({ {i,j},0 });
                visit[i][j][0] = true;
            }
            else if (list[i][j] == 'X') {
                chk[i][j] = (1 << cnt);
                cnt++;
            }
        }
    }
 
    bit = (1 << cnt) - 1;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    bfs();
 
    return 0;
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 5547 일루미네이션  (0) 2022.05.15
boj 16932 모양 만들기  (0) 2022.05.14
boj 1194 달이 차오른다, 가자.  (0) 2021.04.21
boj 17471 게리맨더링  (0) 2021.04.16
boj 2573 빙산  (0) 2021.04.05

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

 

13701번: 중복 제거

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1

www.acmicpc.net

이 문제는 메모리 제한이 8MB 이므로 2^25만큼의 배열을 사용하면 메모리 초과가 뜹니다.

따라서 이를 수를 구분할 수 있는 몫과 나머지를 이용한 비트마스킹을 이용합니다.

 

인덱스는 몫이 되겠으며, 비트로 사용할 값은 나머지입니다.

x라는 몫에 y라는 나머지가 있는지 비트 연산자로 확인합니다.

y라는 나머지가 있으면 출력, 없으면 return을 시키면 됩니다.

 

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
#include <iostream>
#define MAX 1 + (1 << 20)
using namespace std;
 
int list[MAX];
 
void func(int N) {
    int x = N >> 5;
    int y = N % 32;
    int z = (1 << y);
 
    if (list[x] & z) return;
    list[x] |= z;
    cout << N << ' ';
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int N;
    while (cin >> N) {
        func(N);
    }
 
    return 0;
}
 cs

 

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

 

1648번: 격자판 채우기

준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다. 세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노

www.acmicpc.net

dp + 비트마스킹 문제로 넴모넴모(문제 링크) 문제와 비슷한 방식으로 해결하였습니다.

(안 푸셨으면 풀어 보시는거 추천드립니다 ㅎㅎ)

 

dp[x][bit] : x번 칸부터 M개의 칸의 상태가 bit일 때 x번 칸에 도미노를 놓는 경우의 수

이렇게 두고 해결하였습니다.

 

넴모넴모 문제는 x번 칸 이전의 M + 1개의 칸을 비트로, 이 문제는 x번 칸부터 M개의 칸을 비트로 두었습니다.

그리고 넴모넴모 문제는 x번 칸 뒤에는 채워져있지 않지만 이 문제는 채워져있을 가능성이 있어 확인을 해야하고,

0번 ~ x - 1번 칸은 모두 채워져있도록 로직을 구성하였습니다.

만약 2 * 3 격자판에 칸이 이렇게 채워져있고, x번 칸 차례라고 한다면,

x번 부터 x + (M - 1)번까지 M개의 비트는 역순으로 011로 구성됩니다.

 

우선 위 그림처럼 x번 칸이 이미 채워져있으면 다음 칸(x + 1)으로 넘어갑니다.

 

이렇게 x번 칸이 비워져있을 경우에만 1 * 2 크기나, 2 * 1 크기로 채울 수 있습니다.

위 그럼은 x + 1번 칸이 이미 채워져있으므로 1 * 2 크기는 채울 수 없습니다.

x + M번은 무조건 비어있으므로 2 * 1 크기로 채운 후 다음(x + 1)으로 넘어갈 수 있습니다.

 

이 그림은 x + 1번 칸이 비어있으므로 1 * 2크기를 채운 후 다음(x + 2)으로 넘어갈 수 있습니다.

x + M번은 무조건 비어있으므로 2 * 1 크기로 채운 후 다음(x + 1)으로 넘어갈 수 있습니다.

 

다만 이 그림처럼 맨 밑 칸은 2 * 1을 놓을 수 없으므로 맨 밑 칸이 아닐 경우에만 채워줍니다.

마지막으로 x번이 맨 오른쪽 칸일 경우에는 1 * 2크기로 채울 수 없으므로 맨 오른쪽 칸이 아닐 경우에만 채워줍니다.

 

 

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
#include <iostream>
#include <cstring>
#define MAX 14
#define MOD 9901
using namespace std;
 
int dp[MAX * MAX][1 << MAX];
int N, M;
 
int func(int x, int bit) {
    if (x == N * M) return 1;
 
    int &ret = dp[x][bit];
    if (ret != -1) return ret;
    ret = 0;
 
    if (bit & 1) ret = func(x + 1, (bit >> 1));
    else {
        if (x / M != N - 1) ret = func(x + 1, (bit >> 1) | (1 << (M - 1)));
 
        if (x%M != M - 1 && !(bit & 2)) ret = (ret + func(x + 2, bit >> 2)) % MOD;
    }
 
    return ret;
}
 
void input() {
    cin >> N >> M;
    memset(dp, -1, sizeof(dp));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1135 뉴스 전하기  (0) 2021.11.15
boj 17090 미로 탈출하기  (0) 2021.06.27
boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1311 할 일 정하기 1  (0) 2021.06.21
boj 1577 도로의 개수  (0) 2021.06.20

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

 

14700번: 넴모넴모 (Hard)

첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 1, 000, 000, 007로 나눈 나머지를 출력한다.

www.acmicpc.net

dp + 비트마스킹 문제로 격자판 채우기(문제 링크) 문제와 비슷한 방식으로 해결하였습니다. 

(안 푸셨으면 풀어 보시는거 추천드립니다 ㅎㅎ)

 

dp[x][chk] : x번 칸에서 이전 M + 1개의 칸에 넴모가 채워져있는 상태가 chk인 경우의 수

이렇게 두고 해결하였습니다.

 

격자판 채우기 문제는 x번 칸부터 M개의 칸을 비트로 다루었고, 이 문제는 x번 칸 이전의 M+1개의 칸을 비트로 다루었습니다.

 

우선 맨 왼쪽 칸은 무조건 넴모를 놓을 수 있습니다.. 그 칸에 놓음으로 2 * 2 사각형을 만들 수 없기 때문입니다.

이부분도 생각해주셔야합니다. (x % M == 0 인 곳)

만약 2 * 3 격자판에 칸이 이렇게 채워져있고, x번 칸 차례라고 한다면,

M + 1개의 비트는 x - 1부터 해서 역순으로 1101이라고 생각하시면 됩니다.

그럼 x번 칸에서 봐야할 비트는 (1 << 0) , (1 << 1), (1 << M) 이렇게 3개입니다.

위의 그림에서는 (1 << 1) 비트가 0이므로 x에는 넴모를 올려놓은 것, 올려놓지 않은 것 모두 확인할 수 있습니다.

만약 이 그림이라면 3개의 비트 모두 1이므로 x에는 넴모를 올려놓지 않은 것만 확인하시면 됩니다.

 

 

그리고.. 이 문제가 메모리가 빠듯해서 그런지 1 << 19로 잡아도 메모리 초과가 발생하였습니다.

입력이 N * M <= 300으로 들어오기때문에 10 * 30 이런것도 들어올 수 있다는 것인데

비트는 M + 1개를 다루기 때문에 메모리 공간을 잡는데 어려움이 있었습니다.

17 * 17 = 289이고 18 * 18 = 324이므로 아무리 커도 N과 M 중 작은쪽은 17보다 클 수 없다는 생각을 하였고,

둘 중 작은쪽을 M으로 가게 하였습니다.

 

시간 제한이 2초인데 1.6초로 겨우 AC를 받았습니다..

 

 

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
#include <iostream>
#include <cstring>
#define MOD 1000000007
using namespace std;
 
int dp[301][1 << 18];
int N, M;
 
int func(int x, int chk) {
    if (x == N * M) return 1;
 
    int &ret = dp[x][chk];
    if (ret != -1) return ret;
    ret = 0;
 
    ret = func(x + 1, chk >> 1);
 
    if (!(x % M) || !(chk & (1 << 0)) || !(chk & (1 << 1)) || !(chk & (1 << M))) {
        ret = (ret + func(x + 1, (chk >> 1) | (1 << M))) % MOD;
    }
 
    return ret;
}
 
void input() {
    cin >> N >> M;
    if (N < M) swap(N, M);
    memset(dp, -1, sizeof(dp));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 17090 미로 탈출하기  (0) 2021.06.27
boj 1648 격자판 채우기  (0) 2021.06.22
boj 1311 할 일 정하기 1  (0) 2021.06.21
boj 1577 도로의 개수  (0) 2021.06.20
boj 4781 사탕 가게  (0) 2021.06.19

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

 

1311번: 할 일 정하기 1

N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매

www.acmicpc.net

외판원 문제를 풀때는 dp + 비트마스킹에 적응을 못했어서 푸는데 어려움이 많았지만 이번 문제는 좀 수월하게 했던것 같습니다..

 

dp[x][cost] : x번 사람이 고를 때 x - 1번째 사람까지 골랐던 일의 상태가 cost인 비용의 최솟값

여기서 cost에 비트마스킹을 이용합니다. (N = 20이므로 약 100만 정도의 크기입니다.)

 

저는 번호를 0 ~ N - 1로 두었기때문에 0번 사람부터 차례로 0 ~ N - 1번 일까지 돌면서 고르지 않은 일만 선택하였고,

x가 N일 때 모든 사람이 일을 골랐으면 0, 아니면 INF을 리턴하였습니다.

 

 

+ 음.. 시간과 메모리가 적게 나온 분의 풀이를 보았는데 dp[x][cost]가 아닌 dp[cost]만으로도 해결이 됐습니다..

dp[cost] : 고른 일의 상태가 cost일 때 비용의 최솟값

으로 두고 해결하면 될 것 같습니다! (소스는 같이 올리겠습니다)

 

역시 1차원 배열로 한 것이 시간적으로나 메모리적으로나 많은 이득을 가져갑니다..

 

 

[2차원 배열]

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 20
#define INF 1000000000
using namespace std;
 
int list[MAX][MAX], dp[MAX][1 << MAX];
int N, chk;
 
int func(int x, int cost) {
    if (x == N) {
        if(cost == chk) return 0;
        else return INF;
    }
 
    int &ret = dp[x][cost];
    if (ret != -1) return ret;
    ret = INF;
 
    for (int i = 0; i < N; i++) {
        if (cost & (1 << i)) continue;
 
        ret = min(ret, func(x + 1, cost | (1 << i)) + list[x][i]);
    }
 
    return ret;
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    chk = (1 << N) - 1;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
 
    return 0;
}
 cs

 

 

[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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 20
#define INF 1000000000
using namespace std;
 
int list[MAX][MAX], dp[1 << MAX];
int N, chk;
 
int func(int x, int cost) {
    if (x == N) {
        if(cost == chk) return 0;
        else return INF;
    }
 
    int &ret = dp[cost];
    if (ret != -1) return ret;
    ret = INF;
 
    for (int i = 0; i < N; i++) {
        if (cost & (1 << i)) continue;
 
        ret = min(ret, func(x + 1, cost | (1 << i)) + list[x][i]);
    }
 
    return ret;
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    chk = (1 << N) - 1;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 1648 격자판 채우기  (0) 2021.06.22
boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1577 도로의 개수  (0) 2021.06.20
boj 4781 사탕 가게  (0) 2021.06.19
boj 2186 문자판  (0) 2021.06.19

www.acmicpc.net/problem/1194

 

1194번: 달이 차오른다, 가자.

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,

www.acmicpc.net

기본적인 bfs에 비트마스킹이 더해진 문제입니다.

 

visit[x][y][key] : (x, y)에 도달했을 때 갖고있는 열쇠 종류

문을 열기 위해서는 열쇠를 갖고있어야 하므로 얻은 열쇠를 비트마스킹을 이용하여 관리합니다.

 

로직은 다른 bfs와 똑같이 돌아가며, 확인해야할 조건은

1. 맵 밖으로 나갈 경우

2. 문을 만났을 경우

3. 열쇠를 만났을 경우

4. 해당 좌표를 이미 방문한 경우

5. 벽을 만난 경우

 

1, 4, 5인 경우에는 continue를 해주시면 되고,

2인 경우에는 열쇠가 없는 경우에만 continue를 해주시면 됩니다.

3인 경우에는 열쇠를 추가합니다.

 

탈출에 성공하였으면 현재 시간을 출력해주시고, 큐가 비었는데도 탈출하지 못했으면 -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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Deque<int[]> dq = new ArrayDeque<>();
    static char list[][] = new char[51][51];
    static boolean visit[][][] = new boolean[51][51][64];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M;
 
    static void bfs() {
        for (int t = 0; !dq.isEmpty(); t++) {
            int size = dq.size();
            while (size-- > 0) {
                int x = dq.peek()[0];
                int y = dq.peek()[1];
                int key = dq.poll()[2];
 
                if (list[x][y] == '1') {
                    System.out.println(t);
                    return;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = x + direct[i][0];
                    int ny = y + direct[i][1];
                    int nextKey = key;
 
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                        continue;
                    if ('A' <= list[nx][ny] && list[nx][ny] <= 'F') {
                        int door = list[nx][ny] - 'A';
 
                        if ((key & (1 << door)) == 0)
                            continue;
                    }
                    if ('a' <= list[nx][ny] && list[nx][ny] <= 'f') {
                        nextKey = nextKey | (1 << (list[nx][ny] - 'a'));
                    }
 
                    if (visit[nx][ny][nextKey] || list[nx][ny] == '#')
                        continue;
                    dq.add(new int[] { nx, ny, nextKey });
                    visit[nx][ny][nextKey] = true;
                }
            }
        }
        
        System.out.println(-1);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            for (int j = 0; j < M; j++) {
                if (list[i][j] == '0') {
                    dq.add(new int[] { i, j, 0 });
                    visit[i][j][0] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 16932 모양 만들기  (0) 2022.05.14
boj 17244 아맞다우산  (0) 2021.11.25
boj 17471 게리맨더링  (0) 2021.04.16
boj 2573 빙산  (0) 2021.04.05
boj 14923 미로 탈출  (0) 2021.03.29

www.acmicpc.net/problem/20304

 

20304번: 비밀번호 제작

서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부

www.acmicpc.net

bfs에 비트마스킹까지 해야하는 문제입니다.

 

관리자 계정 비밀번호와 해커가 로그인 시도에 사용된 비밀번호의 안전거리로 계산한 안전도를 최대로 해야합니다.

우선 로그인 시도에 사용된 비밀번호가 관리자 계정 비밀번호와 같으면 안전거리는 0입니다. (고정)

이를 큐에 넣고 비트마스킹을 이용하여 bfs로 탐색을 합니다. 큐에는 번호와 안전도를 유지합니다.

 

이제 1부터 왼쪽시프트를 하면서 x와 &연산을 합니다. (y = x & i)

y > 0이면 같은 자릿수가 있다는 의미이며, x - i를 한 값이 거리가 1인 숫자입니다.

그리고 y == 0이면 같은 자릿수가 없다는 의미이며, x + i를 한 값이 거리가 1인 숫자입니다.

 

이 과정을 반복하여 cnt의 max를 구하여 출력합니다.

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Queue<int[]> q = new LinkedList<>();
    static int visit[];
    static int N, M, ans;
 
    static void bfs() {
        while (!q.isEmpty()) {
            int x = q.peek()[0];
            int cnt = q.poll()[1];
 
            ans = Math.max(ans, cnt);
            for (int i = 1; i <= N; i = i << 1) {
                int y = x & i;
 
                if (y > 0) {
                    if (visit[x - i] != -1)
                        continue;
                    q.add(new int[] { x - i, cnt + 1 });
                    visit[x - i] = cnt + 1;
                } else {
                    if (x + i > N || visit[x + i] != -1)
                        continue;
                    q.add(new int[] { x + i, cnt + 1 });
                    visit[x + i] = cnt + 1;
                }
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        visit = new int[N + 1];
        Arrays.fill(visit, -1);
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            x = Integer.parseInt(st.nextToken());
            q.add(new int[] { x, 0 });
            visit[x] = 0;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 2206 벽 부수고 이동하기  (0) 2021.02.13
boj 14502 연구소  (0) 2021.02.12
boj 2606 바이러스  (0) 2021.02.03
boj 1012 유기농 배추  (0) 2021.02.03
boj 16956 늑대와 양  (0) 2021.02.03

+ Recent posts

티스토리툴바