https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 연구소에 바이러스가 퍼졌습니다. 바이러스가 퍼지기 전에 다행이도 벽을 3개 세울 수 있을 때, 벽을 적절히 배치하여 안전구역(바이러스가 퍼지지 않는 구역)을 최대화하는 문제입니다. 주어지는 바이러스는 1개 이상이기 때문에, 초기 큐에 바이러스의 위치를 모두 넣어놓고 BFS를 돌려 여러 위치에서 바이러스를..

https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 연구소1이 벽을 세워 안전지대의 최대 크기를 구하는 문제였다면, 연구소2는 모든 칸에 바이러스를 퍼뜨리는 가장 빠른 시간을 구하는 문제입니다. 연구소 1, 3과 마찬가지로 DFS를 사용해 조합을 구하고, 해당 조합으로 바이러스를 퍼뜨리는(BFS 사용) 시뮬레이션을 진행합니다. 소스코드 입력 lateinit..

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 다들 한 번쯤은 해봤을 법한 디펜스 게임을 구현하는 문제네요. 궁수의 위치를 선택해야 했기 때문에 백트래킹을 사용한 수열 구하기를 사용해야하나? 싶었는데, 생각해보니 궁수는 3명으로 고정되어 있으므로, 굳이 백트래킹을 사용하지 않아도 3중 for문으로 간단히 가능합니다. 또, 가장 가까운 ..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 보물의 위치는 한 섬에서 서로 가장 먼 두 점에 있습니다. 최단경로가 아닌, 최장 경로를 찾는 문제인 셈이지요. 어떻게 구해야 하나 싶었는데, 가로, 세로의 길이가 각각 50이하인 것을 보고, 브루트포스적으로 접근하여 육지의 모든 점에서 BFS를 돌려 해당 점에서 가장 먼 점을 찾은 뒤, 가장 먼 점을..

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 난이도 : 실버 3 태그 : 구현, 브루트포스 설명 어릴때 많이 해봤던 숫자야구 게임입니다. 프로그래밍 언어를 처음 배울 때 구현 능력 향상 예제로도 많이 접하곤 하죠. 이번 문제는 특이하게도, 숫자와 해당 숫자의 strike, ball이 주어졌을 때, 가능한 정답의 개수를 출력하면 됩니다. 그냥 간단하게, 123부터 시작하여 987 까지(중복이 허용되지 않으므로), 숫자, strike, ball..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 조합론, 깊이 우선 탐색 설명 위와 같이, 하나의 시를 2개의 선거구로 나누려 합니다. 선거구의 각 구역은 모두 직/간접적으로 이어져 있어야 하며,이때 두 선거구 간의 인원 수의 차이가 최소가 되어야 합니다. n이 2 !selected[index] }.sum() // 선거구2 인구 수 answer = minOf(ans..

https://www.acmicpc.net/problem/17106 17106번: 빙고 한 줄에 5개의 글자, 총 5줄을 출력한다. 각 줄은 순서대로 빙고판의 각 행을 나타낸다. 색칠된 칸은 "#", 색칠되지 않은 칸은 "."로 따옴표 없이 나타낸다. 예를 들어 A1, C3, C4만 색칠하려면 다음과 www.acmicpc.net 난이도 : 플래티넘 5 태그 : 구현, 브루트포스 설명 위 빙고를 풀면 되는 문제입니다. 코드없이 풀 수도 있을 것 같긴 한데, 저는 풀다가 지쳐서 결국 코드를 돌려 해결했습니다... 25개의 각 칸이 색칠되어있는 경우와 색칠되어있지 않은 경우, 총 2 ^ 25 개의 경우의 수에서 각각의 칸이 모순이 되는지 판단하면 됩니다. 애매한 칸은 B5인데, 해당 칸이 거짓이라 해도 문제의..

https://www.acmicpc.net/problem/25585 25585번: 86 ─에이티식스─ 1 첫 번째 줄에 전장의 크기 $N$이 주어진다. 전장은 $N \times N$ 크기 좌표로 이루어져 있다. 다음 $N$개의 줄에는 전장의 정보가 주어진다. 각 줄마다 $N$개의 좌표 정보가 주어지며 0은 빈칸, 1은 레기 www.acmicpc.net 난이도 : 골드 5 태그 : 백트래킹, 브루트포스 설명 대각선으로만 이동할 수 있는 장기말로, 다른 적들을 다 잡을 수 있는지, 잡을 수 있다면 얼마만큼의 시간이 소요되는지 구하는 문제입니다. 처음엔 n이 꽤 작길래, 대각선 방향으로 이동하는 모든 경우의 수를 다 확인하였으나, 당연하게도 시간초과. n이 최대 100이여도 n이 1 만큼 증가할때마다 말도안..

https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 난이도 : 골드 2 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 3차원 큐브를 탈출하는 문제입니다. 한 층씩 좌우로 층을 회전할 수 있고, 한 층씩 마음대로 쌓을 수 있기 때문에, 각 층을 회전하여 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS) 1번, 각 층을 쌓아 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 난이도 : 실버 2 태그 : 브루트포스, 백트래킹 설명 배열의 순서를 적절히 섞어 위 식의 최댓값을 찾는 문제였습니다. 처음에는 위 식을 |A[0] - A[1]| + |A[2] - A[3]| 과 같이 두 식의 차이의 절대값 인줄 알고 그리디로 접근하면 되겠지? 싶었는데 |A[0] - A[1]| + |A[1] - A[2]| 였습니다 ㅎㅎ; 😭 흠... 그럼 두 번째 방법으로, 백트래킹으로 모든 경우의 수를 탐색하..