[백준] 20304 - 비밀번호 제작 - 플레 5

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• BFS, 비트마스킹

---

1. 문제설명

간단하게 설명하면 다음과 같습니다.

 

서버 관리자가 사용하는 비밀번호의 최대 갯수 N과 해커가 비밀번호를 뚫기 위해 시도한 횟수 M 그리고 그 비밀번호 숫자가 주어집니다.

 

두 비밀번호의 안전 거리는 이진법으로 표현한 두 비밀번호의 서로 다른 자리의 개수로 정의합니다

예를 들어 3을 2진수로 표현하면 0011 이고

8을 2진수로 표현하면 1000 입니다.

 

이때 두 비밀번호의 안전거리는 3입니다.

 

또한 해커가 4역시 시도했을때 4와 8의 안전거리를 구하면

4는 0100

8은 1000 이니 두 비밀번호의 안전거리는 2가 됩니다.

 

앞서 구한 두 비밀번호의 안전 거리중 더 작은 값을 안전도 라고 할때

비밀번호의 안전도가 최댓값이 되는 안전도를 구하는 문제입니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 1024MB
• 0 ≤ N ≤ 1000000
• 1 ≤ M ≤ 100000
• 로그인 시도에 사용된 비밀번호 정수값 P1, P2, ... ,PM 0 ≤ PM ≤ N

---

2. 접근방식

우선 N과 M을 볼때 최대 백만과 십만이 주어집니다. 단순히 큐에 0부터 100만 까지의 숫자를 넣고 해당 숫자를 하나씩 뽑아 비밀번호 M과 비교한다면 O(NM) 으로 최악의 경우 2의 11승 계산을 실시하니 무조건 시간초과가 발생할 겁니다.

 

따라서 이번에는 비트마스킹을 사용해 문제를 해결할 겁니다.

 

비트마스킹을 하기 위해서 해밍 거리를 계산할 필요가 있습니다.

왜냐하면 이번에 저희가 찾을 안전 거리가 두 숫자의 비트의 해밍 거리이기 때문이죠

 

그럼 최대 100만 이니 이를 2진수로 변경하면 20자리의 숫자가 나옵니다.

 

그럼 모든 숫자가 다를경우 해밍 거리는 20일테고 우리는 21로 해밍거리를 초기화 해서 N까지 포함된 방문 처리 배열을 생성해 주면 되겠죠

 

그 다음 queue에는 도둑이 뚫기 위해 사용했던 초기 비밀번호를 넣고 그 번호와 같은 번호는 해밍거리가 0이니 0으로 초기화 하면 될것 같습니다.

 

이제 두 문자의 제대로된 해밍 거리를 계산하기 위해 XOR 비트 연산자를 사용해 줄 겁니다.

 

XOR 비트 연산자는 두 비트가 서로 다른 경우 1 그렇지 않은 경우 0을 반환하는 연산자입니다.

 

현재 queue에는 도둑이 뚫기 위해 사용했던 비밀번호가 담겨 있을 테니 해당 숫자와 새로운 숫자를 비교해 안전 거리를 구하고 그 안전거리 중 최소값인지 확인하고 그 최솟값들 중 최대값을 찾아 안전도로 바꿔주면 됩니다.

---

3. 코드

import sys
input = sys.stdin.readline
from collections import deque

# 입력
N = int(input())
M = int(input())
password = list(map(int, input().split()))
bit_length = N.bit_length()     # -> 입력받은 N에 따라 비트 자리수 계산

# 안전거리
visited = [bit_length + 1 for _ in range(N + 1)]
queue = deque()

for ps in password:
    visited[ps] = 0
    queue.append(ps)

# 최대값을 찾기 위해 0으로 초기화
answer = 0
while queue:
    current_password = queue.popleft()

    # 비트 자리수 비교
    for i in range(bit_length):
        temp_password = (1<<i) ^ current_password

        # 최소 안전 거리 구하기
        if temp_password <= N and visited[current_password] + 1 < visited[temp_password]:
            visited[temp_password] = visited[current_password] + 1

            # 안전도 찾기
            answer = max(visited[temp_password], answer)
            queue.append(temp_password)

print(answer)

---

[코드설명]

import sys
input = sys.stdin.readline
from collections import deque

# 입력
N = int(input())
M = int(input())
password = list(map(int, input().split()))
bit_length = N.bit_length()     # -> 입력받은 N에 따라 비트 자리수 계산

 

입력을 받고 구해야 할 최대 비트 수를 계산해 줍니다.

 

N이 100만 이라면 bit_length 는 20이 됩니다.

---

# 안전거리
visited = [bit_length + 1 for _ in range(N + 1)]
queue = deque()

for ps in password:
    visited[ps] = 0
    queue.append(ps)

 

입력받은 N은 최대 해밍 거리인데 여기에 +1만 해주면 모든 경우의 수 중 최솟값을 구할 수 있으니 N + 1 로 visited 배열 초기화

 

그 후 도둑이 뚫기 위해 사용한 숫자는 해밍 거리가 0이니 해당 위치에 0으로 초기화 해주고 queue에 넣어줌

---

# 최대값을 찾기 위해 0으로 초기화
answer = 0
while queue:
    current_password = queue.popleft()

    # 비트 자리수 비교
    for i in range(bit_length):
        temp_password = (1<<i) ^ current_password

        # 최소 안전 거리 구하기
        if temp_password <= N and visited[current_password] + 1 < visited[temp_password]:
            visited[temp_password] = visited[current_password] + 1

            # 안전도 찾기
            answer = max(visited[temp_password], answer)
            queue.append(temp_password)

 

여기서 초기 queue에는 3과 4가 들어가 있죠

 

3과 4부터 시작해서 현재 수와 해밍 거리가 1 차이나는 수들을 구해줄겁니다.

 

XOR 연산이 두 비트가 서로 다른 경우 1을 반환한다고 했습니다.

 

즉 서로 같은 비트면 0을 반환하고 서로 달라야지만 1을 반환한다는 뜻입니다.

 

그럼 현재 새로이 생성한 1<<i 는 1<<0 과 동일하고 이는 0번째 위치가 1인 비트 입니다.

 

즉 0001을 의미하고 이 0001과 0011의 XOR 연산을 실시하면 0010이 현재 임시 비밀번호인 겁니다.

 

여기서 임시 비밀번호가 이전 비밀번호와 해밍 거리가 1차이 난다면 해당 수를 visited 배열에 업데이트 하고 queue에 넣어줄 겁니다.

 

만약 그렇지 않다면 구할 필요가 없습니다.

 

우리는 안전 거리 중 최소값을 찾을 것이고 그 최솟값 중 최댓값을 찾을 겁니다.

 

해밍 거리 0을 제외한 최소값은 해밍 거리 1이니 XOR 연산을 이용해 1의 갯수가 1 차이나는 비트를 만들고 그걸 queue에 넣어 줌으로써 점점 해밍 거리의 차이가 큰 값들을 visited 배열에 초기화 해 나가는 방식입니다.

 

그럼 모든 동작을 실시 했을때 해당 해밍 거리가 현재 정답보다 큰 경우 answer를 계속 업데이트 해줍니다.

 

그 후 출력을 하면 되겠

---

 

4. 결과

---

[회고]

이번 문제는 해결하는데 시간이 오래 걸렸습니다.

 

비트 마스킹이 생소하기도 했고 문제 조건을 어떻게 설정하지가 큰 관건 이었습니다.

 

우선 비트 마스킹부터 이해할 필요가 있어 구글링을 통해 비트 마스킹을 알아 보았습니다.

 

왼쪽 시프트 연산자는 현재 값을 기준으로 2배 큰 값들을 생성합니다. 1<<0 이면 1 1<<1 이면 2 1<<2 면 4 이런식이었습니다.

 

또한 XOR 연산자가 핵심이었는데

 

두 비트를 비교하는 과정에서 우리가 찾을 값은 최솟값 이었습니다.

 

처음에는 모든 경우를 찾고 비교하려 하였는데 N이 최대 100만이고 M이 최대 10만이라 최악의 경우 100만 X 10만으로 1000억번 의 연산이 발생하기 때문에 이건 아닌것 같았고 결국 최솟값들을 계속 찾아가면 시작 값을 기준으로 비트의 차이가 더 늘어나는 것 아닐까 라는 생각으로 시프트 연산자와 XOR 연산자를 이용할 수 있었습니다.

 

시작 값을 queue에 넣었을 때 현재 값을 기준으로 해밍 거리가 최솟값이 되려면 자기 자신을 제외한 1뿐이었고 3과 해밍 거리가 1 차이나는 비트를 구해주면 되는 거엿습니다.

 

그렇게 생각하고 코드를 짜려니 이번엔 비트 수를 구하는게 문제였습니다.

 

bin으로 구한 2진수는 0bxxx 형태의 숫자 인데 필요없는 0b가 붙어있고 모든 자릿수가 통일되지가 않았습니다.

 

그러다보니 자리수 비교가 까다로웠는데 이것 역시 구글링을 통해 해결할 수 있었습니다.

 

찾다보니 bit_length 함수를 알게 되었고 이게 입력받은 N값을 기준으로 비트의 자릿수를 구하는 함수인걸 알게 되어 이걸 토대로 반복문을 돌릴 수 있었습니다.

 

반복문을 돌리며 비트 자릿수를 비교해 해밍 거리가 1 차이가 맞다면 해당 위치를 방문 처리하고 그렇지 않은 경우는 다음 번 탐색에서 1차이나는 해밍 거리를 구하면 되는 거였습니다.

 

이전 위치와 1차이가 난다면 이게 누적되면 시작 값 3, 4 와는 해밍 거리가 더 차이가 날 수 밖에 없었고 그 중 최대값을 찾아주면 되는 거였습니다.

 

어려운 문제였고 해결에도 오래 걸린 문제였습니다.

 

비트 마스킹이 생소해 문제를 풀며 모르는 개념이나 헷갈리는 개념은 구글링을 통해 알아가며 문제를 해결하였습니다.