[Baekjoon] 11724_연결 요소의 개수

Silver II

문제(출처: https://www.acmicpc.net/problem/11724)

---

<연결 요소의 개수>

문제 

 

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

 

입력

 

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

 

출력 

 

첫째 줄에 연결 요소의 개수를 출력한다.

 

 

문제 풀이

- my solution

import sys

def bfs(graph, start,visited):
    queue=[start]

    while queue:
        x=queue.pop(0)
        if x not in visited: # 방문하지 않았다면
            visited.append(x) # 방문
            queue+=graph.get(x)
            queue=list(set(queue)) # 중복 제거


if __name__=='__main__':
    n,m=map(int, sys.stdin.readline().split())

    graph={}

    for i in range(n): #init
        graph[i+1]=[]

    for i in range(m): #방향 없는 그래프
        x,y=map(int, sys.stdin.readline().split())
        graph[x].append(y)
        graph[y].append(x)

    visited=[]
    result=0
    i=1
    while len(visited)!=n: # 연결 요소 개수 구하기
        if i not in visited:
            bfs(graph, i,visited)
            result += 1
        i+=1

    print(result)

 

• bfs
  - queue가 빌 때까지 반복: 젤 처음 값 pop 해서 방문하지 않았다면 visited에 추가 및 queue에 추가 (set을 활용하여 중복 제거)
• main
  - 입력
  - 방향 없는 그래프: 양방향으로 추가
  - 연결 요소 개수 구하기: visited 길이가 정점 개수와 같지 않다면 반복 -> 방문하지 않았다면 bfs 호출 및 result +1

---

생각🤔

 

처음에 시간 초과가 발생해서 set(queue)를 추가한 후 계속 위치 바꿔서 제출해봤는데 실패...

모르겠다 해서 다른 사람 코드를 봤는데 아차..

set(queue) 한 것을 변수에 대입을 안 했다 ,,,

이런 실수를 하다니.. 이 코드를 제출하니 바로 통과 완료 -!

 

단시간에 많은 제출...

 

 

---