백준 검색 결과

해당 글 78건

[BOJ 7569번] (DFS/BFS) 토마토 (C++)

토마토 (Silver 1) 문제 전체 문제 보기 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 접근법 이 문제는 BFS 탐색을 통해서 상자에 들어있는 모든 토마토가 익을 때까지 걸리는 시간을 계산해야 하는 문제이다. 일반적인 BFS와 가장 큰 차이점은 탐색을 시작하는 지점이 1개 이상이 될 수 있다는 점이다. 기본적인 DFS/BFS 구현에 대한 이해가 필요하다면 이 글을 참고하자. 아래의 그림은 일반적인 BFS의 탐색이다. 하지만 이 문제에서는 익은 토마토가 여러 개 일 수 있기 때문..
Algorithms/DFS & BFS 2021. 5. 18. 15:41

[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