이번에 풀어볼 문제는 빙산 문제이다. 시간이 지나면서 입력으로 주어진 빙산이 녹아가는데, 빙산이 처음으로 분리되는 시간을 구하는 문제이다. 문제의 조건은 아래와 같다. 빙산이 상하좌우로 맞닿아 있는 바닷물의 칸수만큼 녹는다. 빙산이 차지하는 칸의 개수는 최대 10,000개이다. 배열의 첫 번째 행과 마지막 행, 첫 번째 열과 마지막 열에는 빙산이 존재하지 않는다. 빙산의 높이는 최대 10이다. 기본적인 탐색 문제이다. 먼저 바닷물과 맞닿아 있는 빙산들을 녹이고 나서, 아직 녹지 않은 빙산을 기준으로 탐색을 진행하여 연결된 빙산들을 모두 방문처리 해주는 방식이다. 이렇게 탐색이 한 번 진행된 이후에도 아직 방문하지 않은 빙산이 존재한다면, 빙산이 둘 이상으로 갈라지게 된 것이므로 탐색을 종료한다. 다만 이..
위상 정렬(Topology Sort)이란? 위상 정렬이란 DAG에서 정점을 선형으로 정렬한 것이다. 이때 간선의 정보가 u -> v 형식으로 주어진다면, 위상 정렬의 결과는 항상 정점 u가 정점 v보다 앞에 오게 된다. DAG(Directed Acyclic Graph) DAG는 비순환 방향 그래프를 의미하며, 사이클이 없고 간선에 방향이 존재하는 그래프를 의미한다. DAG가 아닌 그래프, 즉 간선에 방향이 없거나 사이클이 존재하는 그래프에 대해서는 위상 정렬이 불가능하다. 위상 정렬을 활용하는 적절한 예시로 대학교 선수 과목을 들 수 있다. 다음 그림과 함께 살펴보자. 위와 같이 선수 과목들이 정해져 있을 때, 자연어처리와 데이터베이스 시스템 과목을 수강하기 위해서 먼저 들어야 하는 과목을 순서대로 나열..
이번 포스팅의 주제는 최단 경로 알고리즘이다. 그래프 상에서 특정 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘인데, 대표적인 알고리즘으로 오늘 알아볼 다익스트라 알고리즘과, 추후 포스팅 할 예정인 플로이드-워셜 알고리즘, 벨만-포드 알고리즘이 있다. 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 그리디 알고리즘의 한 형태이다. 알고리즘의 진행 과정은 아래와 같다. 초기 distance table의 값을 모두 INF 값으로 설정해 주고, 시작 노드의 값만 0으로 설정한다. 현재 distance table에서 아직 방문하지 않았으며, 남은 경로 중 가장 경로가 짧은 노드에 대해서 검사를 진행한다.(초기의 경우 시작 노드) 현재 노드와 인접한 노드들을 검사한다. 현재 노드까지의 최단 경로..
