https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 그래프이론, 그래프탐색, 분리집합 설명 친구의 친구는 나에게도 친구이므로, 한 친구만 만들면 해당 친구가 속한 그룹은 모두 내 친구가 되므로, 그룹 당 친구비가 가장 적은 친구와 친구를 맺으면 됩니다. 접근방법 1. 분리집합 (유니온 - 파인드)를 사용해 각 친구관계를 그룹화한다. 2. 각 ..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 뿌요뿌요 게임 시뮬레이션입니다. 연결된 뿌요의 개수가 4개 이상일 경우 뿌요가 삭제되고, 중력의 영향으로 밑으로 내려온 뒤 4개 이상의 뿌요가 새롭게 생기면 연쇄적으로 해당 뿌요 역시 제거됩니다. 뿌요의 상태가 주어졌을 때, 총 몇 번이나 연쇄적으로 뿌요가 삭제되는지 구하는 ..

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/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프 이론, 그래프 탐색, 정수론, 너비 우선 탐색, 소수 판정, 에라토스테네스의 체 설명 한 번에 한 글자씩 수를 바꿀 수 있으며, 바꾼 숫자는 소수여야 합니다. 목표 숫자로 바꾸는 최소 횟수를 출력하는 문제입니다. 너비 우선 탐색(BFS)을 사용해 '숨바꼭질' 문제와 같이 최단 경로(최소 횟수)를 찾는 문제입니다. https://www.acmicpc.net/prob..

https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 난이도 : 골드 1 태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 창영이와 상근이가 차례로 막대기를 던져 미네랄을 파괴하는 문제입니다. 막대기는 수평으로만 날아가며, 미네랄이 파괴되면 해당 미네랄 클러스터를 내립니다. 접근방법 1. 막대기를 던진다. 첫 시작은 왼쪽 -> 오른쪽 이며, 번갈아가며 던진다 2. 막대기가 미네랄을 파괴했을 경우, 공중에 떠 있는 클러스터를 찾는다. 2..

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/4993 4993번: Red and Black There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles. Wr www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 전형적인 DFS/BFS로..

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/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 난이도 : 골드 4 태그 : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 뮤탈리스크가 SCV(1 ~ 3대)를 때리면 첫 타격때는 9, 둘째 타격때는 3, 셋째 타격에는 1을 줍니다. 이때 SCV를 모두 파괴시키는 최소 공격 횟수를 구하는 문제입니다. 음,,, 너비 우선 탐색으로 접근해야 할 것 같다는 느낌은 빠르게 왔는데, 어떻게 풀지 다소 난해했던 문제였습니다. SCV의 초기 ..