https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 울타리로 분리된 각 구역에 양과 늑대가 있습니다. 양이 더 많다면 늑대를 쫒아낼 수 있고 늑대가 더 많거나 양과 수가 동일하다면 늑대가 양을 다 먹어버립니다. DFS, BFS를 사용한 그룹화 기법을 응용하는 문제입니다. 접근방법 1. 한 점을 대상으로 방문하지 않은 점이라면 해당 점을 DF..
https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 난이도 : 골드 5 태그 : 구현, 시뮬레이션 설명 마법사 상어 시리즈 비바라기 편입니다. 구현 + 시뮬레이션 문제인 만큼 문제에서 주어진 내용을 그래도 구현하면 되는 문제입니다. 요구사항을 정리해보자면, 1. 모든 d(i) 방향으로 s(i) 칸 이동 2. 각 구름에서 비를 내린다 (구름이 있는 칸의 물의 양이 1 증가한다) 3. 물이 증가한 칸에 물복사버그 마법을 시전한다. 3-1. 물복..
코틀린으로 백준 풀기 1일 1코딩테스트를 한 지도 500일이 넘었네요. 아직 보잘 것 없는 실력이긴 하나, 그동안 백준을 풀며 얻은 팁들을 끄적여볼까 합니다. main() 함수의 매개변수는 생략 가능 fun main(args: Array) { } // main 함수 매개 변수는 생략 가능 fun main() { } 자바를 주로 써왔기에 public static void main(String[] args)과 같이 main 함수에 매개변수를 넣는게 익숙했고, 코틀린에서 클래스를 생성했을 때, main() 함수 내 args: Array이라는 매개변수를 자동으로 만들어주길래, 당연히 넣어줘야 하는 줄 알았으나... 사실 생략이 가능합니다. readln(), readLine()으로 입력받기 fun main() {..
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/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 시뮬레이션 설명 지렁이를 그냥 그려놓은 것 같지만, 잘 보다보면 규칙성을 찾을 수 있습니다. 0세대를 봅시다. → 방향입니다. 1세대 입니다. 0세대의 →를 90도 회전한 ↑ 방향입니다. 2세대입니다. 1세대는 →↑였습니다. ↑를 90도 회전하여 ←, →를 90도 회전하여 ↑가 되었습니다. 슬슬 규칙성이 보이시나요? 저는 한참을 계속 ..
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..