023 연결 요소의 개수

첫번째 코드

 

DFS를 처음 접해 관련된 함수 코드를 어떻게 작성해야 할 지 몰라 책을 참고했다

 

- DFS 함수로 v의 위치가 False이면 지났다고 가정하므로 True로 바꾸고 v를 통해서 갈 수 있는 값들 모두 DFS 함수를 돌리는 과정을 통해 True로 바꾸는 함수를 생성한다

- A라는 리스트 안에 0, 1, 2, ..., n의 값에서 어디로 갈 수 있는 지를 적어넣는다 (양방향의 문제이므로 양방향으로 적어 넣는다)

- 마지막으로 해당 함수를 돌리는 코드를 작성한다. 이때 n의 개수만큼 돌려 뺴먹지 않는 수가 없도록 한다

각 수에 대해 DFS를 돌리면 된다!

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
A =[[] for _ in range(n+1)]
visited = [False] * (n+1)

def DFS(v):
    visited[v] = True
    for i in A[v]:
        if not visited[i]:
            DFS(i)
    
for _ in range(m):
    e, s = map(int, input().split())
    A[e].append(s)
    A[s].append(e)

count = 0

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

print(count)

---

 

두번째 코드

 

Recursion Error가 떠서 그게 무엇인가 알아봤더니, 파이썬의 재귀 한계를 넘어가서 생기는 문제라고 한다.

그렇기 때문에 재귀 한계를 늘리는 설정으로 해결이 가능하다.

 

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

n, m = map(int, input().split())
A =[[] for _ in range(n+1)]
visited = [False] * (n+1)

def DFS(v):
    visited[v] = True
    for i in A[v]:
        if not visited[i]:
            DFS(i)
    
for _ in range(m):
    e, s = map(int, input().split())
    A[e].append(s)
    A[s].append(e)

count = 0

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

print(count)

 

통과!

 

DFS 개념을 처음 접한 것이므로 몇 번 더 관련된 함수 코드를 작성하는 연습이 필요하듯 하다

하지만 일단 잘 이해하고 들어본 것으로 만족하고 다음에 한 번 더 보도록 하자!

하루안에 모든걸 마스터 하려하지 말고 차근차근!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/11724.%E2%80%85%EC%97%B0%EA%B2%B0%E2%80%85%EC%9A%94%EC%86%8C%EC%9D%98%E2%80%85%EA%B0%9C%EC%88%98

programmers/백준/Silver/11724. 연결 요소의 개수 at main · ornni/programmers