leah

my dev_log

0%

BOJ 11724

Posted on In ,

Input

python을 사용할 때 시간 초과 를 방지하기 위해, sys 를 이용하여

sys.stdin.readline() 혹은 sys.stdout.write() 를 사용한다!

sys.stdout.write() 의 args 는 string 이어야 하므로, str() 를 사용할 것!

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)

둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

1
2
3
4
5
6
7
N, M = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(N+1)]

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

DFS

  • 일단 visited = True 로 체크하고,
  • adj 배열의 요소를 전부 돌면서 아직 visited 하지 않은 경우 같은 과정을 반복하며 visited = True 로 체크한다. == DFS
1
2
3
4
5
6
def dfs(u):
  visited[u] = True

  for v in adj[u]:
    if not visited[v]:
      dfs(v)

Default

  • 재귀함수 문제에서는 항상 sys.setrecursionlimit() 를 설정하자.
1
2
3
4
import sys
sys.setrecursionlimit(10000)

visited = [False]*(N+1)
1
2
3
4
5
6
count = 0

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

Wrong Answer

처음 시도했던 방법은 아래와 같은데, 시간 초과 가 뜸.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
graph = [list(map(int, input().split())) for _ in range(M)]
visited = [False]*(N+1)

def dfs(u):
  visited[u] = True

  for i in range(M):
    if graph[i][0] == u:
      v = graph[i][1]
      if not visited[v]:
        dfs(v)

count = 0

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

  • 다른 부분은 input() 과,

  • 입력을 근접한 노드를 담는 adj 대신 그대로 저장하는 2차원 배열 graph 을 사용한 것 뿐인데

sys 을 이용해도 위 코드가 시간 초과 가 뜨는 이유는 무엇일까?

; 이유는 위 코드는 근접한 노드만을 하나씩 돌며 dfs를 실행하는 것이 아니라,

  • 주어진 조건을 모두 다시 돌며 index == 0 의 값이 해당 값인지 체크하고,
  • 같을 때 dfs를 실행해야 하므로 N, M가 클 때는 배열을 전부 다시 탐색하는 것이 근접한 노드만 검사할 때보다 훨씬 시간이 많이 필요하기 때문.

Output

첫째 줄에 연결 요소의 개수를 출력한다.

1
sys.stdout.write(str(count))