[Python Algorithm] 연결 요소의 개수 BOJ #11724

문제

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

11724번: 연결 요소의 개수

 

내 문제 풀이

# N이 10000까지 입력될 수 있으므로 아래와 같이 바꿔주어야 함
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

n, m = map(int, input().split())
connected = [[] for _ in range(n)]
visited = [0] * n
count = 0

for i in range(m):
    a, b = map(int, input().split())
    connected[a-1].append(b-1)
    connected[b-1].append(a-1)

def dfs(x):
    if visited[x] > 0: return
    visited[x] = count

    for i in connected[x]: dfs(i)

for i in range(n):
    if visited[i] == 0 and len(connected[i]) > 0:
        count += 1
        dfs(i)

# 아무 것도 이어지지 않은 혼자 남은 점 또한 하나의 연결 요소가 됨
for i in visited:
    if i == 0: count += 1

print(count)

👉 dfs 문제로, 모든 점을 돌아가며 몇 개의 그룹으로 나눌 수 있는지 판단해 주어야 함

아무것도 연결되지 않은 점도 하나의 연결 요소로 세어주어야 하는 것이 포인트 !

 

[ 반례 추가 ]

6 3

1 3

2 3

3 4

 

[ 변수 설명 ]

• connected는 각 점들이 어떤 점들과 연결되어있는지 저장해 줄 리스트이다.
  따라서 connected의 인덱스들은 리스트의 각 인덱스는 점을 의미한다고 보면 된다.
  위의 반례를 예로 들면, [[2], [2], [0, 1, 3], [2], [], []] 이렇게 저장된다.
  (리스트로 점들을 계산할 예정이므로 편하게 '점 - 1'값으로 생각했다.)
• visited는 각 점들을 체크했는지 검사하고, 점 마다 어떤 그룹에 속했는지 표시하는 리스트이다.
  dfs 함수로 해당 인덱스에 해당하는 점을 체크했다면 count 변수 값을 저장해주었다.
• count 변수는 하나로 연결된 점들의 dfs 탐색이 끝날 때마다 +1 해주므로,
  몇 개의 모임으로 이루어져있는지 구분할 수 있게 한다.

 

[ 메인 실행 ]

• 첫 번째 for문에서는 connected 리스트에 연결된 점들을 표시해주었다.
• 두 번째 for문에서는 0부터 n-1까지 반복하면서 알맞은 조건에 dfs 함수를 호출했다.
  (해당 점을 한 번도 체크한 적 없고, 해당 점이 연결된 점이 하나라도 있을 조건)
  그리고 dfs 함수를 실행하기 전에는 count를 증가시켜서 연결 요소들을 구분해주었다.
• dfs 함수에서는 호출되는 점마다 그에 연결된 점을 모두 탐색할 수 있게 했다.
  그리고 visited가 0보다 클 경우 return 해주어서 중복 탐색을 피했고,
  탐색하게 될 경우 해당 점의 위치에 해당하는 visited[x]에 count를 넣어줬다.
• 세 번째 for문은 아무 점과도 이어지지 않은 혼자 남은 점들을 세기 위함이다.
  visited 리스트를 탐색하여 0의 개수를 세어주었다.

 

💡 피드백

• 처음에 input의 리미트를 따로 지정해주어야 하는지를 몰라서 런타임 에러가 났는데,
  구글링해서 원인을 찾을 수 있었다. 이부분 공부해놔야 할듯
• 문제에서 주어진 케이스들로는 혼자 남은 연결 요소를 생각하기 어려워서
  계속 반례를 못찾았는데, 백준 질문검색에서 알맞은 반례를 찾았고,, 그래서 오래걸렸다.