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

• 오늘은 코딩 테스트에서 꼭 알아야 하는 유형 중 하나인 'Graphs'에 대해 이야기해보려 합니다. 그래프 이론은 수학적 구조를 모델링하고 분석하는 데 널리 사용되는 도구로, 그래프 자체는 객체들 간의 쌍을 연결하는 선으로 구성된 추상 네트워크를 나타냅니다.

 

그래프란?

 

• 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 간선은 두 정점을 연결하며, 방향이 있는 경우와 없는 경우가 있습니다. 방향이 있는 그래프를 '방향 그래프(Directed Graph)', 방향이 없는 그래프를 '무방향 그래프(Undirected Graph)'라고 합니다.
• 그 외에도 가중치가 있는 그래프(Weighted Graph), 순환하는 경로가 없는 트리(Tree), 모든 정점들이 서로 연결된 완전 그래프(Complete Graph) 등 다양한 형태의 그래프가 있습니다.

 

그래프 이론 문제의 접근법

 

1. 문제 이해와 제약 사항 파악: 주어진 문제를 정확하게 이해하고, 입력 조건과 제약 사항을 파악해야 합니다.
2. 그래프 구현과 탐색: 주어진 문제에 맞게 그래프를 구현하고, 탐색 알고리즘을 활용하여 원하는 결과를 얻을 수 있습니다.
3. 너비 우선 탐색(BFS): 시작 정점에서 인접한 모든 정점들을 우선적으로 탐색하는 BFS 알고리즘을 사용할 수 있습니다.
4. 깊이 우선 탐색(DFS): 한 경로의 끝까지 탐색한 후 다른 경로로 되돌아가서 탐색하는 DFS 알고리즘을 사용할 수 있습니다.
5. 최단 경로 찾기: 최단 경로를 찾기 위해 다익스트라(Dijkstra) 알고리즘이나 벨만-포드 알고리즘 등을 활용할 수 있습니다. 이를 통해 시작 정점과 도착 정점 사이의 최단 경로를 찾을 수 있습니다.
6. 사이클 탐지: 그래프 내에 사이클이 존재하는지 여부를 판단하기 위해 사이클 탐지 알고리즘을 사용할 수 있습니다. 대표적인 알고리즘으로는 유니온-파인드(Union-Find) 알고리즘이 있습니다.
7. 최소 신장 트리(MST): 그래프 내의 모든 정점을 포함하면서 간선의 가중치 합이 최소가 되는 트리를 구하는 MST 알고리즘을 활용할 수 있습니다. 대표적인 알고리즘으로는 크루스칼(Kruskal) 알고리즘이나 프림(Prim) 알고리즘이 있습니다.
8. 위상 정렬: 방향 그래프에서 순서가 있는 작업들의 전체 순서를 구하는 위상 정렬 알고리즘을 사용할 수 있습니다.
9. 그래프 컷: 그래프에서 최소한의 간선을 제거하여 두 개 이상의 컴포넌트로 분할하는 그래프 컷 문제를 해결하기 위해 플로우(Ford-Fulkerson)나 이분 매칭(Bipartite Matching) 등의 기법을 사용할 수 있습니다.
10. 시간 복잡도 분석과 최적화: 그래프 문제에서는 주어진 입력 크기에 따라 시간 복잡도가 중요합니다. 따라서 어떤 알고리즘을 선택하느냐와 최적화 기법에 따라 성능 개선 여부가 결정됩니다.

 

4963번: 섬의 개수

  문제  

 

• 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

• 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
• 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

 

  해결 방법  
 

• 이 문제는 섬의 개수를 구하는 문제로, 그래프에서 연결 요소의 개수를 찾는 문제와 같습니다. 
• 여기서는 DFS(깊이 우선 탐색) 알고리즘을 사용하여 각 노드를 방문하며 연결된 섬을 찾아냅니다. 이 때 각 노드가 바로 이웃한 노드만 아니라 대각선 방향에 있는 노드와도 연결되어 있으므로, 총 8개의 방향을 확인하며 탐색합니다.

from sys import stdin
import sys; sys.setrecursionlimit(10000)

dx = [0, 0, -1, -1, -1, 1, 1, 1]
dy = [-1, 1, 0, -1, 1, 0, -1, 1]

def dfs(x,y):
    visited[x][y] = True
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < h) and (0 <= ny < w):
            if array[nx][ny] == 1 and visited[nx][ny] == False:
                dfs(nx, ny)

while True:
    w, h = map(int,input().split())
    if w == h == 0:
        break
    array = [list(map(int,input().split())) for _ in range(h)]
    visited = [[False] * w for _ in range(h)]
    result = 0
    
    for i in range(h):
        for j in range(w):
            if array[i][j] == 1 and visited[i][j] == False:
                dfs(i, j)
                result += 1
    print(result)

• 이 문제는 섬의 개수를 구하는 문제로, 그래프에서 연결 요소의 개수를 찾는 문제와 같습니다. 여기서는 DFS(깊이 우선 탐색) 알고리즘을 사용하여 각 노드를 방문하며 연결된 섬을 찾아냅니다.
• DFS 알고리즘이란, 현재 노드에서 방문할 수 있는 노드가 있으면 재귀적으로 계속 방문하는 알고리즘입니다. 만약 더 이상 방문할 곳이 없다면 이전에 방문한 노드로 돌아가 다른 경로를 탐색합니다.
• 8방향에 대해 DFS를 진행하면서, 이미 방문한 곳은 다시 가지 않도록 visited 배열을 사용해 체크합니다. 그래프의 모든 점에 대해 DFS를 수행하며, 새롭게 DFS가 시작될 때마다 섬의 개수를 1씩 증가시킵니다. DFS에 대한 더 자세한 내용은 추후 포스팅에서 찾아뵙겠습니다.

 

7562번: 나이트의 이동

  문제  

 

• 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

from collections import deque

dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

def bfs(sx,sy):
    q=deque()
    q.append((sx,sy))
    graph[sx][sy]=0
    while q:
        x, y = q.popleft()
        if x == ex and y == ey:
            print(graph[ex][ey])
            return
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and ny >= 0 and nx < l and ny < l:
                if graph[nx][ny] == -1:
                    q.append((nx,ny))
                    graph[nx][ny]=graph[x][y]+1

t = int(input())
for _ in range(t):
    l = int(input())
    sx, sy = map(int,input().split())
    ex, ey = map(int,input().split())
    
    graph = [[-1] * l for _ in range(l)]
    
    bfs(sx, sy)

• 이 문제는 나이트의 최소 이동 횟수를 구하는 문제로 그래프에서 최단 거리를 찾는 문제와 같습니다. 여기서 BFS(너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있습니다.
• BFS 알고리즘은 시작점에서 가까운 순서대로 그래프의 모든 정점들을 탐색합니다. 큐(Queue) 자료구조를 사용하여 아직 방문하지 않은 정점들을 차례대로 방문하게 됩니다.
• 나이트의 이동 가능한 8가지 방향에 대해 BFS를 진행하면서, 이미 방문한 곳은 다시 가지 않도록 graph 배열을 사용해 체크합니다. BFS는 시작 노드에서 각 노드까지의 최단 거리를 구하는데 효과적이므로, 도착 지점에 도달했을 때의 거리가 곧 최소 이동 횟수가 됩니다. BFS에 관한 내용은 추후 포스팅에서 추가적으로 다루도록 하겠습니다.

 

• 그래프 이론은 네트워크 구조를 모델링하는 데 매우 유용하며, 코딩 테스트에서도 자주 출제되는 주제 중 하나입니다. 그래프 문제를 해결하기 위해서는 그래프의 기본 개념과 다양한 그래프 탐색 알고리즘을 잘 이해하고 있어야 합니다.
• 특히 DFS와 BFS는 가장 기본적이면서도 중요한 그래프 탐색 알고리즘이므로, 반드시 숙지해야 합니다. 또한 문제 상황에 따라 적절한 알고리즘을 선택할 수 있는 능력도 필요합니다.