꼭 알아야하는 코딩 테스트 유형: 8) #Graph_Traversal

• 이번에는 코딩 테스트에서 중요한 유형인 'Graph Traversal(그래프 탐색)'에 대해 알아보겠습니다. 그래프 탐색은 그래프의 모든 노드를 방문하는 과정을 의미합니다. 그래프는 여러 개의 노드(Node)와 간선(Edge)으로 구성되어 있으며, 실제로 많은 문제들이 그래프 형태로 모델링됩니다.

 

그래프 탐색의 개념

 

• 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조로, 다양한 현실 세계의 문제를 모델링하기 위해 사용됩니다. 그래프 탐색은 주어진 그래프에서 모든 정점을 방문하거나 특정한 조건을 만족하는 정점을 찾기 위해 사용됩니다.
• 주요한 그래프 탐색 알고리즘과 관련된 개념들을 소개하겠습니다.

 

1. 깊이 우선 탐색(Depth-First Search, DFS): 한 정점에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완전하게 탐색하는 방식입니다. 스택(Stack)이나 재귀 함수를 활용하여 구현할 수 있습니다.
2. 너비 우선 탐색(Breadth-First Search, BFS): 한 정점에서 시작하여 인접한 모든 정점들을 먼저 방문하는 방식입니다. 큐(Queue)를 활용하여 구현할 수 있습니다.
3. 최단 경로(Shortest Path): 출발지와 도착지 사이의 가장 짧은 경로를 찾는 문제입니다. 대표적인 최단 경로 알고리즘으로는 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드-워셜(Floyd-Warshall) 등이 있습니다.

 

코딩 테스트에서 그래프 탐색 문제의 접근법

 

• 그래프 탐색은 코딩 테스트에서 다양한 문제 유형에 활용되며, 문제 해결에 필요한 알고리즘 선택과 구현 능력이 요구됩니다. 아래는 코딩 테스트에서 그래프 탐색 문제를 해결하기 위한 일반적인 접근 방법입니다.

 

1. 그래프 구조 이해: 주어진 문제의 요구사항 그래프의 구조와 특성을 파악해야 합니다. 그래프의 정점과 간선의 개수, 방향성 여부, 가중치 등을 확인하여 문제에 적합한 그래프 탐색 알고리즘을 선택할 수 있습니다.
2. 깊이 우선 탐색 (DFS) 활용: DFS는 스택(Stack)이나 재귀 함수를 사용하여 구현할 수 있습니다. 주어진 문제에 맞게 시작 정점과 목표 정점, 방문 순서 등을 고려하여 DFS를 활용해 문제를 해결할 수 있습니다.
3. 너비 우선 탐색 (BFS) 활용: BFS는 큐(Queue)를 사용하여 구현할 수 있습니다. 시작 정점에서 인접한 모든 정점들을 먼저 방문하며 너비 우선으로 탐색하는 특성을 이용하여 문제를 해결할 수 있습니다.
4. 최단 경로 알고리즘 활용: 최단 경로 문제인 경우 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드-워셜(Floyd-Warshall) 등의 알고리즘을 사용하여 해결합니다. 각 알고리즘의 동작 원리와 시간 복잡도를 이해하고 적합한 알고리즘을 선택하세요.
5. 백트래킹(Backtracking): 그래프에서 모든 가능한 경로나 조합을 찾아야 할 때 백트래킹 기법을 활용합니다. DFS와 결합하여 사용되며, 유효한 조건에 따라 탐색하다가 유효하지 않은 상태면 되돌아가는(backtrack) 방식입니다.

• 예시로 관련된 접근 방법을 살펴보겠습니다.

 

최단 경로 찾기

 

• 주어진 가중치(weighted) 혹은 비가중치(unweighted)가 있는 그래프에서 최단 경로를 찾는 문제는 그래프 탐색에서 자주 등장하는 유형 중 하나입니다. 주어진 그래프에서 시작 노드부터 목적지 노드까지의 최단 경로를 찾는 것이 목표입니다.
• 가중치가 없는(unweighted) 그래프의 경우, 너비 우선 탐색(BFS)을 사용하여 최단 경로를 찾을 수 있습니다. BFS는 시작 노드로부터 한 단계씩 넓혀가며 탐색하는 방식으로, 각 단계마다 이전 단계와 연결된 모든 노드들을 방문합니다. 이때, 목적지 노드에 도달하면 탐색을 종료하고 최단 경로를 구할 수 있습니다.

from collections import deque

def bfs(graph, start, destination):
    visited = set()  # 이미 방문한 노드를 저장하기 위한 집합
    queue = deque([(start, [])])  # 큐에 (노드, 경로) 형태의 튜플을 저장
    
    while queue:
        node, path = queue.popleft()
        
        if node == destination:
            return path + [node]  # 목적지에 도착한 경우 경로 반환
        
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                queue.append((neighbor, path + [node]))
    
    return []  # 도착할 수 없는 경우 빈 리스트 반환

 

• 위 코드에서 graph는 인접 리스트 형태의 그래프를 나타내며, start와 destination은 각각 시작 노드와 목적지 노드입니다. BFS 함수는 큐와 집합(visited)을 활용하여 너비 우선 탐색을 수행하고 결과인 최단 경로를 반환합니다.
• 만약 가중치가 있는(weighted) 그래프라면 다익스트라(Dijkstra) 알고리즘이나 벨만-포드(Bellman-Ford) 알고리즘과 같은 다른 알고리즘들을 사용하여 최단 경로를 찾아야 합니다. 이러한 알고리즘들은 각 간선의 가중치 정보도 함께 고려하여 최적의 해결책을 제공합니다.

 

2644번: 촌수계산

  문제  
 

• 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 
• 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
• 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

 

  해결 방법  
 

• 이 문제는 두 사람의 촌수를 계산하는 문제로, 그래프 상에서 두 노드 간의 최단 거리를 구하는 문제입니다. 
• BFS를 사용하여 시작 노드에서부터 뻗어나가며 촌수를 계산할 수 있습니다. 방문하지 않은 이웃 노드를 방문하면서, 큐에 추가하고 촌수를 갱신합니다.

from collections import deque
import sys; input=sys.stdin.readline

def bfs(graph, start, end):
    visited = [-1] * (len(graph) + 1)
    visited[start] = 0
    q = deque([start])

    while q:
        cur = q.popleft()
        for neighbor in graph[cur]:
            if visited[neighbor] == -1:
                visited[neighbor] = visited[cur] + 1
                q.append(neighbor)
    return visited[end]

n = int(input())
a, b = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

print(bfs(graph, a, b))

 

1707번: 이분 그래프

  문제  
 

• 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
• 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

 

  해결 방법  
 

• 이 문제는 그래프가 이분 그래프인지 판별하는 문제입니다.
• 이분 그래프란, 그래프의 모든 정점을 두 집합으로 분할할 때 같은 집합에 속한 정점끼리는 서로 인접하지 않은 그래프를 의미합니다. 이 경우에는 너비 우선 탐색(BFS)를 사용하여 그래프의 정점을 가장 멀리 떨어진 노드부터 확인하면서 집합을 나누어 가며 판별할 수 있습니다.
• BFS를 사용해서 이분 그래프인지 판별하는 `bfs` 함수를 정의합니다. 이분 그래프를 판별하기 위해 각 노드를 두 가지 색깔(1과 -1, 여기선 colors 리스트에 저장)로 구분하는데, 인접한 노드끼리는 서로 다른 색깔로 칠해야 합니다. 따라서 현재 노드와 인접한 노드가 같은 색깔이면 이분 그래프가 아닌 것으로 판별할 수 있습니다.
• 각 테스트 케이스에 대해 그래프를 입력받고, 그래프의 노드 수만큼 반복문을 돌며 아직 색칠되지 않은 노드가 있다면 그 노드를 시작으로 BFS를 실행합니다. 만약 그 과정에서 이분 그래프가 아닌 경우에는 반복문을 빠져나오고, 이분 그래프 판별 결과를 출력합니다.

from collections import deque
import sys; input=sys.stdin.readline

def bfs(graph, start, colors):
    colors[start] = 1
    q = deque([start])

    while q:
        cur = q.popleft()
        for neighbor in graph[cur]:
            if colors[neighbor] == 0:
                colors[neighbor] = -1 * colors[cur]
                q.append(neighbor)
            elif colors[neighbor] == colors[cur]:
                return False
    return True

for _ in range(int(input())):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    colors = [0] * (v+1)
    is_bipartite = True
  
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    for i in range(1, v+1):
        if colors[i] == 0:
            if not bfs(graph, i, colors):
                is_bipartite = False
                break

    print('YES' if is_bipartite else 'NO')

 

• 이처럼 그래프 탐색은 다양한 알고리즘과 함께 사용하여 문제를 해결하는 기본적인 도구입니다.
• 그래프 탐색 문제를 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)를 사용하여 효과적으로 해결하는 전략을 익히고, 다양한 문제에 실제로 적용해보면 도움이 될 것입니다.