작심 24/7

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 기본적인 로직은 상, 하, 좌, 우를 탐색하여 이전 봉우리보다 낮은 경우 → 한 칸 더 갈 수 있다. 이전 봉우리보다 높거나 같은 경우 → 현재 봉우리의 높이를 1~K 만큼 깎아서 (이전 봉우리 높이 - 1) 로 만들 수 있는지 판단. →만들 수 있으면 한 칸 더 갈 수 있다. 이때, 깎을 수 있는 기회는 한 번뿐이므로 깎았다고 표시를 해줘야 한다. 이렇게 가장 긴 길이를 찾는 문제이므로 DFS로 풀면 되지만 굳이 굳이 BFS로 접근해서 방문 체크 때문에 머리 아팠다. DFS는 깊이 우선 탐색이기 때문에 방문 배열 한 개 가지고 재귀 호출을 통해 체크했다가 지웠다..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 최단 거리를 구하는 문제이므로 BFS를 쓰는 게 적합하다. 일단 큐에는 x, y좌표 뿐만 아니라 현재까지의 이동 횟수, 이전에 벽을 부쉈는지의 여부 도 저장해주어야 한다. 벽을 한 번만 부술 수 있기 때문에 이전에 벽을 부순 적이 있으면 그 루트는 앞으로 벽을 뚫고 지나가지 못 한다. 그리고 방문 체크를 해줄 때 벽을 한 번 부순 경우와 벽을 부수지 않은 경우 두 가지로 나누어서 체크해주어야 하기 때문에 3차원 배열 visited를 사용..

17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 궁수 3명을 배치시키는 경우는 M개 중 3개를 순서 상관없이 뽑는 조합으로 구하면 된다. 궁수가 (5, 2)에 있을 때 공격할 수 있는 위치에 따른 거리들을 표시해 보았다. 궁수가 공격할 수 있는 거리는 궁수 위치에서부터 좌, 상, 우 방향으로 BFS 했을 때의 깊이와 같다는 것을 알 수 있다. 공격할 수 있는 적은 거리가 D 이하인 적 중에서 가장 가까운 적이고 그런 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격해야 하므로 깊이 1부터 탐색해야 하고 방향은 왼쪽, 위쪽..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net BFS를 이용하여 상어 크기와 같은 물고기가 있거나 빈칸인 공간으로 이동하면서 상어 크기보다 작은 물고기를 발견하면 우선순위 큐에 BFS의 깊이(걸린 시간), x좌표, y좌표를 넣어준다. 탐색을 다 마치고 돌아와 우선순위 큐가 비어있으면 먹을 수 있는 물고기가 없는 것이므로 종료 후 최종 시간 출력, 비어있지 않으면 큐 안에서 1. 깊이(걸린 시간)가 가장 작은 순서대로 2. x좌표가 가장 위에 있는 순서대로 3. y좌표가 가장 왼쪽에 있는 순서대로 오..

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 프로그래머스 지형 이동과 비슷한 문제이다. 1. BFS로 섬의 번호를 매겨준다. 2. 섬과 섬 사이의 거리의 최솟값을 그래프에 저장한다. 1) 가로 방향 다리 모든 행을 검사하면서 A섬 끝→B섬 시작 일 때가 다리를 놓는 경우이므로 파란색 화살표일 경우에만 그래프에 저장한다. 이때 거리는 1보다 커야 하고 A섬→B섬에 이미 거리가 저장되어 있으면 그 거리와 현재 거리를 비교하여 더 작은 값을 넣어준다. 2) 세로 방향 다리 모든 열을 검사하는..

17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 두 선거구로 나눌 때 각 선거구 안에 있는 영역들은 모두 연결되어 있는 상태여야 한다. 그러므로 두 선거구로 나눌 수 없는 경우는 연결되어 있는 그룹이 세 개 이상일 때이므로 이 경우를 가려주기 위해 먼저 BFS로 연결된 그룹이 몇 개인지 세어준다. 3개 이상일 경우 -> -1 출력 2개일 경우 -> 두 그룹이 각각 선거구이므로 이때 인구의 차 출력 1개일 경우 -> 모두 연결된 상태이므로 다음 단계 넘어감 두 선거구로 나누는 방법은 N개 중에서 K개를 순서 상관없이 뽑는 조합으로 구..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net BFS, 완전 탐색 문제이다. 무조건 3개의 벽을 세워야 하므로 빈칸 n개 중 3개를 순서 상관없이 고르는 조합으로 구현하고 큐로 구현한 BFS로 바이러스의 개수를 구한 뒤 안전 영역의 개수 = 빈칸 개수 - 바이러스의 개수 - 3 의 최댓값을 출력해주면 된다. #include #include #include #include using namespace std; int N, M, cnt, res, x, y, tmp; int arr[8][8], dx[4] ..

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 연산 횟수를 1씩 증가해주며 현재 횟수로 만들 수 있는 숫자들을 모두 임시 큐에 넣어주고 메인 큐가 empty할 때까지 반복한 뒤 빠져나오면 임시 큐의 값들을 전부 메인 큐에 넣어준다. 연산 횟수가 K가 되면 빠져나와 최댓값을 출력해주는데 최댓값의 default를 -1로 해주면 연산을 K번 할 수 없는 경우엔 최댓값이 변하지 않아 문제에서 바라는 대로 -1을 출력할 수 있다. ex) 숫자는 10이고 K는 1일 때 이때 주의할 점은 방문 체크하는 부분이다. 현재 메인 큐를 다 비우고 나면 다음 메인 큐에서 할 연산은 현재 메인 큐와 ..