해밍거리 + BFS 경로 역추적하기

2479번: 경로 찾기

 

이진 코드들이 주어질때, A 이진코드에서 B 이진코드로 가는 경로를 찾을려고 한다

 

이때 경로를 구성한 노드간 서로 인접한 코드끼리의 해밍거리가 1이어야한다

 

해밍거리는 길이가 같은 두 이진코드들에서 왼쪽부터 오른쪽으로 차례로 비교할 때 서로 다른 값을 가진 비트의 수이다

 

예를 들어 010과 110은 서로 다른 비트가 0번째 비트로 1개이므로 해밍 거리가 1이다

 

코드 번호 A,B가 주어질때 가장 짧은 해밍 경로를 찾는다

 

--------------------------------------------------------------------------------------------------------------------------------------------------

 

두 코드간 해밍거리를 모두 구하고 BFS나 DFS로 A에서 B까지 해밍경로를 찾는다

 

BFS나 DFS중에 해밍거리를 구하면 중복해서 계산하기 때문에 비효율적이다

 

BFS나 DFS하기 전에 해밍거리를 미리 구해놓는다

 

생각해보면 두 노드간 이동은 두 노드간 해밍거리가 1일때만 가능하므로,

 

해밍거리가 1인 경우에 두 노드가 이동 가능하다고 간선을 구성하여 그래프를 구성하면 된다

 

from collections import deque
from sys import stdin

n,k = map(int,stdin.readline().split())

A = [0]

for _ in range(n):

    s = stdin.readline().rstrip()
    A.append(s)

dp = [[0]*(n+1) for _ in range(n+1)]
graph = [[] for _ in range(n+1)]

for a in range(1,n+1):

    for b in range(a,n+1):

        for c in range(len(A[a])):

            if A[a][c] != A[b][c]:

                dp[a][b] += 1
            
        dp[b][a] = dp[a][b]

for a in range(1,n+1):
    
    for b in range(1,n+1):
        
        if dp[a][b] == 1:
            
            graph[a].append(b)
            graph[b].append(a)

 

 

어차피 a에서 b까지 해밍거리랑 b에서 a까지 해밍거리는 같으므로 dp[b][a] = dp[a][b]로 조금 시간 단축은 가능

 

dp[a][b]로 a와 b사이 해밍거리를 모두 구해놓고 두 해밍거리가 1인 경우만 이동가능하도록 그래프를 구성

 

이제 BFS를 수행하면서 A에서 B까지 가는 해밍경로 중 최단 경로를 찾는다

 

여기서 핵심은 u에서 v로 이동가능하다고 할때, prev배열을 이용해서 prev[v] = u로 v의 이전 노드를 표시해두어야한다

 

그래야 b부터 시작해서 역으로 추적해서 경로를 찾을 수 있다

 

a,b = map(int,stdin.readline().split())
            
queue = deque([(a,1)])
visited = [0]*(n+1)
visited[a] = 1
prev = [0]*(n+1)

while queue:
    
    u,c = queue.popleft()

    for v in graph[u]:
                    
        if visited[v] == 0:

            if v == b:

                visited[b] = c+1
                prev[b] = u
                break

            else:

                prev[v] = u
                visited[v] = c+1
                queue.append((v,c+1))

        else:

            if visited[v] > c+1:

                prev[v] = u
                visited[v] = c+1
                queue.append((v,c+1))

    if visited[b] != 0:
        
        break

 

 

그리고 visited를 이용해서 중복계산을 막도록 했는데

 

1 > 2 > 3 > 4로 가는거랑 1 > 5 > 4로 가는거는 다른경우기 때문에 단순히 visited[4] = 1로 표시하면 안될건데

 

가장 빨리 목적지로 이동해야하므로 visited에 이동한 거리 양을 표시해두고

 

동일한 지점에 더 빨리 이동하는 경우에만 갱신하도록 하자

 

-------------------------------------------------------------------------------------------------------

 

그리고 여기서 생각해야할 것은 b에 도착하기만 하면 끝이라는거

 

아무 경로나 하나 찾아서 출력하면 되는데 BFS를 이용해서 b에 먼저 도착하는 순간 그 경로가 가장 짧은 경로가 된다

 

그게 너무 당연한게 같은 깊이의 노드들을 처리하면서 전부 처리하면 깊이를 1씩 늘려가기 때문

 

BFS를 예를 들어 생각해보면 길이가 1인 (1,1)에서 시작해서

 

(2,2), (3,2), (4,2)가 들어오고 

 

(2,2)를 빼서, (3,2),(4,2), (5,3)이 들어오고

 

(3,2)를 빼서, (4,2),(5,3),(7,3),(9,3)가 들어오고

 

(4,2)를 빼서, (5,3),(7,3),(9,3),(6,3)이 들어오고

 

이런식으로 BFS가 동일한 깊이의 모든 노드를 처리한 다음 다음 깊이로 가니까 b에 먼저 도달하는 순간 그 경로가 최단경로

 

그래서 바로 break해도 돼

 

근데 for문 안에서만 break하고 while에서는 break안해버린 실수를

 

------------------------------------------------------------------------------------------------------------------------------

 

근데 생각해보니까 visited를 표시할 필요가 있나? 

 

prev만 표시해도 되는거 아닌가?

 

a,b = map(int,stdin.readline().split())
            
queue = deque([a])
prev = [0]*(n+1)
prev[a] = -1

while queue:
    
    u = queue.popleft()

    for v in graph[u]:
                    
        if prev[v] == 0:

            if v == b:

                prev[b] = u
                break

            else:

                prev[v] = u
                queue.append(v)
                
    if prev[b] != 0:
        
        break

 

 

근데 문제는 prev[v] == 0이면 방문하고 prev[v]가 0이 아니면 방문하지 않는 방식으로 했는데

 

이게 맞나?

 

prev[v] != 0이어도 방문해야하는 경우가 있을 수 있는거 아닌가?

 

b번에서 u번으로 이미 갔다면, a번에서 u번으로는 안가도 되는가?

 

이게 성립할려면 목적지가 u번을 지나가야하는 경로인데, b번을 지나서는 못가고, a번을 지나서는 갈 수 있는 경로라는거임

 

하지만 각 간선의 길이가 1이라면 b번을 지나 u번을 지나 가는 경로랑 a번을 지나 u번을 지나는 경로는 차이가 없다

 

u번에 오는 순간 u번을 지나야하는 경로는 a번으로 오든 b번으로 오든 반드시 갈 수 있기 때문이다

 

이게 차이가 있을려면 간선의 길이가 1이 아니어야한다  

 

 

최단경로 복원은 목적지 b번부터 시작해서 prev[b]를 다시 b라고 두고 반복적으로 찾아가다가

 

도달한 값이 b = a가 된다면 멈추고 이를 역순으로 출력하면 된다

 

많이 해봤지

 

당연히 prev[b] = 0이면 b로 도달하지 못했다는 뜻

 

if prev[b] == 0:
    
    print(-1)

else:
    
    A = [b]

    u = b

    while 1:
        
        v = prev[u]
        A.append(v)

        if v == a:
            
            break
        
        u = v
    
    for i in range(len(A)-1,-1,-1):
        
        print(A[i],end= ' ')

 

 

이렇게 하면 2.7초 정도 걸리더라고 

 

왜 오래걸리나 했더니 해밍거리를 구하는 과정이 O(N^2K)라서 그렇다

 

for a in range(1,n+1):

    for b in range(a,n+1):

        for c in range(len(A[a])):

            if A[a][c] != A[b][c]:

                dp[a][b] += 1
            
        dp[b][a] = dp[a][b]

 

 

근데 원하는건 해밍거리가 1인 경우 뿐이고 2 이상은 의미 없으므로,

 

해밍거리가 계산하다가 2 이상이 되면 바로 break하면 0.7초로 빨라진다

 

dp = [[0]*(n+1) for _ in range(n+1)]
graph = [[] for _ in range(n+1)]

for a in range(1,n+1):

    for b in range(a,n+1):

        for c in range(len(A[a])):

            if A[a][c] != A[b][c]:

                dp[a][b] += 1
                
                if dp[a][b] >= 2:
                    
                    break
            
        dp[b][a] = dp[a][b]

for a in range(1,n+1):
    
    for b in range(1,n+1):
        
        if dp[a][b] == 1:
            
            graph[a].append(b)
            graph[b].append(a)

 

 

다른 방법으로는 두 이진코드를 XOR하면 서로 다른 비트는 1이 되고, 서로 같은 비트는 0이 된다

 

따라서 두 이진코드를 XOR한 다음 1인 비트의 개수를 세면 된다

 

근데 그럴 필요가 있나 시간복잡도는 똑같이 O(N^2K)일텐데

 

아니면 조금이라도 더 빠르게 하고 싶으면?

 

https://deepdata.tistory.com/1454

Kernighan’s Algorithm

 

 

def bit_count(n):
    
    count = 0
    
    while n > 0:
    
        count += n & 1
        n >>= 1
    
    return count

n,k = map(int,stdin.readline().split())

A = [0]

for _ in range(n):

    s = stdin.readline().rstrip()
    A.append(s)

graph = [[] for _ in range(n+1)]

for a in range(1,n+1):

    for b in range(a+1,n+1):
        
        v = bit_count(int(A[a],2)^int(A[b],2))
        
        if v == 1:
            
            graph[a].append(b)
            graph[b].append(a)

 

 

 

혹은 창의적인 발상으로 O(NK)에 가능한데

 

해밍거리가 1인 이진 코드 쌍만 찾으면 된다는 점에 주목하자

 

즉, 어떤 이진코드 A가 주어지면 A와 해밍거리가 1인 이진코드만 찾으면 된다

 

A와 해밍거리가 1인 이진코드는 무엇인가?

 

A의 이진코드 중에서 1비트만 다른 코드를 말한다

 

그러면 A의 각 자리를 순회하여 각 자리의 비트를 뒤집은 다음 해당 코드가 실제로 존재하는지만 검사하면 된다

 

비트를 뒤집는건 어떻게 가능하지?

 

1과 0을 xor하면 1이고

 

1과 1을 xor하면 0이고

 

0과 0을 xor하면 0이고

 

0과 1을 xor하면 1이고

 

어떤 비트를 1과 xor하면 뒤집히고 0과 xor하면 그대로 나온다는 것에 주목하자

 

즉 주어진 A코드에서 i번째 비트만 서로 다른 코드 B코드는, i번째 비트를 1로 하고 나머지는 0으로 하는 1 << i와

 

XOR하면 i번째 비트는 뒤집히고(0 > 1, 1 > 0), 나머지 비트는 (0 > 0, 1 > 1) 그대로 보존된다

 

이렇게하면 O(NK)에 해밍거리가 1인 두 코드 쌍을 찾을 수 있어서 0.06초 만에 해결

 

n,k = map(int,stdin.readline().split())

A = {}

for i in range(1,n+1):

    s = stdin.readline().rstrip()
    s = int(s,2)
    A[s] = i

graph = [[] for _ in range(n+1)]

for bit_a in A:
    
    a = A[bit_a]
    
    for i in range(k):
        
        bit_b = bit_a ^ (1 << i)
        
        if A.get(bit_b,0) != 0:
            
            graph[a].append(A[bit_b])
            graph[A[bit_b]].append(a)