[파이썬] 백준 2481 : 해밍 경로 (골드2)

[파이썬] 백준 2481 : 해밍 경로 (골드2)

2481번: 해밍 경로

---

문제

---

풀이

0. 방향성 생각

입력 개수가 최대 10^6, 해밍거리가 1인 노드끼리만 연결해주면 된다.

노드가 최대 10^6인거부터 2개씩 짝지어서 하는 방법은 불가능. 최대 5 * 10^11이므로 불가능하다.

 

코드<->인덱스 매칭을 통해서 딕셔너리를 사용한다는 점까지는 생각할 수 있다.

그 이후에는 

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,length = map(int,input().split())

index,codes = {},{}
for idx in range(1,n+1):
    code = int(input(),2)
    index[code] = idx
    codes[idx] = code

index[code] = idx, codes[idx] = code 이런 방식으로 서로 변환, 역변환 할 수 있게 딕셔너리 작성한다.

 

2. 그래프 정의

graph = {i: set() for i in range(1,n+1)}
for code in index:
    for shift in range(length):
        ncode = code^1 << shift
        if ncode in index:
            graph[index[ncode]].add(index[code])
            graph[index[code]].add(index[ncode])

그래프를 정의한다.

index, codes가 딕셔너리로 정의되어있기 때문에 O(n) = 1이다.

최대 30자리를 비트 시프트해도 입력 10^6개면 300000에 모두 연결시킬 수 있다.

1자리씩 토글시켜주면서 index에 들어있는지 확인한다. index 키는 code이다.

 

3. 그래프 탐색

visit = {i: -1 for i in range(1,n+1)}
visit[1] = 0

q = deque([1])
while q:
    x = q.popleft()
    if graph[x]:
        for nx in graph[x]:
            if visit[nx] == -1:
                visit[nx] = x
                q.append(nx)

모든 노드를 -1로 초기화한다.

방문한 노드에 새로 연결된 노드가 존재하고, 첫 방문인 경우 현재 위치를 visit에 넣고 큐에 추가한다.

 

4. 경로 추적

def trace(target):
    global visit
    if visit[target] == -1:
        return -1
    else:
        ans = [target]
        while True:
            if visit[target] == 0:
                return ans[::-1]
            target = visit[target]
            ans.append(target)

종착점에서 경로를 거슬러 올라간다.

종착점에 도달하지 못하는 경우는 -1 리턴

5. 출력

for _ in range(int(input())):
    answer = trace(int(input()))
    if answer == -1:
        print(-1)
    else:
        print(*answer)

언패킹 통해서 출력

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,length = map(int,input().split())

index,codes = {},{} # index[code] = idx, codes[idx] = code
for idx in range(1,n+1):
    code = int(input(),2)
    index[code] = idx
    codes[idx] = code

graph = {i: set() for i in range(1,n+1)}
for code in index:
    for shift in range(length):
        ncode = code^1 << shift
        if ncode in index:
            graph[index[ncode]].add(index[code])
            graph[index[code]].add(index[ncode])

visit = {i: -1 for i in range(1,n+1)}
visit[1] = 0

q = deque([1])
while q:
    x = q.popleft()
    if graph[x]:
        for nx in graph[x]:
            if visit[nx] == -1:
                visit[nx] = x
                q.append(nx)

def trace(target):
    global visit
    if visit[target] == -1:
        return -1
    else:
        ans = [target]
        while True:
            if visit[target] == 0:
                return ans[::-1]
            target = visit[target]
            ans.append(target)

for _ in range(int(input())):
    answer = trace(int(input()))
    if answer == -1:
        print(-1)
    else:
        print(*answer)

코멘트

비트연산이 익숙하지가 않아서 떠올리는거 부터 실패..