Algorithms/DFS & BFS 검색 결과

해당 글 23건

[BOJ 24445] 알고리즘 수업 - 너비 우선 탐색 2 (C++)

알고리즘 수업 - 너비 우선 탐색 2 (Silver 2) 문제 전체 문제 보기 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 풀이 정점의 개수 N개만큼 정점을 만들고 각 정점에서 인접한 노드들을 먼저 방문하는 BFS를 구현하여서 푸는 문제. 다만, 인접한 노드를 방문할 때 인접한 노드 인덱스의 내림차순으로 방문해야 하기 때문에 인접한 노드 인덱스 값을 내림차순으로 정렬하는 단계가 필요함. 코드 #include #include #inclu..
Algorithms/DFS & BFS 2022. 5. 14. 09:19

[BOJ 11559] Puyo Puyo (C++)

Puyo Puyo (Gold 5) 문제 전체 문제 보기 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 접근법 이번 문제는 BFS를 활용한 구현 문제입니다. BFS를 활용해서 현재 맵에 있는 뿌요를 탐색하여 4개 이상 모여있는 뿌요들은 모두 터트려주고, 빈 공간을 채워서 뿌요를 내리는 동작을 반복하여 문제를 해결할 수 있습니다. 전체 노드의 개수는 6 * 12로 작기 때문에 완전 탐색으로 계산하더라도 충분히 시간 내에 계산 가능합니다. 구현 메인 반복문 먼저 메인 반복문 로직은 다음과 ..
Algorithms/DFS & BFS 2021. 11. 21. 15:13

[BOJ 16234] 인구 이동 (C++)

인구 이동 (Gold 5) 문제 전체 문제 보기 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 접근법 이번 문제는 DFS/BFS를 활용한 구현, 시뮬레이션 문제입니다. 여기서는 BFS를 활용해서 풀이를 진행합니다. 먼저 매일 한 번씩 BFS탐색을 통해서 각 국가들의 인구수 차이를 확인하여 국경을 열어서 연합을 만들 수 있는지 확인 만들어진 연합의 평균 인구수 반환 BFS로 반환받은 연합의 평균 인구수를 활용하여 각 연합별 인구 이동 결과 반영 위 작업을 더이상 인구가 이동하지 않을 때까지 반복하..
Algorithms/DFS & BFS 2021. 10. 28. 14:04

[BOJ 1525] 퍼즐 (C++)

퍼즐(Gold 2) 문제 전체 문제 보기 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 접근법 퍼즐이 한 칸씩 움직이는 경우에 대해서 너비 우선 탐색을 진행하여 최소 거리를 구할 수 있는 문제입니다. 퍼즐의 모양을 저장하기 위해서 2차원 배열을 사용할 수 있지만 1~9까지 수를 9개 저장하고 비교하기 위해서 배열을 사용하는 것은 공간과 시간에 낭비가 발생합니다. 반면 000,000,000 ~ 999,999,999까지 사용할 수 있는 4바이트 int 타입 하나로 퍼즐을 나타내고 값을 비교한다면 9개의 정수 배열을 활용하는 것에 비해 사용하는 공간과 시간을 많이 절약할 수 있습니다. 3*..
Algorithms/DFS & BFS 2021. 10. 21. 12:21