백준 11724

<연결 요소의 개수 구하기>

난이도 : 실버2

1. 백준 문제
   백준 11724

2. 코드 알고리즘
   

3. 코드

import sys
sys.setrecursionlimit(5000)
input=sys.stdin.readline
N, M=map(int, input().split())
cs_list = [[] for _ in range(N+1)]
check_list=[0]*(N+1)
cn_com=0

def DFS(i):
    check_list[i]=1
    for j in cs_list[i]:
        if not check_list[j]:
            DFS(j)

for _ in range(M):
    a, b = map(int, input().split())
    cs_list[a].append(b)
    cs_list[b].append(a)

for i in range(1, N+1):
    if not check_list[i]:
        cn_com +=1
        DFS(i)

print(cn_com)

4. 후기

   • sys.setrecursionlimit()

   재귀함수 꼴 코드를 선언시에는 항상 깊이제한두기!
   python의 깊이제한은 1000이라고 한다
   런타임에러에 빠질 수 있으니 꼭 깊이제한 하고 가기

   • DFS

   말그대로 깊이제한을 두어야 한다.
   DFS() 함수 정의 시 방문한 노드를 탐색하고
   그 노드 안 요소를 다음으로 탐색해야 한다
   시작점 노드를 기준으로 파고들고 파고들어서 끝까지 도달 후
   다시 시작점 노드로 가 다른 분기점 노드로

   결국 그 노드안 요소를 다음으로 탐색해야 함이 중요

   • 인접 리스트

   인접리스트 선언시 노드 인덱스에 신경쓰지 말기
   인접리스트는 해당 노드의 양 끝점 값만 저장하면 됨

   ! 이차원 배열로 선언하기
   -> 노드에 인접 노드 저장시 (즉, 1번째 노드에 인접한 노드 2와 5 저장 시)
   list[1].append(노드)
   하면 list[1]=2,5로 저장

   주의할점은 한쪽만 연결되는 것이 아니므로 list[1]=2일시
   list[2]=1이어야 한다는 점!

좀 많이 많이 많이 빡쳤음
마지막에 계속 런타임에러 걸려서 개빡쳤었는데
readline() 공백 설정해서 그런거였음
휴...
코드는 항상 정직하다ㅋㅋ