스파이더맨: No Way Home 개봉이 얼마 남지 않았다. 스파이더맨의 거미줄과 옷을 보면 거미줄의 모양이 vertice와 edge로 이루어진 Graph와 비슷해 Graph Algorithm이 생각난다.
때문에 그래프 알고리즘에 대해 알아볼 것이다.

Graph란?

그래프(Graph)

그래프라 하면 일반적으로 '정점(노드)'과 '간선(엣지)'으로 이루어진 자료구조를 의미한다.
또한 간선의 방향 유무에 따라서 단방향 그래프와 무방향 그래프(또는 양방향)로 나뉜다.

그래프의 탐색 기법

그래프의 탐색 기법에는 BFS, DFS, 다익스트라, 크루스칼 등등 많은 탐색 기법들이 있다.
그 중 BFS와 DFS가가장 대표적이고 알고리즘 문제로 많이 나오는 자료구조다.

BFS

BFS(Breadth-First Search) 즉 너비 우선 탐색이라고 불린다.

• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다.
  이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.

Baekjoon 2178: 미로 탐색

Solution

import sys

N, M = map(int, sys.stdin.readline().split())
# matrix 배열
matrix = [sys.stdin.readline().rstrip() for _ in range(N)]
# 방문경로 배열
visited = [[0]*M for _ in range(N)]
# 좌/우/위/아래 방향 이동
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

# BFS 경로 탐색
# queue 방식 사용
queue = [(0,0)]
visited[0][0] = 1

while queue:
    x, y = queue.pop(0)

    if x == N-1 and y == M-1:
        # 최종 경로 도착
        print(visited[x][y])
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            if visited[nx][ny] == 0 and matrix[nx][ny] == '1':
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx,ny))

• BFS 방식 사용을 위해서 기본 미로의 배열 matrix와 방문을 확인하는 visited배열을 만든다.
• 주변 노드 확인을 배열에서는 해당 좌표의 연결된 좌표들을 확인하는 것과 동일하다. 즉, 좌/우/위/아래 좌표가 연결된 노드라고 생각하고 문제를 풀어나가면 된다.
• 좌표가 경로를 벗어나지 않는 범위 내에서 1. 방문여부 확인, 2. 길이 맞는지 확인한다.
• 조건에 맞다면 방문여부 수정 후, 큐에 넣어서 다음 차례에 추가한다.
• 방문 여부를 확인할 때, 방문 여부에 몇 번째 방문인지를 적어 넣는다. 이후 해당 좌표가 되면 몇 번째, 방문인지를 출력하면 된다.

DFS는 다음 게시물에서 설명하겠다.