devlog

문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작�� www.acmicpc.net 해설 조금 까다로운 백트래킹 문제 입니다. 문제를 살펴보면 문제에서 주어진 조건은 다음과 같습니다. 1. 총 7명의 학생들로 구성되어야 하며 2. S가 항상 4개 이상인 조합으로 구성되어야 한다, 반대로 Y는 항상 3개 이하여야 한다. 3. 강한 결속력을 위해 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다. 이렇게 보면 일반적인 DFS, 백 트래킹 문제라고 볼 수 있지만 이 문..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 해설 일반적인 BFS 완전탐색을 이용한 시뮬레이션 문제 입니다. 이 문제를 해결하는 핵심 키워드는 바로 문제의 조건에 있습니다..

문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 해설 다리만들기 문제는 BFS와 MST 을 만드는 알고리즘을 이용해서 문제를 해결 할 수 있습니다. MST를 만드는 알고리즘에 대한 설명은 다음 블로그 링크를 참조해주세요. 문제는 크게 두 부분으로 나뉘어 집니다. 1. 바다를 제외한 연결된 영역을 같은 섬 영역으로 표시하고 각 섬마다 구분 지어 주기 2. 각 섬에서 다른 섬까지 이어지는 경로 찾기 1번의 경우 일반적인 ..