백준 11724(파이썬):연결 요소의 개수

13 Oct 2023 in CS study / Baekjoon

백준 11724번 문제 정리글 입니다.

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

• 문제 내용
• 나의 풀이
• 풀이를 본 후
• 해결한 후
• 참조 링크

문제 내용

나의 풀이

    import sys

    n,m=map(int,sys.stdin.readline().split())
    relation=[[]for i in range(n+1)]
    visited=[0]*(n+1)
    visited[0]=1

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

    for i in relation:
        i.sort()

    def bfs():
        count=0

        while sum(visited)<n+1:
            v=visited.index(0)
            queue=[v]
            visited[v]=1
            while queue:
                v=queue.pop(0)
                for i in relation[v]:
                    if visited[i]==0:
                        visited[i]=1
                        queue.append(i)
            count+=1
            
        return print(count)

    bfs()

1. 우선 BFS로 방문하지 않은 정점을 탐색해준다.
2. 탐색 가능할 때까지 탐색 후, 다른 정점을 탐색해야하면 다시 탐색하고 아니면 끝내준다.
3. 따라서, 이렇게 탐색가능할 때까지 BFS 탐색을 반복하여 찾은 연결요소의 개수를 출력해준다.

지난번에 BFS문제를 푼것이 도움이 많이 되었다…

풀이를 본 후

DFS로의 풀이도 존재했다…

해결한 후

DFS, BFS의 개념을 항상 잘 알고있어야 할것 같다. 또한, 연결요소의 개념을 다시한 번 확인해보는 시간이었다…

참조 링크

• https://brain-nim.tistory.com/62