백준 11724 파이썬 풀이

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

문제

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

입력

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

출력

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

예제 입력 1 복사

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 복사

2

예제 입력 2 복사

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 복사

1

 

 

import sys
# sys.stdin.readline()
from collections import deque
global cnt
cnt = 1

def BFS(graph,visited,index):           
    queue = deque([index])
    global cnt
    visited[index] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    
    for i in range(1,N+1):
         if visited[i] == False:
              cnt +=1
              arrayindex = i
              BFS(graph,visited,arrayindex)
    
    return cnt

N,M =map(int,sys.stdin.readline().split())


graph2 = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,sys.stdin.readline().split())
    graph2[x].append(y)
    graph2[y].append(x)

count = 1
visited = [False] * (N+1)
print(BFS(graph2,visited,1))

 

 

원래 bfs는 재귀함수로 쓰이는 형태는 아니지만 싸이클의 개수를 찾아야 했기 때문에..

그냥 while문 돌린 이후에 visited 배열에서 방문처리 되지 않은 애가 있다면 걔를 시작점으로 해서 다시 bfs를 실행하면 되지 않을까?

를 먼저 생각하고 풀었다.

풀 때 입력 예시는 다 맞는데, 왜 40%에서 틀렸다고 뜨는지 궁금해서 새로운 예시를 만들어서 입력했다.

 

예를 들어서 1,2,3이 모두 연결 / 4,5,6이 모두 연결 / 7,8,9 가 모두 연결되어 있다면 연결 요소의 개수는 3이 나와야 했다.

처음에는 cnt를 전역변수가 아니라 메인함수에서 1로 선언한 후에 재귀를 돌렸는데,

위와 같은 예시에서 cnt의 변화가 1->2->3인데 재귀함수의 return이 역순이 되어서 3->2 

최종 cnt의 값이 2가 되어서 출력이 되는 것이었다.

아직 실력이 부족해서 전역변수로 선언해서 해결했다. 

 

얻어갔던 개인적인 포인트

1. global 함수는 함수 바깥과 함수 내부에 모두 선언해주어야 한다(안그러면 함수 내에서 지역변수로 판정하므로)

2. 재귀함수의 return은 역순이 된다는 것에 주의하자.

 

최종 코드는 꽤 간단하게 나왔지만.. 푸는데 꽤 골머리 앓았다.

이러면서 성장하는 거겠죠 ㅋㅋ 코린이들 모두 파이팅 !