[TIL] 99클럽 코테 스터디 8일차 TIL - 그래프이론(BFS/DFS): <백준 2644 촌수계산 > 문제 풀이 with python

Today's keyword : 그래프 이론 (BFS/DFS)

 

📌 문제설명

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

 

 

📌 문제풀이

주어진 두 노드 간의 촌수를 계산하는 문제로, 노드 간의 연결 관계를 그래프로 표현하고, 두 노드 간의 최단 경로를 찾는 것이 목표입니다. 이 문제에서 주의해야 할 점은 그래프가 비어 있거나 연결되지 않은 경우를 처리해야 합니다. 이 경우 -1을 출력해야 합니다. 

BFS 

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)  # 재귀 깊이 제한 설정

n = int(input())
start, end = map(int, input().split())
m = int(input())

# 그래프 초기화
graph = [[] for _ in range(n + 1)]  

# m개의 간선 정보 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # a에서 b로의 간선 추가
    graph[b].append(a)  # b에서 a로의 간선 추가 (양방향)

def bfs(graph, start, end):
    visited = [False] * (n + 1)
    queue = deque([start])
    distance = [0] * (n + 1)  # 각 노드까지의 거리 초기화

    visited[start] = True

    while queue:
        current = queue.popleft()

        if current == end:
            return distance[current]  # end에 도달하면 거리 반환

        for neighbor in graph[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                distance[neighbor] = distance[current] + 1  # 거리 업데이트
                queue.append(neighbor)

    return -1  # 연결되지 않은 경우 -1 반환

answer = bfs(graph, start, end)
print(answer)

1. 큐 사용: BFS는 큐를 사용하여 구현합니다. deque를 사용하여 효율적으로 큐를 관리합니다.
2. 방문 배열: visited 배열을 사용하여 각 노드의 방문 여부를 기록합니다.
3. 거리 배열: distance 배열을 사용하여 각 노드까지의 거리를 기록합니다. 시작 노드에서부터의 거리를 계산합니다.
4. 노드 탐색: 큐에서 노드를 꺼내고, 그 노드의 이웃 노드를 탐색합니다. 이웃 노드가 방문되지 않았다면 큐에 추가하고 거리를 업데이트합니다.
5. 결과 반환: end 노드에 도달하면 그 거리를 반환하고, 모든 노드를 탐색한 후에도 도달하지 못한 경우 -1을 반환합니다.

 

DFS - backtracking 방식

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 깊이 제한 설정

n = int(input())
start, end = map(int, input().split())
m = int(input())

# 그래프 초기화
graph = [[] for _ in range(n + 1)]  

# m개의 간선 정보 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # a에서 b로의 간선 추가
    graph[b].append(a)  # b에서 a로의 간선 추가 (양방향)

visited = [0] * (n + 1)
count = 0

def dfs(graph, v, visited):
    global count 
    visited[v] = count
    count += 1
    if v == end: 
        return visited[v]

    for i in graph[v]: 
        if visited[i] == 0: 
            result = dfs(graph, i, visited)
            if result is not None:  # 결과가 None이 아닐 경우
                return result
            
    count -= 1  # backtrack 시 count 감소
    return None  # 연결되지 않은 경우 None 반환

answer = dfs(graph, start, visited)
if answer is not None: 
    print(answer)
else: 
    print(-1)

1. 입력 처리:

• n: 노드의 수를 입력받습니다.
• start, end: 촌수를 계산할 시작 노드와 끝 노드를 입력받습니다.
• m: 간선의 수를 입력받습니다.
• graph: 인접 리스트 형태로 그래프를 초기화합니다.

2. 그래프 초기화

• graph = [[] for _ in range(n + 1)]: 각 노드에 대한 빈 리스트를 생성하여 그래프를 초기화합니다. 인덱스 0은 사용하지 않기 위해 n + 1 크기로 설정합니다.

3. 간선 정보 입력

• for _ in range(m): m개의 간선 정보를 입력받아 그래프에 추가합니다. 각 간선은 양방향이므로, 두 노드 간의 연결을 양쪽 모두에 추가합니다.

4. DFS 함수 정의:

• def dfs(graph, v, visited): DFS를 수행하는 함수입니다.
• global count: 전역 변수 count를 사용하여 현재 노드까지의 거리를 추적합니다.
• visited[v] = count: 현재 노드를 방문하고, 그 노드까지의 거리를 기록합니다.
• count += 1: 다음 노드를 방문하기 위해 count를 증가시킵니다.
• if v == end: 현재 노드가 목표 노드인 경우, 그 거리를 반환합니다.
• for i in graph[v]: 현재 노드의 이웃 노드를 탐색합니다.
• if visited[i] == 0: 이웃 노드가 방문되지 않은 경우, 재귀적으로 DFS를 호출합니다.
• count -= 1: 백트래킹 시 count를 감소시켜 이전 상태로 되돌립니다.
• return None: 연결되지 않은 경우 None을 반환합니다.

5. 결과 출력:

• answer = dfs(graph, start, visited): DFS를 호출하여 결과를 저장합니다.
• if answer is not None: 결과가 None이 아닐 경우, 즉 두 노드가 연결되어 있으면 그 거리를 출력하고, 연결되어 있지 않으면 -1을 출력합니다.

DFS - distance 인수 사용 

import sys

sys.setrecursionlimit(10 ** 6)  # 재귀 깊이 제한 설정

n = int(input())
start, end = map(int, input().split())
m = int(input())

# 그래프 초기화
graph = [[] for _ in range(n + 1)]  

# m개의 간선 정보 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # a에서 b로의 간선 추가
    graph[b].append(a)  # b에서 a로의 간선 추가 (양방향)

def dfs(graph, v, visited, distance):
    visited[v] = True
    if v == end:
        return distance  # end에 도달하면 거리 반환

    for neighbor in graph[v]:
        if not visited[neighbor]:
            result = dfs(graph, neighbor, visited, distance + 1)
            if result is not None:  # end에 도달한 경우
                return result

    return None  # 연결되지 않은 경우 None 반환

visited = [False] * (n + 1)
answer = dfs(graph, start, visited, 0)
print(answer if answer is not None else -1)

1. 재귀적 탐색: DFS는 재귀를 사용하여 그래프를 탐색합니다. 현재 노드를 방문하고, 그 노드의 이웃 노드를 재귀적으로 방문합니다.
2. 방문 배열: visited 배열을 사용하여 각 노드의 방문 여부를 기록합니다.
3. 거리 인수: distance 인수를 사용하여 현재 노드까지의 거리를 추적합니다. distance는 매 호출 시 1씩 증가합니다.
4. 결과 반환: end 노드에 도달하면 그 거리를 반환하고, 모든 노드를 탐색한 후에도 도달하지 못한 경우 None을 반환합니다.

📌 오늘의 회고 

초반에 bfs로 탐색하다가 잘 되지 않아 dfs로 탐색하고, dfs에서 distance인수 받는걸 생각 못해서 count를 더하는 방식으로 힘들게 풀었다. 문제를 역시 많이 풀어봐야 한다.  

 

 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL