0521_백준 2644번 : 촌수계산 & 11724번 : 연결 요소의 개수/ BFS와 DFS 연습/ Python

오늘 라이브 강의에서는 그래프 유형의 알고리즘에 대해서 배웠다. 그래프를 표현하는 방법으로 인접행렬, 인접리스트를 학습하고 나아가 그래프를 탐색하는 방법인 DFS(깊이우선탐색)과 BFS(너비우선탐색)을 연습했다. 수업이 끝나고 이와 관련된 백준 문제를 정리해봤다👇 난이도는 높지 않지만 11724번 연결 요소의 개수는 python으로 제출하면 시간초과가 나서 pypy로 통과했다😂

 

 

---

"BFS(너비우선탐색) 유형"

 

[문제 출처]

백준 2644번 촌수계산 https://www.acmicpc.net/problem/2644

2644번: 촌수계산

[코드 구현]

import sys
from collections import deque

def bfs(v):
    q = deque()
    q.append(v)
    visit[v] = 1
    while q:
        tmp = q.popleft()
        for i in adj[tmp]:
            if visit[i] == 0:
                q.append(i)
                visit[i] = visit[tmp] + 1

input = sys.stdin.readline
n = int(input())
t_s,t_b = map(int, input().split())
m = int(input())
adj = [[] for _ in range(n+1)]
visit = [0]*(n+1)
for i in range(m):
    p, c = map(int, input().split())
    adj[p].append(c)
    adj[c].append(p)
bfs(t_s)

print(visit[t_b]-1 if visit[t_b] else -1)

 

---

 

[문제 출처]

백준 11724번 연결 요소의 개수 https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

[코드 구현]

def connect(v):
    global cnt
    stack = [v]
    visit[v] = 1
    while stack:
        tmp = stack.pop()
        for i in adj[tmp]:
            if visit[i] == 0:
                stack.append(i)
                visit[i] = 1
    if visit.count(1) != n:
        for k in range(1, len(visit)):
            if visit[k] == 0:
                cnt += 1
                connect(k)
    return

n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
visit = [0]*(n+1)
cnt = 1
for i in range(m):
    s, e = map(int, input().split())
    adj[s].append(e)
    adj[e].append(s)
connect(1)
print(cnt)