목록그래프 (168)

1일1알

백준 16948번 데스 나이트 C++

일반적인 bfs탐색 문제이다. 좌표 변화를 담고있는 배열을 이용해서 깔끔하게 푼 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; struct Knight { Knight(int row, int col, int moveCount) :row(row), col(col), moveCount(moveCount) {} int row; int col; int moveCount; }; int main() { ios_base::sync_with_stdio(false); cin..
알고리즘 2021. 11. 19. 12:26
백준 6118번 숨바꼭질 C++

bfs탐색을 이용하여 해결할 수 있는 문제이다. 2차원 벡터로 그래프를 나타내고 노드와 거리를 저장하도록 pair 를 이용하고 found벡터와 함께 bfs탐색을 하면서 문제를 해결하였다. 탐색을 하다가 거리가 갱신되면 답을 갱신하고 cnt를 0으로 초기화 해주고, 만약 거리가 같다면 기존 답과 비교해서 새로 찾은 헛간의 번호가 더 작다면 갱신해주고, cnt를 1 늘려주었다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; int main() { ios_..
알고리즘 2021. 11. 18. 12:16
백준 2589번 보물섬 C++

BST 탐색으로 해결할 수 있는 문제이다. 지도의 모든 부분을 검사하면서 만약 L인 지역이면 그곳부터 BST탐색을 시작하고, 가장 먼 곳 까지의 거리를 구하고 구한 거리들 중 가장 큰 값을 찾으면 해결할 수 있다. 땅을 방문했는지 안했는지 검사하는 visited 벡터를 만들었고, 새로 검사를 시작할 때는 visited 벡터를 초기화 해주었다. 그리고 BST탐색을 하기 위한 큐에는 pair을 사용해서 안쪽에 있는 pair는 좌표 정보를, int는 거리 정보를 저장하면서 탐색을 하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using na..
알고리즘 2021. 11. 11. 12:30
백준 12852번 1로 만들기 2 C++

bfs탐색으로 풀 수 있는 문제인데 숫자 n이 1이 되기까지의 숫자들의 정보를 저장해야 하는 문제이다. 우선 최솟값은 bfs탐색을 하면서 쉽게 구할 수 있고, 자신의 이전 값을 저장하는 parent 배열을 만들었다. bfs탐색을 진행하면서 자신의 이전 값을 parent 배열에 저장하고, 숫자가 1이 되면 1부터 parent 배열을 통해 값이 n이 될 때까지 역추적? 하면서 값을 하나씩 저장한다. 저장된 정보를 역순으로 출력하면 n에서 1이 되는 과정의 숫자들이 출력된다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long..
알고리즘 2021. 11. 3. 00:25
백준 1926번 그림 C++

단순한 그래프 탐색 문제이다. 가로 세로로 이어진 그림의 개수와 그림 중에서 넓이가 가장 큰 값을 구하면 된다. bfs와 dfs 모두 사용할 수 있다. 나는 bfs방식을 이용해서 해결하였다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; void Input(vector& v, int n, int m) { for (int i = 0; i > v[i][j]; } } } pair bfs(vector& v, int n, in..
알고리즘 2021. 11. 2. 11:52
백준 10164번 격자상의 경로 C++

직사각형의 경로에서 동그라미가 주어지면 그 곳을 거쳐서 오른쪽 밑 끝까지 가고, 주어지지 않으면 그냥 오른쪽 밑 끝까지 가는 경우의 수를 구하는 문제이다. 동그라미의 좌표가 주어지지 않으면 (0, 0)에서 (n-1, m-1) 까지의 경우의 수를 구하고 동그라미의 좌표가 (x, y)라고 주어지면 (0, 0)에서 (x, y) 경우의 수와 (x, y,)에서 (n-1, m-1)까지의 경우의 수를 곱하면 된다. 동그라미는 좌표가 아닌 숫자로 주어지기 때문에 좌표로 변환해야 한다. 숫자가 k로 주어지면 ( (k - 1) / m , (k - 1) % m ) 의 식을 통해 좌표를 구할 수 있다. bfs방식을 통해서 경우의 수를 구하였다. #include #include #include #include #include ..
알고리즘 2021. 11. 1. 12:57
이전 Prev 1 ··· 24 25 26 27 28 Next 다음