[Baekjoon/🥈SilverⅡ] 11724: 연결 요소의 개수

Intro

접근 방법🙋‍♀️

연결 요소?

• 여기서 말하는 연결 요소란 하나로 이어진 그래프라 생각하면 쉽다.

• 다음의 예제에서 연결 요소의 개수는 두개이다.
• 연결 요소끼리는 서로 이어지지 않아야 한다.
  • 만약 (1, 2, 3)과 (4, 5, 6) 사이 하나의 간선이라도 존재한다면 연결 요소는 1개가 된다.

접근 방법?

해당 문제는 bfs 또는 dfs를 적용해 해결할 수 있다.

● bfs: 넓이 우선 탐색

● dfs: 깊이 우선 탐색

Algoritm👩‍💻

• 처음 나는 문제를 접하고 bfs나 dfs 방식이 아닌 내 나름의 방식으로 문제를 해결해보았다.

#21.01.08
#11724: 연결 요소의 개수

import sys
n, m = map(int, sys.stdin.readline().rstrip().split())
lst = []
check = set()
cnt = 0

for i in range(m):
  temp = list(map(int, sys.stdin.readline().rstrip().split()))
  temp.sort()
  lst.append(temp)
lst.sort(key= lambda i : (i[0], i[1]))

for f, b in lst:
  if f not in check and b not in check:
    cnt += 1
  check.add(f)
  check.add(b)

l = n - len(check)
print(cnt + l)

• 간선들을 입력받을 때 작은 수가 앞에 오도록 정렬을 하였다.
  • 또, 간선들끼리도 증가하는 순으로 정렬하였다.

• 간선을 하나씩 방문하면서 set에 간선에 포함된 정점들을 추가하였다.
  • set은 중복 저장이 되지 않으므로 최종적으로 방문한 정점만이 저장된다.
  • 간선에 포함된 두 정점이 모두 set에 존재하지 않을 경우 => 새로운 연결 요소이므로 cnt값을 하나 증가한다.

• cnt값과 하나의 정점이 연결 요소를 이루는 경우를 포함해 결과를 출력한다.

• 복잡한 방법만큼이나 시간이 매우 많이 걸린다…ㅠㅠ

Algorithm👩‍💻: BFS

• 그렇다면 bfs를 적용한 알고리즘을 살펴보자!

#21.01.08
#11724: 연결 요소의 개수
#bfs 사용하기

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

for i in range(m):
  f, b = map(int, sys.stdin.readline().split())
  graph[f].append(b)
  graph[b].append(f)

def bfs(v):
  order = [v]
  while order:
    t = order.pop()
    for j in graph[t]:
      if visited[j] == 0:
        order.append(j)
        visited[j] = 1

result = 0
for k in range(1, n+1):
  if visited[k] == 0:
    bfs(k)
    result += 1

print(result)

• 위 알고리즘과 시간차이가 엄청난 것을 확인할 수 있다!!!!!

그럼 해당 포스팅은 여기까지 하도록 한다!!

끝!! ~(˘▾˘~)

참고📃

https://velog.io/@i-zro/fdfdf