[파이썬] 백준 2479 : 경로찾기 (골드4)

[파이썬] 백준 2479 : 경로찾기 (골드4)

• https://www.acmicpc.net/problem/2479
  

---

풀이

방향성 생각

• binary로 들어오는 데이터들을 정수형으로 변환한다.

• key index <-> 정수 변환에 필요한 두 딕셔너리를 만든다.

  • 들어오는 bit 수가 1000개여서 전부 관리 가능하다.

• bit 연산을 통해서 입력 정수에 대해서 그래프를 만들어준다.

• BFS를 통해서 탐색하기

  • 단수 T/F 연산이 아니라 역추적이 필요하기 때문에 어디서 왔는지 기록

• 목적지에 도달했으면 역추적, 아니면 -1 출력

---

전체코드

from collections import deque ,defaultdict as dd

N,K = map(int,input().split())

# key index <-> bit
num_bin = {i:int(input(),2) for i in range(1,N+1)}
bin_num = {v:k for k,v in num_bin.items()}

start,end = map(int,input().split())

# G[x] = [nx1,...nxk] 연결노드
G = dd(lambda: [])
for a in num_bin.values():
    for k in range(K):
        na = a^(1<<k)
        if na in bin_num:
            G[a].append(na)

# V[x] = px 이전 방문노드 기록 (key index 대신, 숫자로 기록)
V = dd(lambda: -1)
V[num_bin[start]] = None
Q = deque([num_bin[start]])

# BFS
while Q:
    x = Q.popleft()
    for nx in G[x]:
        if V[nx] == -1:
            V[nx] = x
            Q.append(nx)

if V[num_bin[end]] == -1:
    print(-1)
else:

    # 역추적
    path = [num_bin[end]]
    while True:
        px = V[path[-1]]
        path.append(px)
        if V[px] == None:
            break

    # 도착지에서부터 기록한 숫자 정보 역순 + key index로 변환
    answer = [bin_num[a] for a in reversed(path)]
    print(*answer)

코멘트

• 입력이 좀 더 큰 백준2481 문제가 있다.

• 비트연산 역추적만 할줄알면 어렵지 않은 문제