[BOJ][🟡3][백준#02479] 경로 찾기

문제 출처

BAEKJOON Online Judge #2479

문제

길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다. 우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다. 예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다.

A=000 B=111 C=010 D=110 E=001

두 코드 A와 B사이의 해밍 거리를 H(A,B)로 표현한다. 그러면, H(A,B)=3, H(A,C)=1, H(A,D)=2, H(A,E)=1 이다. 우리는 이진 코드들에 대해 해밍 경로를 찾고자 한다. 해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다. 위의 예에서 (A,C,D)는 코드 A와 C의 해밍 거리가 1이고, 코드 C와 D의 해밍 거리가 1이므로 해밍 경로이다. (A,E,B)는 코드 A와 E의 해밍 거리는 1이지만, 코드 E와 B의 해밍 거리가 2이므로 해밍 경로가 아니다. 이 문제는 주어진 두 코드 사이에 가장 짧은 해밍 경로를 구하는 프로그램을 작성하는 것이다.

입력

첫째 줄에는 두 개의 정수 N과 K가 빈칸을 사이에 두고 주어진다(3 ≤ N ≤ 1,000, 2 ≤ K ≤ 30). 둘째 줄부터 N개의 줄에는 각 줄마다 길이가 K인 이진 코드가 하나씩 주어진다. 하나의 코드는 빈칸이 없이 주어진다. 코드들은 주어진 순서대로 1부터 N까지의 번호로 구분된다. 코드가 같은 경우는 없다. 그 다음 줄에는 해밍 경로를 찾고자 하는 서로 다른 두 개의 코드 A와 B가 각각의 코드번호로 주어진다.

출력

입력으로 주어진 두 코드 사이에 해밍 경로가 존재하면 그 경로 중 가장 짧은 경로를 코드 A부터 코드 B까지 경로상의 코드 번호로 출력한다. 코드 번호를 출력할 경우에는 코드 번호 사이에 하나의 빈칸을 사이에 두고 출력한다. 만약 답이 여러 개 있으면 그 중에 하나만 출력하고, 경로가 존재하지 않으면 -1을 출력한다.

예제

입력

5 3
000
111
010
110
001
1 2

출력

1 3 4 2

My Sol

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

T, L = map(int, input().split())
arr = []
for _ in range(T):
    arr.append(int(input()[::-1], 2))

mat = []
for i in range(T):
    num = 0
    for j in range(T):
        cnt = 0
        for k in range(L):
            if (arr[i]^arr[j]) & (1<<k):
                cnt += 1
                if cnt==2:
                    cnt = 0
                    break
        num += (1<<j)*cnt
    mat.append(num)

for i in range(L):
    mat[i] &= ~(1<<i)

S, E = map(int, input().split())
S, E = S-1, E-1

paths = deque()
paths.append([S])
Q = deque()
Q.append(S)
v = 0
while not v & (1<<E) and Q:
    s = Q.popleft()
    path = paths.popleft()
    for i in range(T):
        if v&(1<<i): continue
        if not mat[s]&(1<<i): continue
        v ^= (1<<i)
        if i==E:
            path += [i]
            for n in path:
                print(n+1, end=' ')
            quit()
        Q.append(i)
        paths.append(path+[i])
print(-1)

시간과 용량을 극적으로 줄이기 위해 visited, mat 2차원 배열 등 체크용으로 사용하는 가용한 모든 것을 비트형식으로 작성하였다.

최초 1과0으로 이루어진 입력 텍스트를 반전하여 int(,2)를 이용해 2진수를 10진수로 변환해 저장하고, 이 각각을 인덱스에 맞춰 서로 연결되어 있는지 비트를 통해 체크하였다.

자기 스스로와는 링크될 수 없으므로 mat[i] &= ~(1<<i)를 index마다 작성하여 0으로 만들어주었다.

Q를 이용해 앞에서 시작점을 뽑아내고, 이후 시작점과 연결된 점들을 하나하나 확인해 방문하지 않았다면 방문 체크를 한다.

최단 경로를 구해야하므로 BFS를 사용하면 좋을 것 같은데, 경로를 어떻게 체크해야할까 하다가 Q와 같이 동작하는 paths 배열을 만들어 popleft하여 시작점의 도착점을 담아 append 하는 방식으로 Q와 순서를 맞춰주었다. 때문에 Q에서 꺼낸 시작점과 연결된 점이 도착점이 있다면, 함께 꺼내온 path에 도착점까지 넣어서 출력해주면 되겠다.

경로는 인덱스 때문에 출력해야 하는 형식보다 1씩 작으므로 for문을 이용해 1씩 키워서 출력해주었다. 만약 Q가 동날 때까지 출력하지 못하면, -1을 출력하고 마친다.

결과

맞았습니다!!

모범답안

출처

# 2479 경로찾기
from sys import stdin
import sys
from collections import defaultdict
def dfs(now, road):
    if now == e:
        print(*road)
        sys.exit()
    
    for i in range(k):
        temp = list(ham[now])
        temp[i] = str(abs(1- int(temp[i])))
        temp = ''.join(temp)
        if temp in ham and ham[temp][0] == 0:
            ham[temp][0] = 1
            dfs(ham[temp][1], road + [ham[temp][1]])
            ham[temp][0] = 0

n, k = map(int, stdin.readline().split())
ham = defaultdict(list)
for i in range(n):
    ham[i+1] = ''.join(list(stdin.readline().rstrip()))
    ham[ham[i+1]] = [0, i+1]
s, e = map(int, stdin.readline().split())
dfs(s, [s])
print(-1)

코드길이가 짧아서 가져온 풀이이다. 나는 BFS를 이용했는데, 이 분은 DFS를 이용해 푸셨다. defaultdict라는 모듈을 import해 사용하셨다. 딕셔너리의 한 종류인 것 같다. 경로 설정은 인자로 넣어서 매번 전달해주었는데도 속도가 빨랐다. visited 체크를 딕셔너리로 특이하게 하셨다.