목록너비우선탐색 (7)
전자공학 및 알고리즘
백준 4991 - 로봇 청소기(C++)
문제 링크입니다. https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 비트마스킹과 BFS를 이용해 풀 수 있는 문제입니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #define S second using namespace std; int N, M; char map[21][21]; int check[..
백준 16947 - 서울 지하철 2호선(C++)
문제 링크입니다. https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 순환되는 그래프를 찾을 수 있는지를 물어보는 문제였습니다. DFS와 BFS를 함께 써야했던 문제입니다. 그래프가 양방향으로 주어집니다. 주어진 그래프는 순환하는 지점이 만들어지는데, 해당 지점에 속하지 않은 정점과 순환하는 곳과의 거리를 구하는 문제입니다. 그렇다면, 2가지를 구해야하는데 1. 순환하는 지점을 구해야한다. 2. 속하지 않는 지점과 순환하..
백준 1068 - 트리(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 그래프 탐색을 이용하는 문제입니다. 노드를 하나 지웠을 때, 리프 노드를 구하는 문제입니다. 시작 노드를 찾은 뒤, 시작 노드에서 그래프 탐색을 시작해줍니다. 탐색 노드와 연결된 노드 중, 연결되지 않는 노드로 이동해 다음 노드로 계속 이동해줍니다. 더 이상 이동할 수 없는 노드로 도착하면, 리프 노드 갯수를 1 증가해줍니다. 여기서, 지워진 노드가 연결되어 있어도 이동할 ..
백준 12869 - 뮤탈리스크(C++)
문제 링크입니다. https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net Dp로 풀 수 있지만, BFS로 푸는게 더 간단해 보여 약간의 노다가를 추가한 BFS로 풀었습니다. 3개의 SCV가 각각 9 or 3 or 1의 값이 빼집니다. 따라서 모든 경우를 확인한 뒤, 전부 0이 된 최소 횟수를 출력해주면 됐습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #inclu..
백준 12886 - 돌 그룹(C++)
문제 링크입니다. https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net BFS를 이용해 푸는 문제입니다. BFS를 짜는 것 자체는 간단했습니다. 돌이 A, B, C가 존재하니 옮길 수 있는 경우는 3가지입니다. 1. A 와 B 2. A 와 C 3. B 와 C 각 경우에서도 X가 큰 경우, Y가 큰 경우가 있으니 총 6가지 경우만 확인하면 됐습니다. 방문했던 돌의 크기를 확인하는 방법은 3차원 배열을 이용해 [A][B][C]로 저장하면 편하겠지만..
백준 17471 - 게리맨더링(C++)
문제 링크입니다. https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 백트래킹과 BFS를 이용한 문제였습니다. N개의 정점이 주어질 때, 이들을 적절하게 나눠 인구수 차이를 가장 적게 만드는 문제였습니다. 해당 문제를 풀려면 구햔해야 하는 것들이 있습니다. 1. 선거구를 나누는 방법 2. 나뉜 선거구가 연결되는 지 확인 3. 선거구의 인구차를 확인 이와 같이 3개를 구현하면 풀 수 있었습니다. 먼저 1번부터 확인해보겠습니다. 1. 선거구를 나누는 방법 인구수를 최소로 ..
백준 18404 - 현명한 나이트(C++)
문제 링크입니다. https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net BFS를 이용해 푸는 문제입니다. 일반적인 상하좌우 4방향 탐색이 아닌, 나이트 이동인 8방향으로 탐색하는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF ..