문제 14502번: 연구소 문제 설명 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으…

문제 2178번: 미로 탐색 문제 설명 크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 …

문제 17086번: 아기상어2 문제 설명 N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다. 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동…

다익스트라 알고리즘이란? 다익스트라 알고리즘은 하나의 시작 지점으로부터 모든 다른 지점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘 으로 분류된다. '매번 경로의 길이가 짧은 노드를 선택하는 과정'을 반복하기 때문이다. 다익스트라 알고리즘의 과정 시작 정점을 설정하고, 시작 정점의 거리 값을 0으로 설정한다. 시…

문제 그래프 - 순위 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매…

BFS에 대해 알아보기 전에 우선 그래프(graph), 큐(queue)에 대한 이해가 필요하다. 그래프에 대한 설명은 [자료구조] 그래프(Graph)란? , 큐에 대한 설명은 [자료구조] JavaScript로 구현하는 큐 에 자세히 정리해두었다. BFS란? BFS(Breadth First Search) 는 너비 우선 탐색이라고 하며 시작 노드로부터 가…

dfs에 대해 알아보기 전에 우선 그래프에 대한 이해가 필요하다. 그래프에 대한 설명은 여기 에 자세히 정리해두었다. DFS란? DFS(Depth-First-Search) 는 깊이 우선 탐색 이라고 하며 그래프에서 깊은 부분을 우선으로 탐색하는 알고리즘이다. DFS는 트리에서 생각하면 이해하기 쉽다(트리도 그래프의 일종이다). 트리를 탐색할 때 시작 …

그래프(Graph)란? 그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조로 실제 세계의 현상이나 사물을 정점(vertex) 과 간선(edge) 으로 표현한 것이다. 전기 소자를 그래프로 표현하게 되면 전기 회로의 소자들이 어떻게 연결되어 있는지를 표현해야 회로가 제대로 동작하는지 분석할 수 있으며, 운영 체제에서는 프로세스와 자원들이 어떻게…