[파이썬/Python] 백준 11724번 연결 요소의 개수

[파이썬/Python] 백준 11724번 연결 요소의 개수

11724번: 연결 요소의 개수

---

문제

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

 

해설

1. 간선의 양 끝점을 통해 정점끼리의 연결관계를 정리해준다.

2. 정점을 방문하고, 방문한 정점을 체크하여 연결관계를 확인한다. (DFS)

3. 더 이상 연결된 정점이 없으면 함수를 종료하고 연결 요소를 1 증가시킨다.

4. 모든 정점 N에 대해 2~3 과정을 반복한다.

 

코드

import sys
sys.setrecursionlimit(2500)

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

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    if u in graph:
        graph[u].append(v)
    else:
        graph[u] = [v]
    
    if v in graph:
        graph[v].append(u)
    else:
        graph[v] = [u]

def dfs(u):
    visited[u] = True
    if u in graph:
        for v in graph[u]:
            if visited[v] == False:
                dfs(v)

visited = [False for _ in range(N+1)]
count = 0

for u in range(1, N+1):
    if visited[u] == False:
        dfs(u)
        count += 1

print(count)

 

풀이

import sys
sys.setrecursionlimit(2500)

1. Python 은 PyPy3와 다르게 재귀 깊이가 1000으로 제한되어 있다. 따라서 재귀 깊이를 임의로 수정할 필요가 있다.

 

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

2. 정점의 수 N과 간선의 개수 M을 입력 받고, 그래프를 받아줄 딕셔너리도 초기화해준다.

 

앞으로 input() 대신 sys.stdin.readline() 을 사용할 예정이다.

 

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    if u in graph:
        graph[u].append(v)
    else:
        graph[u] = [v]
    
    if v in graph:
        graph[v].append(u)
    else:
        graph[v] = [u]

3. 양 끝점 u, v 를 입력받고, graph 딕셔너리에 저장해준다.

 

def dfs(u):
    visited[u] = True
    if u in graph:
        for v in graph[u]:
            if visited[v] == False:
                dfs(v)

4. 정점을 방문하는 함수 dfs 이다.

해당 정점을 방문했기 때문에 먼저 True 로 방문표시를 해준다.

정점 u 와 연결되어 있는 정점 v 들에 대해 dfs 함수를 재귀호출하여, 정점 u와 연결되어 있는 모든 정점들을 방문처리 해준다.

 

visited = [False for _ in range(N+1)]
count = 0

for u in range(1, N+1):
    if visited[u] == False:
        dfs(u)
        count += 1

print(count)

5. 방문을 처리할 visited 리스트를 False 로 초기화해주고, 연결 요소의 개수를 구해줄 count 도 초기화한다.

모든 정점에 대해 방문하지 않은 정점이라면, dfs 함수를 호출하고 개수를 카운트해준다.

 

피드백

꼬박 하루가 걸려 문제를 해결하고 이제야 겨우 포스팅을 한다.

 

처음 RecursionError 가 발생했던 이유는 재귀 깊이를 수정하지 않았기 때문이다.

이 부분은 코드에 문제가 있나 확인이 필요했기 때문에 고민을 많이 했고, 결국 내 코드에는 문제가 없었다..

 

두번째 시간초과 오류는 무엇이 문제인가 알아보던 중, PyPy3 에 대해 알게 되었고,

PyPy3 로 돌렸을 때는 문제가 해결되어 PyPy3의 장점 때문에 해결되었다! 라기에는

Python 으로는 해결되지 못한 찝찝함이 가시지 않았다.

 

글 읽기 - pypy3랑 python3 차이가 궁금합니다.

위의 글을 읽어보면서 Python 으로 문제를 해결한 사람들도 많이 보았고, 결국 Python 으로 해결하기 위해 다른 해결책을 모색하였다.

결국, Python 으로 문제를 해결하게 된 방법은, 기존에 입력했던 input() 을 sys.stdin.readline() 으로 치환하면서 해결되었다.

다른 사람들이 해결한 문제들을 볼 때, 왜 편한 input() 을 냅두고 sys.stdin.readline() 같은 긴 문장을 쓰는걸까? 하며 이해하지 못했다.

아아.. 선배님들은 다 이유가 있었다 ㅠ

 

하루가 걸려 해결한 문제는 결국 내가 작성한 로직의 문제라기 보다는, 내가 언어에 대한 지식이 부족했던 탓이 컸다.

내가 회의감이 드는건 편하기 위해 사용했던 python 이 되려 그 편리함 때문에 제약사항이 많다는 점이다.

원래부터 python 이 기존 언어들보다 편하기 때문에 그만큼 느리다는 단점은 알고 있었지만, 딱히 내가 시간에 대한 고민이 크지 않았기에 별로 와닿지 않았었다.

근데 이제 확실히 느껴진다. 그래도 파이썬은 여전히 문법적인 측면에서 편하다ㅋ

 

내가 새롭게 알았던 지식들에 대해서 하나로 정리해서 포스팅을 해볼까 했지만 이미 깔끔하게 정리하신 분이 계셔서 아래 글을 숙지하고 파이썬을 풀면 좋을 것 같다.

파이썬으로 문제 풀 때 주의해야할 점들