[백준/BOJ] 11724번 : 연결 요소의 개수 _Python

11724번: 연결 요소의 개수

 

>문제

>접근방법

   그래프 탐색으로 한 번 탐색이 종료될 때마다 count 개수를 세면 되겠다.

 

 

>풀이법

   주석으로 대체

 

 

>코드

1) bfs로 푼 코드

import sys
from collections import deque
# 시간초과 방지를 위한 코드 (input()으로 입력받으면 시간초과가 뜸)
input = sys.stdin.readline

# 노드와 간선의 개수를 각각 입력 받기
n, m = map(int, input().split())

# 방문 확인을 위한 리스트 False값으로 디폴트 설정
visited = [False for _ in range(n+1)]
# 그래프 생성 0은 제외해야하기 때문에 1만큼 크게 만들어줌
graph = [[] for _ in range(n+1)]
# 결괏값을 담을 변수 
cnt = 0

# 간선의 정보를 입력 받기
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 연결된 요소를 확인하는 함수
def bfs(S):
	# 너비우선탐색을 위한 큐 생성, 인자로 받은 노드 번호를 넣는다.
    queue = deque([S])
    # 인자로 받은 번호의 노드를 우선 방문처리 한다.
    visited[S] = True
	
    # 큐가 빌 때까지 반복(연결된 노드를 모두 방문할 때까지)
    while queue:
    	# 큐의 값을 가져와 node에 삽입
        node = queue.popleft()
        # node와 연결된 다른 노드를 하나씩 확인한다.
        for i in graph[node]:
        	# i가 아직 방문하기 전이라면
            if not (visited[i]):
            	# 큐에 삽입하고 방문처리를 해준다.
                queue.append(i)
                visited[i] = True

# 방문하기 전인 노드를 노드 전체 개수만큼 반복하며 탐색한다.
# 방문하기 전이라면 bfs() 함수를 수행하고 종료될 때마다 cnt에 1을 더해준다.
for j in range(1, n+1):
    if visited[j] == False:
        bfs(j)
        cnt += 1

# 결괏값 출력
print(cnt)

 

2) dfs로 푼 코드

import sys
# 런타임 에러(재귀오류)를 방지하기 위한 코드
sys.setrecursionlimit(10000)
# 시간초과 방지를 위한 코드 (input()으로 입력받으면 시간초과가 뜬다)
input = sys.stdin.readline

# 노드와 간선의 개수를 입력받는다.
n, m = map(int, input().split())
# 결괏값을 담을 변수
cnt = 0

# 노드 개수만큼 빈 그래프 생성, 0은 제외되기 때문에 n+1 크기로 만든다.
graph = [[] for _ in range(n+1)]
# 방문 처리를 위한 리스트 생성, 마찬가지로 n+1의 크기로 만든다.
visited = [False for _ in range(n+1)]

# 간선의 정보를 입력받는다.
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 연결된 요소를 탐색하는 함수
def dfs(S):
	# 먼저 인자로 받은 노드를 방문처리 한다.
    visited[S] = True
    # 인자로 받은 노드의 연결된 노드들을 하나씩 탐색
    for i in graph[S]:
    	# i가 아직 방문하기 전이라면
        if visited[i] == False :
        	# i를 재귀 호출한다.
            dfs(i)

# 아직 방문 전인 모든 노드를 탐색한다.
for j in range(1, n+1):
    if visited[j] == False:
        dfs(j)
        dfs가 종료될 때마다 연결된 요소의 개수를 1 더해준다.
        cnt += 1

# 결괏값 출력
print(cnt)

 

>결과

 

>결론 

문제는 간단한데 시간초과가 떠서 당황했다. 다르게 푸는 방법이 있나 싶었는데 입력받는 코드가 input()은 개행문자를 포함하기 때문에 시간초과가 날 수 있다고 한다. 여러 줄을 입력 받아야 하는 경우에는 sys의 sys.stdin.readline()을 사용하는게 좋다고 한다. 줄 바꿈을 하는 개행문자 없이 바로 다음 줄로 이동하기 때문이다. 그것도 모르고 bfs로 했더니 안되길래 dfs로 하면 될까 싶어 두 번 풀었다. 속도 차이는 근소하네. 다음부턴 input = sys.stdin.readline 을 첫 줄에 적고 시작해야겠다.