Algorithms 검색 결과

해당 글 123건

[BOJ 1012번] (DFS/BFS) 유기농 배추 (C++)

유기농 배추 (Silver 2) 문제 전체 문제 보기 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 접근법 배추의 위치정보를 가지는 2차원 Node* 배열을 DFS/BFS 탐색을 통해서 풀 수 있는 문제이다. 가로 세로의 크기가 다르기 때문에 2중 반복문 등을 통해서 데이터를 입력할 때 헷갈리지 않도록 유의하며 구현하자. 기본적인 DFS / BFS 구현에 대한 이해가 필요하다면 이 글을 참고하자. 자료구조 선택 기본 자료구조로 활용할 Node를 아래와 같이 선언한다. struct Node { Node() : mNum(0..
Algorithms/DFS & BFS 2021. 5. 17. 16:46

[BOJ 2667번] (DFS/BFS) 단지번호붙이기 (C++)

단지번호붙이기 (Silver 1) 문제 전체 문제 보기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 접근법 이 문제의 데이터 형식은 2차원 배열 형식으로 주어진다. 더 정확하게 따지면 문자열의 배열로 주어지고 있다. 입력 데이터인 0 또는 1이 같은 행일 경우 구분자 없이 입력되기 때문이다. 때문에 이 문제에서는 특별히 문자열을 파싱 하여 각 2차원 배열 노드에 값을 입력하는 부분이 추가로 구현되어야 한다. 데이터가 입력된 노드들에 인접 노드를 설정해주고 BFS 혹은 DFS를 사용하여 풀 수 있는 문제이다...
Algorithms/DFS & BFS 2021. 5. 17. 11:24

[BOJ 2606번] (DFS/BFS) 바이러스 (C++)

바이러스 (Silver 3) 문제 전체 문제 보기 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 접근법 컴퓨터를 노드, 컴퓨터 쌍이 연결된 네트워크를 간선으로 자료구조를 구성한 후 BFS 혹은 DFS로 풀 수 있는 간단한 문제이다. 필자는 BFS로 풀었다. 문제에서 구하려고 하는 값은 1번 컴퓨터로 인해서 감염된 컴퓨터의 수이다 (1번 컴퓨터는 감염된 컴퓨터 수 에서 제외해야 함). 그래서 카운트 변수를 하나 만들어서 1번 노드를 제외한 다른 노드를 방문할 때 카운트 변수를 하나씩 증가시켜주고, 이를 출력한다. ..
Algorithms/DFS & BFS 2021. 5. 16. 22:01

[BOJ 1260번](DFS/BFS) DFS와 BFS (C++)

DFS와 BFS (실버 II) 문제 전체 문제 보기 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 접근법 이 문제는 DFS / BFS 유형의 입문 문제이다. 주어진 도시와 간선 정보를 바탕으로 모든 도시를 DFS로 한번 출력하고 BFS로 한번 출력하는 문제이다. 때문에 가장 정석의 DFS와 BFS를 각각 구현하면 된다. 바로 구현을 시작한다. 주의사항 필자는 처음 코드를 제출 했을 때 87% 에서 런타임 에러가 발생했었다. 이유는 출발 노드에 간선이 연결되어 있지 않은 ..
Algorithms/DFS & BFS 2021. 5. 16. 21:05