데이터 저장 가이드라인이 있는 아주 친절한(?) 문제이다.
하지만 친절은 해로우므로, 별도로 graph 구성을 했다.
graph[i]=[이동할 수 있는 노드번호들] 로 구성했다.
0번부터 출발하여, graph[0]의 노드번호들을 백트래킹으로 탐험한다.
ex)
- 위의 예시에서, 0번(출발지점)과 연결된 노드들 -> 1,2
- graph[0]에서 노드1을 제거하고 1번으로 이동(재귀)
- 재귀 밖에선, 노드1을 다시 넣어주고 노드2를 제거하고 이동(재귀)
- 반복하다가, 99번노드(도착지점)에 도달할 경우, global값 tmp을 1로 바꿔줌
- 결과리턴!
(BFS를 써도 될 문제긴 하나, 백트래킹으로 충분히 마무리 될 문제라 생각)
res=[]
def go(x):
global tmp
if x==99:
tmp=1
return
for i in range(len(graph[x])):
tmp_val=graph[x].pop(i)
go(tmp_val)
graph[x].insert(i,tmp_val)
for m in range(10):
tmp=0
_,N=map(int,input().split())
graph=[[] for i in range(N+1)]
road=list(map(int,input().split()))
for i in range(0,len(road),2):
graph[road[i]].append(road[i+1])
go(0)
res.append(tmp)
for i in range(len(res)):
print("#%d %s"%(i+1,res[i]))
뉴비