문제링크

예제1

정점 6개, 간선 5개

예제2

정점 6개, 간선 5개

풀이 개념

인접 행렬을 쓸지 인접 리스트를 쓸지 먼저 판단을 해야 한다.

우선 간선 갯수를 확인해 보면 Nx(N-1)/2 까지 입력 될 수 있다.

대각선에 있는 숫자를 보면 다 자기 자신을 가르키고 있다.

서로 같은 정점을 뽑는 경우의 수만 뺀 나머지가 Nx(N-1)/2 이다. 결국 대각선 빼고 전부 다 간선으로 채워질수 있다는 의미이다. 결국 인접 행렬를 쓰는게 더 바람직하지 않을까 생각한다.

풀이 (dfs)

체크 배열을 먼저 다 false로 채워주고 반복문을 돌려서 false인 배열을 만나면 완전 탐색(dfs)을 돌린다.

현재 는 1 > 2 > 5 순서로 체크가 된 상태 (+1)

그다음 2가 체크가 되어 있으므로 체크가 안된 3을 확인한다.

그 다음 3 > 4 > 6 체크 한 다음 탐색 종료, 4,5,6은 다 체크가 된 상태이니 더 이상 체크할 필요 없음 (+1)

결국 +2가 되서 답은 2이다.

N, M = map(int, input().split())

# 인접 행렬 adj
adj = [[0] * N for _ in range(N)]

# M개 만큼 M줄 간선 정보 입력됨
for _ in range(M):
    a, b = map(lambda x: x - 1, map(int, input().split()))
    adj[a][b] = adj[b][a] = 1

for row in adj:
    print(row)

인접에서 -1을 했으므로

0, 1
1, 4
4, 0
2, 3
3, 5

각각 인접이 잘 된것을 확인 할 수 있음

시간 초과

import sys

# 재귀가 1000이상 걸리거 같음 sys.setrecursionlimit 사용
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())

# 인접 행렬 adj
adj = [[0] * N for _ in range(N)]

# M개 만큼 M줄 간선 정보 입력됨
for _ in range(M):
    a, b = map(lambda x: x - 1, map(int, input().split()))
    adj[a][b] = adj[b][a] = 1

# for row in adj:
#     print(row)

ans = 0
check = [False] * N


def dfs(now):
    for nxt in range(N):
        # 방문 체크
        if adj[now][nxt] and not check[nxt]:
            check[nxt] = True
            dfs(nxt)


# 배열  True / False 체크
for i in range(N):
    if not check[i]:
        ans += 1
        check[i] = True
        dfs(i)


print(ans)

시간 초과 해결법

시간초과 발생한 이유는 N이 최대 1000개 이므로 Nx(N-1)/2 은 최대 50만 정도가 입력되기 때문입니다.

python에서 시간 초과 같은경우 input 함수를 엄청 많이 호출함으로

기본 input 대신

input = sys.stdin.readline

더 빠른 입력함수 사용

import sys

# 재귀가 1000이상 걸리거 같음 sys.setrecursionlimit 사용
sys.setrecursionlimit(10 ** 6)
# 빠른 input 함수 만들기
input = sys.stdin.readline

N, M = map(int, input().split())

# 인접 행렬 adj
adj = [[0] * N for _ in range(N)]

# M개 만큼 M줄 간선 정보 입력됨
for _ in range(M):
    a, b = map(lambda x: x - 1, map(int, input().split()))
    adj[a][b] = adj[b][a] = 1

# for row in adj:
#     print(row)

ans = 0
check = [False] * N


def dfs(now):
    for nxt in range(N):
        # 방문 체크
        if adj[now][nxt] and not check[nxt]:
            check[nxt] = True
            dfs(nxt)


# 배열  True / False 체크
for i in range(N):
    if not check[i]:
        ans += 1
        check[i] = True
        dfs(i)


print(ans)