2479번 - 경로 찾기
from collections import deque
n,k = map(int,input().split())
d = [0]
ans = []
maxx = 0
def compare(a,b):
temp = 0
for i in range(k):
if a[i] != b[i]:
temp+=1
return temp
dd = [[]for i in range(n+1)]
for i in range(n):
a = list(input())
d.append(a)
for i in range(1,n+1):
for j in range(i+1,n+1):
if compare(d[i],d[j]) == 1:
dd[i].append(j)
dd[j].append(i)
m,mm = map(int,input().split())
v = deque([m])
vv = [[-1] for i in range(n+1)]
vv[m] = [m]
while len(v) != 0:
temp = v.popleft()
if temp == mm:
print(*vv[temp])
break
for i in dd[temp]:
if vv[i][0] == -1 or (len(vv[temp])+1 < len(vv[i])):
v.append(i)
vv[i] = vv[temp]+[i]
else:
print(-1)
댓글을 작성하려면 로그인해야 합니다.
shkang1115 10달 전
from collections import deque
n,k = map(int,input().split())
d = [0]
ans = []
maxx = 0
def compare(a,b):
temp = 0
for i in range(k):
if a[i] != b[i]:
temp+=1
return temp
dd = [[]for i in range(n+1)]
for i in range(n):
a = list(input())
d.append(a)
for i in range(1,n+1):
for j in range(i+1,n+1):
if compare(d[i],d[j]) == 1:
dd[i].append(j)
dd[j].append(i)
m,mm = map(int,input().split())
v = deque([m])
vv = [[-1] for i in range(n+1)]
vv[m] = [m]
while len(v) != 0:
temp = v.popleft()
if temp == mm:
print(*vv[temp])
break
for i in dd[temp]:
if vv[i][0] == -1 or (len(vv[temp])+1 < len(vv[i])):
v.append(i)
vv[i] = vv[temp]+[i]
else:
print(-1)