본문 바로가기

그래프 이론15

[백준/C,C++] 2667번: 단지번호붙이기 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 hackids.tistory.com/76 [백준/C,C++] 2178번: 미로 탐색 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicp.. hackids.tistory.com 2178번: 미로 탐색에서 발.. 2021. 4. 20.
[백준/C,C++] 2178번: 미로 탐색 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 간단한 BFS 문제입니다. 이동 가능한 방향은 최대 4방향(상, 하, 좌, 우)이며, BFS로 0을 제외한 모든 노드에 대해 깊이를 계산해 준 후에 (N, M)의 깊이를 출력해 주면 됩니다. 유의해야 할 점은 모든 노드에서 4방향(상, 하, 좌, 우)으로 이동할 수 있는 것은 아니기에 해당 방향으로 갈 수 있는지, 해당 방향의 노드가 갈 수 있는 지점(1이면 가능, 0이면 불가능)인지 체크하고, 방문했던 곳인지를 체크해주면 됩니다. #i.. 2021. 4. 20.
[백준/C,C++] 1260번: DFS와 BFS www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 구현하는 문제입니다. DFS와 BFS의 개념과 구현 방법은 생략하고, 현재 정점에서 여러 정점을 방문할 수 있을 때, 정점 번호가 작은 것을 먼저 방문해야 하므로, 그래프를 오름차순으로 정렬만 해주면 됩니다. #include #include #include #include #include using namespace.. 2021. 4. 20.

티스토리툴바