Algorithm

https://www.acmicpc.net/problem/1707 문제 분석이 문제는 노드와 간선으로 이루어진 그래프를 입력 받아 해당 그래프가 이분 그래프인지 판별을 하여 이분 그래프가 되면 YES를 아니면 NO를 출력하는 문제이다. 우선 주어진 데이터를 보면 간선에 방향이 없기 때문에 무방향 그래프로 만들어야 하는 것을 알 수 있다. 또한 이분 그래프 판별을 위한 DFS를 하기 위해서 필요한 방문 여부 배열, 이분 그래프 판별 용 변수 등을 만들어야 한다. 그리고 여기서 중요한게 이분 그래프를 정확히 이해하는 것이다. 이분 그래프에 대한 자세한 내용은 검색을 하는 것으로 대체하고 간단히 설명을 하면 하나의 간선마다 연결된 두개의 노드가 서로 다른 집합에 속하고 이 조건을 모든 간선이 통과하면 이분 그..

문제 설명 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 내용은 위 갈음하고 간단하게 설명만 하자면 상하좌우로 1이 이어져서 만들어진 집합이 몇개인지 찾아보라는 것이다. 즉 밭의 모든 구역에 배추를 심었으면 1이 상하좌우로 모두 이어져 있으므로 답은 1개가 될 것이고, 만약 대각선으로 배추가 심어져있으면 상하좌우에는 배추가 없으므로 배추의 총 개수가 답이 될 것이다. 문제 풀이 이 문제는 전형적인 DFS, BFS문제이다. 필자는 DFS로 문제를 풀이..

BFS(Breadth-First Search)란? BFS란 넓이 우선 탐색이란 뜻으로 그래프 탐색의 일종이다. 흔히들 그래프 탐색이라 하면 DFS와 BFS 두개가 있는데 DFS와 다른 점은 다음에 방문할 노드를 정할때 주변에 있는 노드가 우선이라는 점이다. 보통 그래프에서 최단 경로를 찾을때 가장 많이 사용된다. BFS의 특징 BFS는 스택의 구조를 가지는 DFS와 달리 FIFO 탐색으로 구현된다. 위와 같은 이유로 사용되는 자료구조 역시 stack이 아닌 queue를 사용한다. 시간 복잡도는 DFS와 같은 O(V+E)를 가진다. 재귀적으로 동작하지 않는다. 즉 검색 속도에 있어서 이점을 가질수 있다. BFS의 원리 BFS 시작 노드 정하고 자료구조 초기화 BFS도 DFS와 마찬가지로 방문했던 노드는 다..

DFS(Depth-First Search)란? DFS란 그래프 탐색 기법 중 하나이다. 말 그대로 시작 노드에서 부터 한 쪽으로 탐색을 시작하면 그 방향에 있는 모든 노드들을 방문하고 다른 방향의 노드들을 탐색하는 기법이다. DFS의 특징 및 사용법 DFS 특징 DFS는 보통 재귀함수로 구현되며 탐색하고자 하는 그래프의 규모에 따라서 시간 복잡도가 달라지게 됩니다. DFS의 시간 복잡도는 O(V+E)(V=노드 수, E=간선 수)로 표현 됩니다. DFS는 한번 방문한 노드들을 다시 방문해서는 안되므로 노드 방문 여부를 체크할 수 있는 배열이나 리스트를 가지고 있습니다. 다른 그래프 탐색 기법인 BFS에 비해 구현이 단순하다는 장점이 있지만 그만큼 검색 속도에 있어서는 뒤쳐집니다. DFS 사용법 및 사용문제..