SWEA 1219. 길찾기(Python)(D4)

Wjong·2023년 1월 30일
0

swea

목록 보기
14/36
post-thumbnail


데이터 저장 가이드라인이 있는 아주 친절한(?) 문제이다.
하지만 친절은 해로우므로, 별도로 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]))
profile
뉴비

0개의 댓글