[백준/Python] DFS/BFS - 11724번 연결 요소의 개수

풀이 👩🏻‍🏫

import sys
sys.setrecursionlimit(10000)
## 1
# 정점의 개수, 간선의 개수
n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1) 
count = 0

## 2
# graph = [[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]]
for i in range(m):
  a,b = map(int, sys.stdin.readline().split())
  graph[a].append(b)
  graph[b].append(a)
  
## 3
# DFS 정의
def dfs(graph,v,visited):
  # 방문 처리
  visited[v] = True
  # 해당 노드의 인접노드를 방문했는지 확인
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i,visited)
## 4
## 연결 요소 갯수 세기
for i in range(1, len(visited)):
  if visited[i] == False:
    count += 1
    dfs(graph,i, visited)

print(count)

• sys.stdin.readline()
  • input()은 시간초과 발생

그림 풀이

연결 요소

✏️ Python 문법

input() vs. sys.stdin.readline()

• input()

  • prompt 인자가 있을 경우, 개행문자없이 표준 출력에 쓴다
  • 함수는 입력을 통해 한 줄을 읽고, 문자열로 변환하고(개행문자를 제거) 값을 반환한다.
    

• sys.stdin.readline()

  • prompt message를 파라미터로 받지 않으며, 개행 문자를 포함하여 반환한다.
  • 입력 크기에 제한을 줘서 읽어들이고 싶은 만큼 읽기 가능
  • input()보다 빠르다

  import sys
   ## 한 개의 정수 입력받을 때
   # sys.std~ 가 한줄로 입력 받기 때문에 개행 문자도 입력 받아짐
   # 따라서 3\n이 저장되므로, 개행문자 제거해야 하고, int타입으로 사용하기 위해 형변환
   a = int(sys.stdin.readline())
   
   ## 임의의 개수의 정수를 한줄에 입력받아 리스트에 저장할 때
   # map()은 맵 객체를 만들기 때문에, 리스트형으로 바꿔주기 위해서 list()로 감쌈
   data = list(map(int,sys.stdin.readline().split()))
   
   ## 임의의 개수 정수 n줄 입력 받아 2차원 리스트에 저장할 때
   list_ = []
   n = int(sys.stdin.readline())
   for i in range(n):
   	data.append(list(map(int,sys.stdin.readline().split())))
     
   ## 문자열 n줄 입력 받아 리스트에 저장할 때
   # strip()은 문자열 맨 앞과 맨 끝의 공백문자를 제거
   n = int(sys.stdin.readline())
   data = [sys.stdin.readline().strip() for i in range(n)]
  

https://blog.sungmin.dev/102