출처 : SW Expert Academy
문제
주어진 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 프로그램을 만드시오.
노드 번호는 1번부터 존재하며, 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.
[입력]
첫 줄에 테스트 케이스 개수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 첫 줄에 V와 E가 주어진다. 5<=V=50, 4<=E<=1000
테스트케이스의 둘째 줄부터 E개의 줄에 걸쳐, 간선의 양쪽 노드 번호가 주어진다.
E개의 줄 이후에는 출발 노드 S와 도착 노드 G가 주어진다.
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
두 노드 S와 G가 서로 연결되어 있지 않다면, 0을 출력한다
코드
import sys
sys.stdin = open('input.txt')
# 주어진 출발 노드에서
# 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 프로그램
T = int(input())
def bfs(S, G):
queue = [S]
visited[S] = 1
while len(queue):
front = queue.pop(0)
if front == G:
print("#{} {}".format(tc, result[front]))
return
# 이어진 노드들 찾기
for j in range(V + 1):
if graph[front][j] == 1 and visited[j] == 0:
queue.append(j)
# 간선 저장
result[j] = result[front] + 1
visited[j] = 1
if result[G]:
print("#{} {}".format(tc, result[G]))
else:
print("#{} 0".format(tc))
for tc in range(1, T+1):
# V개의 노드 개수와 방향성이 없는 E개의 간선 정보
V, E = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(E)]
# 출발 노드 S와 도착 노드 G
S, G = list(map(int, input().split()))
# 간선 그래프 그리기
graph = [[0 for _ in range(V+1)] for _ in range(V+1)]
for i in range(E):
start = data[i][0]
end = data[i][1]
graph[start][end] = 1
graph[end][start] = 1
visited = [0 for _ in range(V+1)]
result = [0 for _ in range(V+1)]
bfs(S, G)
장애물
문제1.
def bfs(S, G):
queue = [S]
while len(queue):
front = queue.pop(0)
### 여기가 문제점!! ###
if not visited[front]:
visited[front] = 1
# 이어진 노드들 찾기
for j in range(V+1):
if graph[front][j] == 1 and visited[j] == 0:
queue.append(j)
# 간선 저장
result[j] = result[front] + 1
즉 경로가 5인것과 3인것이 있으면 3인걸 출력하게끔 만들어야함.
해결법
간선을 저장하고 바로 그 간선을 지나는 노드를 저장해야한다.
result[j] = result[front] + 1 # 간선 저장
visited[j] = 1 # 노드 방문 저장
배운점
BFS는 같은 레벨인 경우들을 탐색하고 다음으로 넘어간다.
그래서 이 문제의 경우 무조건 최소의 레벨을 출력할 수 있다.
2021.06 ~