반응형 너비우선탐색5 [C/C++] 백준 #2206 벽 부수고 이동하기(너비 우선 탐색) #2206은 평범한 너비 우선 탐색 문제는 아닙니다. 벽을 한번까지는 부실 수 있는 조건이 있기 때문에, 이에 대해서 처리를 해주어야 합니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 한번 이동하는데 항상 1이라는 가중치가 있는 그래프이기 때문에, 벽을 뚫고 갈 수 있다는 것을 원칙을 정해서 풀면 됩니다. 1) 벽을 한번 부수고 지나간 길은 음의 값으로 경로값을 적는다... 2023. 4. 16. [C/C++] 백준 #2178 미로 탐색(너비 우선 탐색) 미로 탐색은 대표적인 그래프 탐색과 관련되어 풀 수 있는 문제입니다. 길이 여러개이고, 움직일 때 비용이 똑같다고 한다면, 다익스트라와 같이 우선순위큐를 사용하는 알고리즘을 이용하지 않고, 너비 우선 탐색을 이용해도 됩니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 미로 탐색은 최단 경로를 찾아야 한다는 표현이 있지만, 고전적인 미로 탐색 문제입니다. 너비우선탐색 알고리즘을 이용하였습니다. 출발점에서부터 너비우선탐색을 하다가 도착지점에 도착하면.. 2023. 4. 13. [C/C++] 백준 #2146 다리 만들기(DFS, BFS) 이번 문제는 최단거리를 찾는 문제이긴 하지만, 이동하는데 드는 비용이 항상 같기 때문에 너비 우선 탐색을 사용하면 되는 문제입니다. 문제는 아래의 링크입니다. https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제를 풀 때에는 두 단계를 걸쳐서 풀었습니다. 일단 섬마다 고유한 아이디를 부여하기 위해서 깊이우선탐색(DFS)을 이용해서 고유 아이디를 붙였습니다. 다음으로는 모든 섬에 대해서 다리를 놓기 위한 최단 거리를 구하는 작업을 하였습니다. 이 .. 2023. 4. 10. [C/C++] 백준 #1963 소수 경로(너비 우선 탐색) 이번 문제는 소수중 한자리의 숫자만 다른 소수 경로를 찾는 문제입니다. 소수를 찾기 위해서 에라토스테네스의 체를 이용해도 되겠지만, 저는 미리 구한 4자리 소수 집합을 사용했습니다. 약간 편법일 수 있겠지만. 소수의 경로를 찾기 위해서 소수 후보를 찾는 것이 가장 힘듭니다. 일단 4자리 소수는 모두 홀수 소수이므로 갈 수 있는 경로는 31가지가 됩니다. 그것을 생각해서 한자리 숫자들을 바꾸면서 소수면 너비우선탐색 알고리즘으로 방문을 합니다. 그래서 목표하는 소수가 나오면 그때의 경로횟수가 답이 됩니다. 그런데, 모든 갈 수 있는 경로를 다 갔는데, 목표하는 소수가 나오지 않은 경우(queue가 비어있는 경우)에는 불가능하다고 출력을 내면 됩니다. 제가 작성한 소스입니다. //----------------.. 2022. 12. 9. #1525 퍼즐 우리는 4x4짜리 슬라이딩 퍼즐은 자주 갈지고 놀게 됩니다. 슬라이딩 퍼즐은 아래의 그림과 같이 생겼는데요. 비어있는 칸이 있고, 이 칸의 주변 상하좌우에서 숫자를 옮길 수 있습니다. 이번 문제는 4x4 슬라이딩 퍼즐이 아니고 3x3 슬라이딩 퍼즐입니다. 슬라이딩 퍼즐이 주어지면, 가장 빠르게 맞출 때 최소의 이동횟수를 푸는 것입니다. 불가능한 경우도 생깁니다. 이건 숫자가 있어야할 곳과 비어있는 칸의 위치로 원래 판단할 수 있습니다. 하지만, 그것을 이용해서 프로그램하지는 않았습니다. https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmi.. 2022. 9. 1. 이전 1 다음 728x90
