https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 연구소에 바이러스가 퍼졌습니다. 바이러스가 퍼지기 전에 다행이도 벽을 3개 세울 수 있을 때, 벽을 적절히 배치하여 안전구역(바이러스가 퍼지지 않는 구역)을 최대화하는 문제입니다. 주어지는 바이러스는 1개 이상이기 때문에, 초기 큐에 바이러스의 위치를 모두 넣어놓고 BFS를 돌려 여러 위치에서 바이러스를..
https://www.acmicpc.net/problem/1385 1385번: 벌집 첫째 줄에는 당신이 있는 방의 번호 a와 출구가 있는 방의 번호 b가 주어진다.1 ≤ a, b ≤ 1,000,000) www.acmicpc.net 난이도 : 플래티넘 5 태그 : 구현, 그래프이론, 그래프탐색, 너비우선탐색 설명 벌집(2292)에 비해 꽤나 매운맛인 벌집 문제 입니다. 위와 같이 생긴 벌집을 대상으로 최단거리를 찾는 BFS을 돌려 풀 수 있겠다는 생각은 빨리 들었으나, 벌집의 모양을 그래프로 나타내는 것에 상당히 어려움을 느꼈습니다. 벌집을 그래프로 나타내라! 그래프는 위와 같이 벌집을 약간 회전시켜 2차원 배열 형태로 나타낼 수 있습니다. 예를 들어 500 * 500 사이즈 배열의 경우, (250, 25..
https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 난이도 : 골드 5 태그 : 구현, 시뮬레이션 설명 마법사 상어 시리즈 비바라기 편입니다. 구현 + 시뮬레이션 문제인 만큼 문제에서 주어진 내용을 그래도 구현하면 되는 문제입니다. 요구사항을 정리해보자면, 1. 모든 d(i) 방향으로 s(i) 칸 이동 2. 각 구름에서 비를 내린다 (구름이 있는 칸의 물의 양이 1 증가한다) 3. 물이 증가한 칸에 물복사버그 마법을 시전한다. 3-1. 물복..
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/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/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/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 난이도 : 골드 5 태그 : 구현, 시뮬레이션 설명 2차원 블록 세계에 비가 왔을 때, 빗물이 고여있는 양을 구하는 문제입니다. 해당 문제의 경우, 각각의 블록을 기준으로 하여 (왼쪽 블럭 중 가장 큰 값, 오른쪽 블록 중 가장 작은 값) 중 가장 작은 값을 구한 뒤, 기준이 되는 블록의 높이만큼 빼주면 해당 블록에 채워지는 물의 양을 구할 수 있습니다. 빨간색 화살표로 가르키고..
https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 난이도 : 실버 3 태그 : 구현, 브루트포스 설명 어릴때 많이 해봤던 숫자야구 게임입니다. 프로그래밍 언어를 처음 배울 때 구현 능력 향상 예제로도 많이 접하곤 하죠. 이번 문제는 특이하게도, 숫자와 해당 숫자의 strike, ball이 주어졌을 때, 가능한 정답의 개수를 출력하면 됩니다. 그냥 간단하게, 123부터 시작하여 987 까지(중복이 허용되지 않으므로), 숫자, strike, ball..