[Python/DailyAlgo] 28. 그래프 탐색

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

DFS/BFS

https://dailyalgo.kr/ko/problems/28

---

풀이

DFS 풀이

# counts 쓴 버전
def solution(n, edges):

    def dfs(node):
        # 지금 있는 위치가 local인데,
        # 그 local보다 한 레이어 바깥에 있는,
        # 즉 nonlocal한 변수인 counts를 여기서 가져와 쓰겠다는 거
        # 두 레이어 바깥에 있었다면 global을 썼어야 함.
        nonlocal counts
        counts += 1
        # 우리는 dfs에 그 노드가 호출된 것 자체가
        # 그 노드에 방문했단 걸 의미하므로, counts 1 증가시키면 됨.

        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                dfs(next_node)

    # 파이참에서 한 수업 코드와 달리, 
    # 여긴 n + 1로 크기를 설정해줘야 한다!!
    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    counts = 0

    for edge in edges:
        s, e = edge
        graph[s].append(e)
        graph[e].append(s)

    # 당연히 방문 처리랑 dfs도 1부터 시작해야 함
    visited[1] = True
    dfs(1)

    return counts

# DFS 전형적인 문제.
# O(V + E) = 1만 + 100만 = 101만 정도로 시간복잡도 선에서 세이프.

# 입력 : 정점의 개수 n과 간선 정보가 담긴 2차원 리스트 edges
# 출력 : 1번 정점에서 출발해 도달할 수 있는 모든 정점의 개수

# 이 문제는 도달 가능한 노드 개수라 했지만,
# 사실상 시작 노드가 포함된 하나의 영역, 하나의 덩어리의 크기를 구하라는 거라,
# 그게 섬의 크기처럼 표현이 됨.

# counts 안 쓴 버전


def solution(n, edges):

    def dfs(node):
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                dfs(next_node)
                
    # 파이참에서 한 수업 코드와 달리, 
    # 여긴 n + 1로 크기를 설정해줘야 한다!!
    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)

    for edge in edges:
        s, e = edge
        graph[s].append(e)
        graph[e].append(s)

    # 당연히 방문 처리랑 dfs도 1부터 시작해야 함
    visited[1] = True
    dfs(1)

    return visited.count(True)

# DFS 전형적인 문제.
# O(V + E) = 1만 + 100만 = 101만 정도로 시간복잡도 선에서 세이프.

# 입력 : 정점의 개수 n과 간선 정보가 담긴 2차원 리스트 edges
# 출력 : 1번 정점에서 출발해 도달할 수 있는 모든 정점의 개수

# 이 문제는 도달 가능한 노드 개수라 했지만,
# 사실상 시작 노드가 포함된 하나의 영역, 하나의 덩어리의 크기를 구하라는 거라,
# 그게 섬의 크기처럼 표현이 됨.

BFS 풀이

# counts 쓴 버전
from collections import deque
def solution(n, edges):

    def bfs(node):
        nonlocal counts
        queue = deque([node])
        
        while queue:
            # 이거 한 번 한 번이 그 노드를 방문했다는 거임
            node = queue.popleft()
            counts += 1

            # 중요!!!

            # visited[node] = True

            # 아래 visited를 빼고 위 코드를 하면,
            # 틀림!! 굉장히 중요한 요소.
            # 왜냐하면, 저렇게 하면 if not이 안 걸려서,
            # 새로운 큐를 pop하기 전에, 한 동작에서
            # 인접 노드를 확인할 때, ex. 3이 중복으로 들어가게 됨.
            # 그래서 counts가 더 오르게 됨.

            # 예를 들어, 1에서 시작해서 queue에 2 3을 넣었고,
            # 이제 2로 가서 (아직 3은 방문 처리 안됨),
            # 인접한 거 4만 큐에 넣어야 하는데, 3도 큐에 들어가게 됨.

            # 인접 노드 확인
            for next_node in graph[node]:
                if not visited[next_node]:
                    visited[next_node] = True
                    queue.append(next_node)


    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    counts = 0

    for edge in edges:
        s, e = edge
        graph[s].append(e)
        graph[e].append(s)

    visited[1] = True
    bfs(1)

    return counts

---

250218 재풀이

DFS

def solution(n, edges):

    # 정점 번호 1부터 시작

    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    for edge in edges:
        s, t = edge
        graph[s].append(t)
        graph[t].append(s)
    
    def dfs(node):
        # 2. 재귀하며 현재 정점에서 action 실행
        nonlocal counts
        counts += 1
        
        # 3. 인접한 모든 정점들에 대해
        for next_node in graph[node]:
            # 4. 방문x 인접 정점으로 이동(함수 호출)
            if not visited[next_node]:
                visited[next_node] = True
                dfs(next_node)

    counts = 0
    # 1. 시작 정점 방문 처리
    visited[1] = True
    dfs(1)
    return counts

BFS

from collections import deque
def solution(n, edges):

    # 정점 번호 1부터 시작

    graph = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    for edge in edges:
        s, t = edge
        graph[s].append(t)
        graph[t].append(s)
    
    def bfs(node):
        nonlocal counts
        queue = deque([node])

        # 2. queue가 빌 때까지 반복
        while queue:
            # 3. pop하며 현재 정점에서 action 실행
            node = queue.pop()
            counts += 1

            # 4. 인접한 모든 정점들에 대해,
            for next_node in graph[node]:
                # 5. 방문x 인접 정점으로 이동(큐에 append)
                if not visited[next_node]:
                    visited[next_node] = True
                    queue.append(next_node)

    counts = 0
    # 1. 시작 정점 방문 처리
    visited[1] = True
    bfs(1)
    return counts