백준 11724 연결 요소의 개수 파이썬 풀이, 시간초과, 반례

난이도 : 실버2
풀이일 : 04145
https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

---

링크로 이동하기 귀찮은 분들을 위한 캡쳐

 
연결 요소는 길을 통해 갈 수 있는 정점 무리 의미

---

1차 시도 오답

import sys

n, m = list(map(int, sys.stdin.readline().split()))
load = [[0] * (n+1) for _ in range(n+1)]
for _ in range(m):
    u, v = list(map(int, sys.stdin.readline().split()))
    load[u][v] = load[v][u] = 1
connect = []

for i in range(1, n+1):
    visited = [0] * (n+1)
    visited[i] = 1
    temp = i
    stack = [i]
    while stack:
        k = stack.pop()
        for j in range(1, n+1):
            if load[k][j] == 1 and visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                load[k][j] = load[j][k] = 0
                temp += j
    if temp > i:
        connect.append(temp)

print(len(connect))

코드 구성
1. 노드, 간선 정보 2차원 배열에 저장 (방향성이 없으므로 순서를 바꾼 길도 함께 저장)
2. 전 노드를 순회하며 stack 이용한 DFS 구현, stack 추가 시 양방향 길 모두 삭제
3. visited로 방문 여부 확인 후 미방문 시 stack 추가
4. connect에 이동하지 않은 초기 노드만 추가되는 경우가 없도록 temp와 비교
 
틀린 이유
1. 시간 초과
2. 원형으로 모두 이어진 경우 문제 발생

---

2차 시도 오답

import sys

n, m = list(map(int, sys.stdin.readline().split()))
load = [[0] * (n+1) for _ in range(n+1)]
for _ in range(m):
    u, v = list(map(int, sys.stdin.readline().split()))
    load[u][v] = load[v][u] = 1
connect = 0

for i in range(1, n+1):
    visited = [0] * (n+1)
    visited[i] = 1
    temp = [i]
    stack = [i]
    while stack:
        k = stack.pop()
        for j in range(1, n+1):
            if load[k][j] == 1 and visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                load[k][j] = load[j][k] = 0
                temp.append(j)
    for j in range(len(temp)):
        for k in range(len(temp)):
            if load[temp[j]][temp[k]] or load[temp[k]][temp[j]]:
                load[temp[j]][temp[k]] = load[temp[k]][temp[j]] = 0
    if len(temp) > 1:
        connect += 1

print(connect)

코드 변화
1. 원형으로 이어진 경우 해결 코드 추가 -> 반복문을 통해 temp 속 모든 요소들의 간선 파악, 삭제
 
틀린 이유
1. 연결 노드 정보가 충분히 삭제되지 않는 경우 발생
2. 연결 노드가 없는 노드를 세지 않는 문제 발생

---

최종 정답

# 1. 전체 길 2차원 배열에 저장
# 2. 이차원 배열을 탐색하며 1을 만나면 DFS 함수 실행, count += 1
# 3. 카운트 수 출력

import sys

# 간선 삭제 함수
def DFS(arr, num):
    visited = [0] * n
    connect = [num]
    stack = [num]
    while stack:
        i = stack.pop()
        for j in range(n):
            if arr[i][j] == 1 and visited[j] == 0:
                connect.append(j)
                stack.append(j)
                visited[j] = 1
    # 모든 연결 노드 간선 삭제 
    for x in range(len(connect)):
        for y in range(len(connect)):
            arr[connect[x]][connect[y]] = arr[connect[y]][connect[x]] = 0
    return

n, m = list(map(int, sys.stdin.readline().split()))
load = [[0] * n for _ in range(n)]
for _ in range(m):    # 양방향 간선정보 저장
    u, v = list(map(int, sys.stdin.readline().split()))
    load[u-1][v-1] = load[v-1][u-1] = 1

for w in range(n):    # 간선 없는 노드 파악을 위한 작업
    load[w][w] = 1

count = 0

# 2차원 배열 순회하며 간선 발견 시 함수 실행
# 함수 실행 시, 연결 요소 개수 +1
for a in range(n):
    for b in range(n):
        if load[a][b] == 1:
            DFS(load, a)
            count += 1

print(count)

코드 변화
1. 노드 정보 0부터 저장 -> 습관적으로 1부터 표시하던 건데 그냥 바꿈
2. 모든 노드에 대해 본인과의 간선 표시 -> 간선 없는 노드 파악을 위한 작업
3. 2차원 배열 순회하며 간선 발견 시 함수 실행 -> 연결 요소 개수 세는 방법 변경

---

반례

입력	2 0	3 2 1 2 3 2
출력	0	1

---

시간초과 해결
파이썬으로 동일 코드를 올리면 계속 시간 초과 발생
질문 게시판을 참고하여 언어를 pypy로 변경하면 통과!

---

느낀점
일단 코드를 짜고 수정하는 대신 로직을 생각하고 체계화 한 다음에 구현하자
반례를 스스로 생각해보고 처음 로직에 담아낼 수 있도록 하자