컴퓨터 알고리즘 12주차

시험은 그래프를 주고 시작 노드 줘서 출력값 구해라

 

문제 1

•  (DFS) 입력으로 주어지는 그래프의 DFS 탐색 결과를 출력하는 프로그램을 작성하시오.
• 입력 그래프의 성질
  • n (1 ≤ n ≤ 100) 개의 정점과 m (1 ≤ m ≤ 1,000) 개의 간선으로 구성
  • 정점은 1 ~ n 사이의 정수로 번호가 매겨져 있고, 정점의 번호는 모두 다름
  • 모든 간선은 무방향 간선이고, 한 정점에서 임의의 다른 정점으로 가는 경로는 반드시 존재
• 구현 조건
  • 그래프는 인접리스트 구조를 사용하여 표현해야 한다.
• 인접 정점의 조사 순서
  • 정점 u의 인접 정점(or 부착 간선)들을 번호가 작은 정점부터 조사한다.
  • (인접 정점들을 번호가 작은 정점부터 큰 순서대로 조사하라. 조사 순서에 따라 방문 결과가 달라질 수 있음에 유의할 것)
• 입출력:
  • 입력 - 첫 줄에 정점의 개수 n, 간선의 개수 m, 탐색 시작 정점 번호 s가 주어진다.
  • 이후 m개의 줄에 한 줄에 하나씩 간선의 정보(간선의 양 끝 정점 번호)가 주어진다.
  • 간선은 임의의 순서로 입력되고, 중복 입력되는 간선은 없다.
  • (무방향 간선이므로 간선 (u, v)와 (v, u)는 동일한 간선으로 취급)
• 출력
  • 출발정점 s에서 출발하는 DFS의 방문 순서대로 정점 번호를 출력한다.

DFS

# 1 <= n <= 100
# 1 <= m <= 1000


n,m,s = map(int,input().split())

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

for _ in range(n+1):
    adj_list[_] = list(sorted(set(adj_list[_])))
    #print(adj_list[_])


visited = [False] * (n+1)

def dfs(v):
    visited[v] = True
    print(v)
    for w in adj_list[v]:
        if not visited[w]:
            dfs(w)
dfs(s)

문제 2

•  (BFS) 입력으로 주어지는 그래프의 DFS 탐색 결과를 출력하는 프로그램을 작성하시오.
• 입력 그래프의 성질
  • n (1 ≤ n ≤ 100) 개의 정점과 m (1 ≤ m ≤ 1,000) 개의 간선으로 구성
  • 정점은 1 ~ n 사이의 정수로 번호가 매겨져 있고, 정점의 번호는 모두 다름
  • 모든 간선은 무방향 간선이고, 한 정점에서 임의의 다른 정점으로 가는 경로는 반드시 존재
• 구현 조건
  • 그래프는 인접행렬 구조를 사용하여 표현해야 한다.
• 인접 정점의 조사 순서
  • 정점 u의 인접 정점(or 부착 간선)들을 번호가 작은 정점부터 조사한다.
  • (인접 정점들을 번호가 작은 정점부터 큰 순서대로 조사하라. 조사 순서에 따라 방문 결과가 달라질 수 있음에 유의할 것)
• 입출력:
  • 입력 - 첫 줄에 정점의 개수 n, 간선의 개수 m, 탐색 시작 정점 번호 s가 주어진다.
  • 이후 m개의 줄에 한 줄에 하나씩 간선의 정보(간선의 양 끝 정점 번호)가 주어진다.
  • 간선은 임의의 순서로 입력되고, 중복 입력되는 간선은 없다.
  • (무방향 간선이므로 간선 (u, v)와 (v, u)는 동일한 간선으로 취급)
• 출력
  • 출발정점 s에서 출발하는 BFS의 방문 순서대로 정점 번호를 출력한다.

BFS

# 1 <= n <= 100
# 1 <= m <= 1000


n,m,s = map(int,input().split())

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

for _ in range(n+1):
    adj_list[_] = list(sorted(set(adj_list[_])))
    #print(adj_list[_])


visited = [False] * (n+1)