Algorithm/Baekjoon

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

rmsidgkrl 2020. 5. 21. 23:39
728x90
반응형

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

 

 

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

 

[문제 출처]

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

 

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진�

www.acmicpc.net

[코드 구현]

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번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주��

www.acmicpc.net

[코드 구현]

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)
반응형