Twinparadox Factory

깊이 우선 탐색과 너비 우선 탐색에 대해 간단하게 비교하여 정리하고자 한다. 두 알고리즘은 생각보다 알고리즘 문제 풀이에서 많이 볼 수 있고, 각각의 응용 방식을 통해 나오는 코딩 테스트 문제가 많기 때문에 참고해두는 것이 좋고, 기본적인 구현 방식은 알고 접근하는 것이 좋다. 기본적인 구현 코드는 백준 온라인 저지의 1260번 DFS와 BFS 을 구현하는 코드이다. DFS(Depth-First Search) Stack으로 구현할 수 있고, 함수 호출도 Stack처럼 이뤄지기 때문에 대부분 재귀 함수로 구현된 코드들이 많다. DFS는 미로 찾기로 치면, 막히는 곳까지 계속 파고 드는 Leaf-wise한 방식이다. 분기점이 나오면 길 하나를 선택하고 더 이상 진행하지 못하는 시점까지 진행한다고 보면 이해하..

시간 제한 : 1초메모리 제한 : 128MB 입력첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. 출력첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다. 소스코드#include #include #include #include usin..

시간 제한 : 1초메모리 제한 : 128MB 입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.입력의 마지막 줄에는 0이 두 개 주어진다. 출력각 테스트 케이스에 대해서, 섬의 개수를 출력한다. 소스코드#include #include using namespace std; int dir[8][2] = { {1,0}, {0,1}, {-1,0}, {0,-1}, {1,1}, {1,-1}, {-1,1}, {-1,-1} }; int island, w, h; vector board; vector visit; void dfs(int..

시간 제한 : 1초메모리 제한 : 256MB 입력첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다. 출력첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다. 소스코드 #include #include usi..