출처 : https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
1. 문제 설명
V개의 노드 개수와 방향성이 없는 E개의 간선 정보가 주어진다.
주어진 출발 노드에서 최소 몇 개의 간선을 지나면 도착 노드에 갈 수 있는지 알아내는 프로그램을 만드시오.
예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경우, 두 개의 간선을 지나면 되므로 2를 출력한다.
노드 번호는 1번부터 존재하며, 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.
[입력]
첫 줄에 테스트 케이스 개수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 첫 줄에 V와 E가 주어진다. 5<=V=50, 4<=E<=1000
테스트케이스의 둘째 줄부터 E개의 줄에 걸쳐, 간선의 양쪽 노드 번호가 주어진다.
E개의 줄 이후에는 출발 노드 S와 도착 노드 G가 주어진다.
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
두 노드 S와 G가 서로 연결되어 있지 않다면, 0을 출력한다.
2. 코드
큐를 이용하여 풀 수 있는 문제였습니다. 재귀를 이용하여 bfs를 몇번 실행해야 출발 노드에서 도착 노드까지 갈 수 있을 지 코드를 작성하였습니다. 간선이 양방향이기 때문에 2차원 배열을 만들어 활용하였습니다.
아래가 작성한 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
# bfs를 실행할 함수
def bfs(q, cnt, end):
global result
next_q = []
# 현재 큐에 원소가 없을 때까지 진행
while len(q):
node = q.pop(0)
# 끝점에 도달한 경우 종료
if node == end:
result = cnt
return
# 현재 노드에서 방문을 안한 노드 중 갈 수 있는 노드를 다음 큐에 추가
for n in range(1, V+1):
if visited[n] == 0 and pos[node][n] == 1:
visited[n] = 1
next_q.append(n)
# 다음에 실행할 큐에 원소가 없을 경우 종료
if len(next_q) == 0:
return
# 원소가 있으면 bfs 다시 실행
else:
bfs(next_q, cnt+1, end)
T = int(input())
for tc in range(1, T+1):
V, E = map(int, input().split())
# 간선 정보를 저장할 이차원 배열
pos = [[0 for _ in range(V+1)] for _ in range(V+1)]
for _ in range(E):
x, y = map(int, input().split())
pos[y][x] = 1
pos[x][y] = 1
start_n, end_n = map(int, input().split())
# 노드 방문 기록을 저장할 배열
visited = [0]*(V+1)
result = 0
# 초기값 정보 정리
q = [start_n]
visited[start_n] = 1
bfs(q, 0, end_n)
print('#{} {}'.format(tc, result))
|