[BOJ/백준] 2479 경로 찾기 파이썬

문제 링크 : https://www.acmicpc.net/problem/2479

2479번: 경로 찾기

 

BFS로 풀이 하였다.

 

그냥 모든 경우 다 따져도 될 것 같다.

BFS 돌면서 현재 점과 방문하지 않은 점들중 해밍 거리가 1인 것만 골라서 BFS를 진행해도 무방할 듯 하다.

30 * 1000 * 1000 = 30,000,000 이므로 다 따져도 충분하다.

 

그치만 나는 그냥 미리 해밍 거리가 1인걸 구하고 그 녀석들 가지고만 BFS를 수행했다.

그리고 가장 중요한것은 경로를 저장하는 것이다.

 

나는 visited 배열을 방문체크와 경로 저장에 사용 했다.

그래서 visited배열에는 해당 점으로 오기전 점의 번호를 저장한다.

 

예제 1번으로 따지면

[1, 4, 1, 3, 1] 이 된다.

이때 출발지가 1, 도착지가 2이므로 2부터 거꾸로 거슬러 가면 2 - 4 - 3 - 1이 된다.

이것을 역으로 출력하면 된다.

 

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

n,k = map(int, input().split())
bits = [input().strip() for _ in range(n)]
sn,en = map(lambda x:int(x)-1, input().split())

def solv():
    visited = [-1]*n
    candidate = set_candidate()

    q = deque([(sn,0)])
    visited[sn] = sn

    while q:
        now,cnt = q.pop()
        if now == en:
            print_answer(visited)
            return

        for nxt in candidate[now]:
            if visited[nxt] == -1:
                visited[nxt] = now
                q.appendleft((nxt,cnt))
    print(-1)
def print_answer(visited):
    path = [en+1]
    nxt = visited[en]
    while visited[nxt] != nxt:
        path.append(nxt+1)
        nxt = visited[nxt]

    path.append(sn+1)
    path.reverse()
    print(*path)
def set_candidate():
    candidate = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            flag = False
            for a,b in zip(bits[i],bits[j]):
                if a != b:
                    if flag:
                        break
                    flag = True
            else:
                candidate[i].append(j)
                candidate[j].append(i)
    return candidate

solv()