Algorithms/DFS & BFS 검색 결과

해당 글 23건

[BOJ 1167] 트리의 지름(C++)

트리의 지름(Gold 3) 문제 전체 문제 보기 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 접근법 이 문제는 BFS/DFS를 두 번 탐색하여 풀 수 있다. 아래의 그림을 보자. 위와 같은 트리가 주어졌을 경우 트리의 지름은 아래와 같이 노드 5에서 출발해서 노드 7로 연결하는 길이인 24이다. 이문제를 풀기 위해서 생각해볼 점은 "임의의 노드에서 가장 멀리 떨어진 노드는 반드시 '노드 5' 혹은 '노드 7'이다."라는 점이다. 임의의 노드에서 탐색을 진행하여 그 노드와 가장 멀리 떨어져 ..
Algorithms/DFS & BFS 2021. 9. 3. 12:04

[BOJ 1043] 거짓말 (C++)

거짓말 (Gold 4) 문제 전체 문제 보기 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 접근법 이 문제에서 진실을 모르는 사람들만 있는 파티의 수를 구해야 한다. 이 문제에서 진실은 같은 파티에 참석한 사람들에게 전파되는 특징이 있다. 파티의 참석자를 노드, 파티의 참석 정보를 인접 노드에 대한 정보, 진실이 전파되는 특징을 인접 노드 탐색으로 본다면 BFS로 풀 수 있는 문제이다. 자료구조 선택 BFS 알고리즘을 활용하여 문제를 풀어본다. BFS로 풀이하기 위하여 다음과 같은 노드를 정의할 수 있다. BFS에서는..
Algorithms/DFS & BFS 2021. 9. 2. 08:31

[BOJ 1707] (DFS/BFS) 이분 그래프 (C++)

이분 그래프(Gold 4) 문제 전체 문제 보기 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 접근법 문제를 읽고 이분 그래프가 무엇인지 감이 오지 않는다면 이 글을 참고하자. 위키백과: 이분 그래프. 이 글에 따르면 이분 그래프는 다음과 같은 특징을 가진다. 모든 노드는 빨간색 혹은 파랑색을 가지며, 한 노드의 인접한 노드는 서로 다른 색상을 가져야 한다. 우리는 이 특징을 활용하여 다음과 같이 BFS로 문제를 풀 수 있다. 한 번도 방문하지 않은 노드는 색상을 가지지 않는다. 처음 노드를 파..
Algorithms/DFS & BFS 2021. 8. 23. 22:03

[BOJ 7562] (DFS/BFS) 나이트의 이동 (C++)

나이트의 이동 (Silver 2) 문제 전체 문제 보기 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 접근법 이 문제에서는 나이트가 목표지점까지 이동하기 위한 최단거리를 구하는 문제이다. 최단거리 문제는 BFS로 풀 수 있다. 나이트 특유의 2*1 이동 방식에 유의해서 인접 노드를 잘 설정하면 쉽게 풀 수 있는 문제이다. 필자는 dx,dy 배열을 사용하여 나이트의 이동을 표현하였다. array dx{ -2, -1, 1, 2, 2, 1, -1, -2 }; array dy{ 1, 2, 2, 1, -1, -2, -..
Algorithms/DFS & BFS 2021. 8. 23. 18:06