백준 #11724 연결요소 개수 풀이

백준 #11724 연결요소 개수 풀이

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

단순히 bfs로 풀면 되지만 입력 받는 값의 범위 (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 로 인하여 시간 초과가 발생하였다.

map(int, input().split)를 사용하여 처음에 변수를 받았는데, 아래 처럼 변경하여 시간 초과를 해결하였다.

map(int , read().split())

▶ input().split()과 read().split의 차이는 뭘까?

파이썬 공식 문서에 따르면 input()의 처리과정은 다음과 같다.

input()함수 호출 -> 인자로 주어진 프롬프트 문자열을 화면에 출력하고 사용자 입력을 기다림 -> 사용자에게 입력받음 -> 입력 문자 하나하나에 대응하여 버퍼에 저장 -> enter를 입력함과 동시에 개행문자 '

' 가 입력되고 버퍼 입력 종료 -> 해당 시스템의 콘솔 입출력 인코딩을 사용하여 디코드되어 유니코드 문자열로 변환 -> 줄바꿈문자 제거 -> 값을 반환

readline의 처리과정은 다음과 같다.

readline 호출 -> 사용자 입력받음 -> 문자열 형태로 한 번에 버퍼에 저장 -> 값을 반환

두 함수의 속도의 차이는 결국, 1. prompt 메시지를 출력하는가 2. 입력에 대한 버퍼사이즈 차이인데 , 문자에 대응하여 버퍼에 입력하는 input과 달리 한번에 읽어와 저장하는 readline은 입력이 반복될수록 더 우위에 있을 수 밖에 없다.

BFS로 구현

#-*- coding: utf-8 -*- from collections import deque import sys # n의 범위는 1<= n <= 1000 , m의점위는 0 <= m <= n*(n-1)/2 read = sys.stdin.readline n,m = map(int, read().split()) graph = [[] for _ in range(n+1)] visited = [0] * (n+1) for _ in range(m): a,b = map(int , read().split()) graph[a].append(b) graph[b].append(a) def bfs(num): queue = deque() visited[num] = 1 queue.extend(graph[num]) while queue: node = queue.popleft() if visited[node] == 0 : visited[node] = 1 queue.extend(graph[node]) return count = 0 #For문 돌면서 아직 방문하지 않은 노드를 찾으면서 count + 1 해준다. for i in range(1,n+1): if visited[i] == 0: bfs(i) count += 1 print(count)

DFS로 구현

from collections import deque import sys sys.setrecursionlimit(10000000) #파이썬은 재귀함수 호출 시 기본 디폴트로 호출 수 1000로 세팅되기 때문에 #위와같이 호출수를 별도로 선언해줘야한다. read = sys.stdin.readline n,m = map(int, read().split()) graph = [[] for _ in range(n+1)] visited = [0] * (n+1) for _ in range(m): a,b = map(int , read().split()) graph[a].append(b) graph[b].append(a) count = 0 def dfs(num): visited[num] = 1 for i in graph[num] : if not visited[i]: dfs(i) return for i in range(1,n+1): if visited[i] == 0: dfs(i) count += 1 print(count)

from http://meaningful-story.tistory.com/9 by ccl(A) rewrite - 2021-12-10 19:01:25