4Legs_Archives

문제 링크 : www.acmicpc.net/problem/8452 8452번: 그래프와 쿼리 첫 번째 줄에 그래프의 정점, 간선의 수와 질의의 수를 나타내는 n, m, q 가 주어진다. (1 ≤ n ≤ 1, 000, 1 ≤ m ≤ 100, 000, 1 ≤ q ≤ 200, 000) 정점들은 순서대로 1부터 n까지 번호가 매겨져 있고, 간선들 www.acmicpc.net 문제 유형 BFS, Dijkstra, 오프라인 쿼리 오프라인 쿼리(Offline Query)란, 주어지는 쿼리들을 받는 즉시 처리하지 않고 모두 저장해둔 뒤 임의의 순서로 쿼리를 해결하는 기법을 말한다. 이 문제에서는 모든 쿼리를 다 받은 뒤, 쿼리를 역순으로 처리함으로써 문제를 간단화하여 해결할 수 있다. 즉, 원래의 U k 쿼리는 그래프..

문제 링크 : www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 삼성 SW 역량 테스트 기출문제이다. 이 문제도 전형적인 2차원 배열에서의 BFS 문제이지만, 단순 BFS로는 해결되지 않는 부분이 있다. 문제의 조건에서, 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 ..

문제 링크 : www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제를 봤을 때 BFS로 풀어야 하는 문제이구나! 하는 느낌은 바로 받을 수 있지만, 막상 문제를 해결하려고 하면 생각이 복잡해지는 문제이다. 출구를 향해 일단 가다가 잠긴 문을 만나면 목적지를 열쇠로 바꿔가면서 가는 방법을 제일 처음 생각해 볼 수 있다. 이 방법은 각 출구마다의 최단경로 path를 기억해 놓고, 통과해야 하는 문이 어떤 문들인지를 파악한 후에 가장..

문제 링크 : www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 �� www.acmicpc.net 다소 전형적인 2차원 배열에서의 BFS 응용 문제이다. 2차원 배열의 판(Board)에 로봇(말)이 있고, 목표 지점까지의 최소 거리 등을 구하는 유형의 문제이다. [BFS에 대해] BFS (Breadth-First Search, 너비 우선 탐색) [서론] BFS는 DFS와 더불어 그래프 탐색의 기본적인 알고리즘이다. DFS로 풀 수 있는 문제의 대부분은 BFS로 풀 수 있다. 갈 수 있는 모든 노드를..

[서론] BFS는 DFS와 더불어 그래프 탐색의 기본적인 알고리즘이다. DFS로 풀 수 있는 문제의 대부분은 BFS로 풀 수 있다. 갈 수 있는 모든 노드를 탐색하는 것은 결과적으로 같기 때문이다. 기본적인 정의와 동작 원리를 이해하고, 이차원 배열에서의 응용 문제들을 풀어보자. BFS (Breadth-First Search, 너비 우선 탐색) ■ 개념 그래프를 탐색할 때, 다음 level의 모든 노드를 먼저 방문하여 탐색하는 기법이다. 즉, 인접한 모든 노드를 우선으로 방문하여 탐색하는 방법이라 할 수 있다. ■ 동작 원리 1번 노드에서 출발하는 다음과 같은 그래프에서 BFS가 어떻게 작동하는지 살펴보자. - 1번 노드의 인접 노드인 2, 5, 7번 노드를 순서대로 방문한다. - 2번 노드의 자식 노드..