boj_11724_연결 요소의 개수

 

문제는 아래 링크를 통해서 보시면 될것 같슴다.

​

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

 

11724번: 연결 요소의 개수

11724번 제출 맞은 사람 숏코딩 재채점/수정 채점 현황 강의 연결 요소의 개수 분류 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 3 초 256 MB 30992 15164 9925 46.096% 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u,...

www.acmicpc.net

우선 인접 리스트와 DFS를 활용하여 풀어보았습니다. 참고로 인접리스트는 dict 클래스를 활용하였습니다.

 

 

 

import sys
sys.stdin = open('input.txt', 'r')

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

check_dict = {}
for i in range(N):
    check_dict[i+1] = []

for i in range(M):
    u, v = map(int, input().split())
    check_dict[u].append(v)
    check_dict[v].append(u)

result = 0

while check_dict:
    stack = []
    visited = []
    stack.append(list(check_dict)[0])
    while stack:
        node = stack[len(stack)-1]

        if node not in visited:
            visited.append(node)

        for w_node in check_dict[node]:
            if w_node not in visited:
                stack.append(w_node)
                break
        else:
            stack.pop()

    for node in visited:
        del(check_dict[node])
    result += 1

print(result)

결과는...시간 초과..

​

실행 언어를 PyPy3으로 바꿔주면 돌아가긴 한다고 해서 돌려봤더니 돌아가긴 해요. PyPy가 컴파일을 활용해서 그렇다는데 언제 한 번 이것 관련해서도 포스팅을 해봐야겠습니다.

실행 속도 : 1204ms

​

그래서 크게 두 가지 부분을 바꿔봤습니다.

​

1. 혹시 인접리스트를 dict로 활용해서 그런가 싶어서 list로 변경해봤습니다.(근데 제가 알기론 dict가 key 검색이 복잡도가 낮은 걸로 알고 있긴 하지만..)

2. 방문했는지 확인하는 코드를 in 연산자를 활용하는 것이 아닌 visited를 False의 리스트로 만들고 방문할 때마다 True로 변경하는 식으로 하고 방문 체크할 때는 visited 리스트의 인덱싱을 통해서 체크하였습니다.

​

import sys
sys.stdin = open('input.txt', 'r')

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

check_list = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    check_list[u].append(v)
    check_list[v].append(u)

count = 0
visited = [False for _ in range(N+1)]

for node in range(1, N+1):
    if not visited[node]:
        stack = []
        stack.append(node)
        while stack:
            node = stack[len(stack) - 1]

            if not visited[node]:
                visited[node] = True

            for w_node in check_list[node]:
                if not visited[w_node]:
                    stack.append(w_node)
                    break
            else:
                stack.pop()
        count += 1

print(count)

하지만 또 결과는...시간 초과..

​

PyPy3으로 바꿔주니 웃긴건 줄어들긴 했습니다.

실행 속도 : 952ms

​

그럼 뭐하니..Python에서 시간 초과가 뜨는데..계속 삽질 중인데 성공하는 대로 글 업데이트를 해야겠습니다. 다시 코딩하러 갑니다.

​

---

해결하고 난 후..

​

결국 해결하긴 했는데 생각보다 더 원초적인 문제였다. 데이터 빨리 못 받는게 큰 문제였던거 같다.

평소에 쓰던 input().split()을 쓰지 않고 아래 코드를 사용한다.

 

import sys
N, M = map(int, sys.stdin.readline().split())

 

그렇게 변경된 데이터를 받아오는 코드는 아래와 같다.

 

import sys

N, M = map(int, sys.stdin.readline().split())

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

​