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 |