Twinparadox Factory

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

제한사항 2초, 512MB 입력 첫 번째 줄에는 현수막의 크기인 M와 N가 주어진다. (1 ≤ M, N ≤ 250) 두 번째 줄부터 M+1 번째 줄까지 현수막의 정보가 1과 0으로 주어지며, 1과 0을 제외한 입력은 주어지지 않는다. 출력 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. 풀이 방법 BFS, DFS 구분하지 않고 뭘 하든 될 줄 알았는데 BFS를 사용하니까 메모리 초과가 발생했다. 그래서 방향을 틀어 DFS를 사용해서 문제를 해결했다. 사실 BFS로 문제를 해결할 때, 이미 Queue 안에 들어간 내용을 따로 체크해줬으면 메모리 초과가 발생하지 않았을 것 같다. 소스코드 #include #include using namespace std; vect..

시간 제한 : 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..

https://www.acmicpc.net/problem/7576 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를..