백준 algorithm 1260 11724 2606 python dfs bfs 연결요소

파이썬 알고리즘 : DFS와 BFS, 연결 요소의 개수, 바이러스

백준 1260, 백준 11724, 백준 2606

2023년 8월 4일 알고리즘 문제풀이

백준 1260

문제 링크

1차 시도

나의 생각

오랜만에 dfs, bfs라 당황했다. 우선 2차원 배열로 그래프를 그린 후 두 정점 사이의 간선이 있으면 1, 없으면 0으로 표현했다. 그리고 방문한 정점을 표시하기 위한 배열도 만들었다. dfs는 이동할 수 있는 다음 정점으로 재귀를 통해 확인하는 과정을 거쳤다. bfs는 현재 정점에서 이동할 수 있는 정점 모두를 deque에 담은 후 popleft하면서 각각마다 그 다음 목적지를 확인하였다. bfs를 큐로 관리하는 것이 기억해내느라 푸는데 시간이 촉박했다.

결과

정답

코드

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

import sys
from collections import deque
n, m, v = map(int, sys.stdin.readline().split())
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a][b] = 1
    graph[b][a] = 1

visited_dfs = [False for _ in range(n+1)]
visited_bfs = [False for _ in range(n+1)]

def dfs(x, arr, ans):
    arr[x] = True
    ans.append(x)
    for i in range(1, n+1):
        if not arr[i] and graph[x][i]:
            dfs(i, arr, ans)

def bfs(x, arr, ans):
    arr[x] = True
    options = deque()
    options.append(x)
    while options:
        now = options.popleft()
        ans.append(now)
        for i in range(1, n+1):
            if not arr[i] and graph[now][i]:
                options.append(i)
                arr[i] = True

ans_dfs = []
ans_bfs = []
dfs(v, visited_dfs, ans_dfs)
bfs(v, visited_bfs, ans_bfs)
print(*ans_dfs, sep=' ')
print(*ans_bfs, sep=' ')

백준 11724

문제 링크

1차 시도

나의 생각

연결 요소(Connected Component)는 간선을 통해 이동 가능한 정점들의 집합이다. 한 연결 요소 내의 정점들간에는 이어져있다.

처음에는 각 정점에서 모든 점을 순회하며 아직 방문한 적이 없고, 이동 가능한 점이 있다면 그곳으로 이동하고 방문 표시를 하도록 구현했다. 그 후 이를 반복하다가 더이상 방문 가능한 곳이 없을때, 모든 도시에 방문했다면 더이상 연결요소가 없으므로 그대로 결과를 출력하고, 아직 방문처리가 안된곳을 탐색하여 있다면 거기서 다시 시작하도록 하였다. 우선 결과는 오답이 떴다.

문득 DFS랑 비슷하다는 생각이 들었다. 그래서 생각해보니 BFS로 방문할 수 있는 모든곳을 방문처리하면 연결 요소 를 셀 수 있겠다는 생각이 들어 BFS로 풀었고 바로 맞출 수 있었다!

결과

정답

코드

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

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int, sys.stdin.readline().split())
    graph[u][v] = graph[v][u] = 1

visited = [False for _ in range(n+1)]
visited[0] = True

def bfs(k,cnt):
    visited[k] = True
    arr = deque()
    arr.append(k)
    while arr:
        now = arr.popleft()
        for i in range(1,n+1):
            if graph[now][i] == 1 and not visited[i]:
                arr.append(i)
                visited[i] = True
        if False not in visited:
            break
    cnt += 1
    return cnt

ans = 0
for i in range(1,n+1):
    if not visited[i]:
        ans += bfs(i,0)
print(ans)

백준 2606

문제 링크

1차 시도

나의 생각

위의 11724와 똑같은 문제라고 생각했다. 1과 같은 연결 요소내의 있는 정점의 갯수를 구하면 된다. 하지만 문제에서는 1로 인해 감염된 컴퓨터의 수라고 했으니 1이 포함된 연결 요소의 정점 갯수에서 1개를 빼면 된다. 1은 1이 감염시킨 컴퓨터가 아니니까..

결과

정답

코드

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

import sys
from collections import deque

n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(k):
    a,b = map(int,sys.stdin.readline().split())
    graph[a][b] = graph[b][a] = 1
visited = [ False for _ in range(n+1)]

def bfs(x):
    visited[x] = True
    arr = deque()
    arr.append(x)
    while arr:
        now = arr.popleft()
        for i in range(1,n+1):
            if not visited[i] and graph[now][i] == 1:
                arr.append(i)
                visited[i] = True

bfs(1)
cnt = 0
for i in range(1,n+1):
    if visited[i] == True:
        cnt += 1
print(cnt-1)
CATALOG
    algorithm