너비 우선 탐색

문제https://www.acmicpc.net/problem/7562풀이너비 우선 탐색 간단한 BFS 문제로 기존 문제와 다른 점은 목적지에 도착할 때까지 걸린 count가 필요하다. bool 배열로 해당 칸의 방문 여부를 판별하는 것보다 int 배열로 해당 칸에 도착할 때까지 걸린 count를 기록한다. 방문 여부는 해당 칸의 count가 0인지를 확인하면 된다. 코드#include #include #include #include using namespace std;int T;int I;// visited 배열이 아닌 int로 count와 방문 여부를 동시 관리int moveCount[300][300];int moveX[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };int moveY[..

문제 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 구현, 시뮬레이션, 너비 우선 탐색 판의 가장자리 부터 bfs를 실시하여 치즈가 있는 칸을 0으로 설정하여 치즈가 모두 녹을 때까지 진행하면 된다. 칸의 가장자리는 에는 치즈가 놓여있지 않기 때문에, (0, 0)에서 bfs를 시작해도 무방하다. 루프를 돌면서 만나는 치즈를 바로 0으로 만들면 해당 칸이 현재 루프에 영향을 미치므로 다음 루프에서의 판을 나타내는 next_board배열을 만들어서 next_board에 해당 칸을 0으로 설정한다. // 다음 칸이 ..

문제 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 그래프 탐색, 너비 우선 탐색 간단한 너비 우선 탐색 문제로, 8방향만 주의하면 된다. 지도의 (0, 0)부터 탐색을 시도하며, 현재 타일이 방문하지 않은 섬이라면 해당 타일부터 너비 우선 탐색을 실시한다. 상하좌우 대각 8방향에서 방문하지 않은 섬이 있다면 방문하고 이를 반복한다. 탐색이 종료되면 시작한 타일이 포함된 섬을 하나 방문한 것으로 섬의 개수가 1 증가한다. 코드 #include #include using namespace std; ..

문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 구현, 시뮬레이션, 너비 우선 탐색 각 칸에 대해서 연합을 이룰 수 있는지 확인하기 위해, 각 칸의 상하좌우를 탐색하여 연합을 만든다. 연합은 시작 칸과 인접한 칸에서만 이루어지는게 아니라, 연합이 이루어진 칸에서도 인접한 칸을 비교하여 조건에 맞으면 연합이 이루어진다. 그러므로 각 칸을 bfs로 탐색하면서 연합을 이루는 칸이 어느 칸인지 탐색한다. 연합 벡터의 수가 2이상이라면, 인구 이동이 가능한 상태이므로 인구 이동을 실시한다. 이를..

문제 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 브루트포스 알고리즘, 너비 우선 탐색, 조합론, 백트래킹 학생은 전체 25명이다. 여기서 자리를 7개 선택하여 문제의 조건이 맞는지 확인하는 방식으로 답을 구한다. 학생의 수가 많지 않기 때문에 브루트포스로 구현해도 시간 초과는 발생하지 않는다. 자리를 선택하는 방법은 백트래킹을 사용한다. 자리 선택과 해제를 반복하며 자리를 7개 선택했다면 현재 상태가 문제의 조건을 만족하는지 확인한다. 문제의 조건은 다음과 같다. 선택한 자리 모두 상하좌우로 연결되어 ..

문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 조합론, 너비 우선 탐색, 깊이 우선 탐색, 브루트포스 알고리즘 주어진 선거구에서 임의로 몇 개를 선택하여 A구역으로 설정하고, 선택하지 않은 구역은 B구역으로 설정한다. N이 최대 10이므로 모든 경우의 수를 비교해도 시간 초과는 발생하지 않는다. 선거구를 선택할 때는 깊이 우선 탐색의 방식으로 1번 선거구를 선택하고 계산한 다음, 다시 해제하는 방식으로 진행한다. 선택한 선거구가 문제의 조건을 만족하는지 확인해야 한다. 구역은 2개로 나뉘어져야 하므로, 선택한 선거구가 ..

문제 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘, 너비 우선 탐색 다른 K칸에 최단 거리로 이동하려면, 최단 거리에 있는 S나 K칸에서 로봇을 복제해서 최단 거리로 이동해야 한다. 즉, S와 K칸을 하나의 노드로 취급하여 다른 S와 K칸 과의 간선을 설정하고, 해당 간선으로 최소 스패닝 트리를 이루면 로봇의 최소 이동 거리를 구할 수 있다. 여기서 각 노드의 거리를 구해야 한다. 현재 칸마다 가중치가 없고 각 칸사이의 거리는 1이므..

문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 너비 우선 탐색, 구현, 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 문제의 2차원 배열에서 각 섬은 너비 우선 탐색으로 섬의 수와 위치를 파악할 수 있다. 배열에 섬의 위치와 섬의 번호를 설정하였다면, 섬과 섬 사이의 간선의 길이를 파악해야 한다. 섬의 모든 점에서 부터 상하좌우로 움직이며 다른 섬에 도달하였을 경우 거리를 파악하여 간선으로 vector에 넣는다. 점의 수가 최대 100이므로 시간초과는 발생하지 않는다. 해당 ..

문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 [백준][C++] 1261: 알고스팟 문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의 kantatatam.tistory.com 너비 우선 탐색 문제로, 위의 문제와 풀이가 동일하다. 하나 주의해야 할 점은, 시작 지점의 거리가 0이 아니고, 시작 지점의 도둑 루피..

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 너비 우선 탐색 문제이다. 다익스트라로 시도를 했을 때, 메모리초과와 시간초과가 발생하여 너비 우선 탐색으로 변경하였다. 미로의 각 칸을 하나의 노드로 생각하고, (0, 0)칸부터 탐색한다. 현재 노드의 상하좌우를 탐색한다. 탐색하는 노드까지의 거리는 현재 노드까지의 거리에서 벽이 있다면 +1 없다면 +0이다. 탐색하는 노드의 거리를 갱신할 수 있다면 갱신하고, 큐에 넣는다. 거리를 나타내는 배열이 2차원 배열임을 주목하자. 코드..