[알고리즘] BFS를 이용하여 최단거리를 출력해야할때 with predecesso(프로시져)

# 발단

9019번: DSLR

 BFS문제는 간선에 가중치가 없는 경우 그래프적으로 해석하면 최단거리를 구할 수 있다. 왜냐하면 노드의 방문을 큐로 관리하기 때문에 넓이우선탐색을 하고 이 넓이는 하나의 turn이 될 수 있다. 그 turn에서 목표지점을 발견했다면 그것이 최단거리이다.

 몇몇 BFS문제를 풀었을때, 이러한 최단거리까지 총 몇번의 거쳐서 가는가를 구하는 응용 문제들( ex. 며칠이 걸리나? like 토마토 )은 프로시져를 활용하여 풀었다. 즉 큐에 방문할 당시의 단계+1을 해주고 도착점에서 그 값을 구하도록 했다.

# 토마토 문제
mNext = (next[0],next[1],next[2], cur[3]+1) # 마지막 인자는 현재까지의 방문일에 +1 을 해준다

 

## DSLR에서는?

 근데 DSLR에서는 거쳐온 경로를 구해야했다, 즉 LLDDD와 같은 값을 구해야 했다. 토마토의 방식과 똑같이 하면 됐지만, 그렇게 풀 생각을 안하고 아래와 같이 이전의 위치를 기억하게 하는 dict을 만들고 재귀적으로 뒤에서부터 앞으로 돌아가게 만들었다.

ddict = defaultdict(list)

def backward(ddict,cur,start) :
  while True :
    if ddict[cur][0] == start :
      print(ddict[cur][1], end="")
      break
    print(ddict[cur][1],end="")
    cur = ddict[cur][0]

일단 이 풀이는 틀렸다.

• 앞에서부터 뒤의 출력결과가 나와야하는데, 뒤에서부터 앞의 출력결과를 구해버렸다. ( 이건 코드를 바꾸면 되긴 하지만..)
• 프로시져를 활용하면 쓰지 않아도 되는 메모리를 낭비하게 된다
• 시간도 낭비한다

 

# 결론

def solve() :
  cur, target = map(int, sys.stdin.readline().strip().split())
  dq = deque()
  dq.append((cur,""))
  commands = ["D","S","L","R"]
  visit = [False for i in range(10_000)]

  while cur != target :
    cur = dq.popleft()
    for command in commands :
      next = DSLR(command, cur[0])
      if not visit[next] :
        dq.append((next,cur[1]+command)) # <---- 이렇게 활용
        visit[next] = True
        if next == target:
          print(cur[1]+command)
          return

여튼 이것도 프로시져방식을 이용하여 그냥 string을 하나씩 더해주면 된다. 괜히 헛고생했다.