와드의 블로그

문제흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)가 있습니다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 됩니다. 만약 0과 1이 섞여 있으면, 영상을 4개의 영역으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 괄호 안에 묶어서 표현합니다. N × N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 문제입니다.입력: 첫째 줄에 영상의 크기 N (N은 1, 2, 4, 8, 16, 32, 64 중 하나)이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 길이가 N인 0과 1로 이루어진 문자열이 주어집니다.출력: 영상을 압축한 결과를 출력합니다.링크: https://www.acmicpc.n..

문제눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있습니다. 이 모눈종이 위에 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어집니다. 분리된 각 영역의 개수와, 각 영역의 넓이를 오름차순으로 정렬하여 출력하는 문제입니다.입력: 첫째 줄에 M(세로), N(가로), 그리고 직사각형의 개수 K가 주어집니다. 둘째 줄부터 K개의 줄에 직사각형의 왼쪽 아래 꼭짓점 좌표 (x1, y1)과 오른쪽 위 꼭짓점 좌표 (x2, y2)가 주어집니다.출력: 첫째 줄에 분리된 영역의 개수를 출력하고, 둘째 줄에 각 영역의 넓이를 오름차순으로 정렬하여 공백으로 구분해 출력합니다.링크: https://www.acmicpc.net/problem/2583풀이..

문제어떤 지역의 높이 정보가 N×N 크기의 2차원 배열로 주어집니다. 많은 비가 내리면 수위 이하의 모든 지점이 물에 잠기게 됩니다. 물에 잠기지 않는 안전한 영역이란, 물에 잠기지 않은 지점들이 상하좌우로 인접해 있으며 그 크기가 최대인 영역(덩어리)을 말합니다. 비의 양(수위)에 따라 물에 잠기는 지점이 달라질 때, 발생할 수 있는 안전한 영역의 최대 개수를 구하는 문제입니다.입력: 첫째 줄에 2차원 배열의 행과 열의 개수 N이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 각 지점의 높이가 주어집니다. (높이는 1 이상 100 이하의 정수)출력: 첫째 줄에 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력합니다.링크: https://www.acmicpc...

문제차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배합니다. 배추를 보호하기 위해 배추흰지렁이를 구입했는데, 이 지렁이는 상하좌우로 인접한 배추로 이동할 수 있습니다. 따라서 배추들이 모여있는 덩어리(군데)마다 최소 1마리의 지렁이가 필요합니다. 배추밭의 크기와 배추가 심어진 위치가 주어질 때, 각 테스트 케이스에 대해 필요한 최소 배추흰지렁이 마리 수를 구하는 문제입니다.입력: 테스트 케이스의 개수 T, 배추밭의 가로길이 M, 세로길이 N, 배추가 심어져 있는 위치의 개수 K. 이어서 K개의 줄에 배추의 위치 X, Y가 주어집니다.출력: 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수.링크: https://www.acmicpc.net/problem/1012풀이이 문제는 2차원 격자..

문제N×M 크기의 배열로 표현되는 미로가 있습니다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타냅니다. (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제입니다. 한 칸에서 다른 칸으로 이동할 때에는 서로 인접한 칸으로만 이동할 수 있습니다. (칸을 셀 때에는 시작 위치와 도착 위치도 포함합니다.)입력: 첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 100)이 주어집니다. 다음 N개의 줄에는 M개의 정수로 미로가 주어집니다. 각각의 수들은 붙어서 입력으로 주어집니다.출력: 첫째 줄에 지나야 하는 최소의 칸 수를 출력합니다.링크: https://www.acmicpc.net/problem/2178풀이가중치가 동일한(모든 칸의..