본문 바로가기

BFS21

[백준][dfs] 2583 영역 구하기 c++ 구현 목차 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 문제 구현 방향 좌표라고 처음에 당황했는데 그냥 좌표값만큼 할당해주면 알아서 색칠된 도형을 표시할 수 있다. 또한 y좌표 기준이 아래부터 시작해서 당황했는데 회전해도 똑같기 때문에 그냥 넣어주면 된다. 물론 나는 Y좌표를 거꾸로 해서 올바르게 넣었다 ㅜ 코드 구현 #include #include #include #include using namespace std; i.. 2024. 4. 4.
[백준][bfs] 2468 안전 영역 c++ 구현 목차 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 문제 구현 방향 물에 잠기지 않는 영역을 세어주는 방식으로 구현했다. bfs를 여러번 돌리면 쉽게 풀리는 문제이다. 문제 구현시 주의점 빗물 높이가 0인 경우도 있다는 점을 주의해야 한다. 코드 구현 #include #include #include #include using namespace std; int dx[4] = { 0, 0, -1, 1 }; int dy[4] = { 1, -1, 0,.. 2024. 4. 2.
[백준][bfs] 10026 적록색약 c++ 구현 목차 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 문제 구현 방향 bfs탐색이 어짜피 O(N^2)이고 범위가 적어 시간을 생각하지 않고 전처리를 해주어 정상인일 때와 적록색약일때를 탐색 했다. 적록색약은 적색과 초록색을 같은 색으로 만들어 주고 탐색해주면 된다. 코드 구현 #include #include #include using namespace std; char board[101][101]; int visit[101][101.. 2024. 3. 22.
[백준][bfs] 1967 트리의 지름 c++ 구현 목차 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 문제 구현 방향 나는 리프 노드부터 bfs탐색을 시작하여 가중치를 더해준 후 그 중 가장 큰 가중치를 출력하는 방식으로 구현하였다. 가중치를 계속해서 누적해주는 것은 dp에서 착안하였다. 문제 풀이 시 주의할 점 그냥 인접행렬로 만들게 되면 메모리를 굉장히 많이 먹기 때문에 메모리 초과 오류에 빠진다. 따라서 구조체를 만들고 인접리스트를 사용하여 간선과 노드를 저장하.. 2024. 2. 24.
728x90

티스토리툴바