[백준] 22868번 파이썬 - BFS, 경로 저장

문제요약 ( 22868. 산책 (small) )

 

22868번: 산책 (small)

 

 

풀이를 위한 부연 설명

• 최단 경로를 확인해야하므로 BFS를 사용해야한다.
  • 인접 행렬을 이용해 그래프 형태로 바꾼다
• S에서 E로 갔다가, 경로가 겹치지 않게 E에서 S로 돌아와야한다.
  
  • 구글링 해보니 이 방법이 여러가지가 있다.
    1. BFS 함수를 따로 구현
    2. 매개변수로 S_TO_E인지 E_TO_S인지 구분
  • 필자는 구글링해서 나오지 않던(아마...),
    1. 문자열로 지나왔던 경로를 저장하고 새로운 visited 배열을 넘기도록 했다.

 

• DFS에 대한 개념과 연관 문제는 다음 게시글을 참고하면 된다.

[코테 알고리즘] DFS, BFS / 관련 문제

 

코드 

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

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, n+1):
    graph[i].sort()

s, e = map(int, input().split())


def bfs(start, end, visited):
    que = deque()
    que.append((start, 0, str(start)))
    visited[start] = True

    while que:
        now, distance, going = que.popleft()
        if now == end:
            return distance, going
        for new in graph[now]:
            if not visited[new]:
                que.append((new, distance+1, going + " " + str(new)))
                visited[new] = True


visited = [False] * (n+1)
first, go = bfs(s, e, visited)

visited = [False] * (n+1)
for i in list(map(int, go.split())):
    visited[i] = True
visited[s] = False
visited[e] = False

print(first + bfs(e, s, visited)[0])

 

 

주석 있는 ver. (상세 설명)

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

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 문제에서 오름차순으로 경로 출력해야한다고 했으므로 소팅 필수
for i in range(1, n+1):
    graph[i].sort()

s, e = map(int, input().split())


def bfs(start, end, visited):
    que = deque()
    que.append((start, 0, str(start)))
    visited[start] = True

    while que:
        now, distance, going = que.popleft()
        if now == end:
            # 도착점에 도착했다면, 거리와 경로 반환
            return distance, going
        for new in graph[now]:
            if not visited[new]:
                # going + " " + str(new)으로 
                # 해당하는 경로를 방문하는 것을 확인
                que.append((new, distance+1, going + " " + str(new)))
                visited[new] = True


visited = [False] * (n+1)
first, go = bfs(s, e, visited)

# 방문했던 경로들만 진짜 방문한 것으로 처리
visited = [False] * (n+1)
for i in list(map(int, go.split())):
    visited[i] = True
# 시작점과 끝점은 BFS를 해야하므로 따로 미방문으로 처리
visited[s] = False
visited[e] = False

print(first + bfs(e, s, visited)[0])

 

 

 

기억할 점

• 오름차순으로 출력해야한다고 했으므로 인접 행렬 정렬이 필수적이다.
• 트래킹 순서에 유의한다.
  • 큐에 값을 넣을 때 방문하는 going을 업데이트 해야한다.

    while que:
        now, distance, going = que.popleft()
        if now == end:
            # 도착점에 도착했다면, 거리와 경로 반환
            return distance, going
        for new in graph[now]:
            if not visited[new]:
                # going + " " + str(new)으로
                # 해당하는 경로를 방문하는 것을 확인
                que.append((new, distance+1, going + " " + str(new)))
                visited[new] = True

 

(feat. 백준 고수님 siyamaki님)