<aside> 1️⃣

문제: 1012번 유기농 배추

배추 재배 시 해충 방지를 위해 배추흰지렁이를 풀어놓으려고 함

• 배추흰지렁이는 인접한 다른 배추로 이동할 수 있어 인접한 배추를 모두 보호할 수 있음

• 배추가 고르지 않게 심어져 있을 때 배추흰지렁이가 몇 마리 필요한지 구하기

• 배추 분포예시(1이 배추가 있는 곳을 의미)

  • 아래의 경우 최소 5마리가 필요

  1	1	0	0	0	0	0	0	0	0
  0	1	0	0	0	0	0	0	0	0
  0	0	0	0	1	0	0	0	0	0
  0	0	0	0	1	0	0	0	0	0
  0	0	1	1	0	0	0	1	1	1
  0	0	0	0	1	0	0	1	1	1

</aside>

<aside> ✅

코드

#include <stdio.h>
#include <string.h>
#define MAX 50

int field[MAX][MAX];     //밭
int visited[MAX][MAX];   //방문 여부
int dx[] = {0, 0, -1, 1}; //상하좌우 이동
int dy[] = {-1, 1, 0, 0};

int M, N;

void dfs(int x, int y) {
    visited[y][x] = 1; //현재 위치 방문 처리

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i]; //다음 x좌표
        int ny = y + dy[i]; //다음 y좌표

        // 범위 내에 있고, 배추가 있으며 아직 방문하지 않았다면 DFS 계속
        if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
            if (field[ny][nx] == 1 && !visited[ny][nx]) {
                dfs(nx, ny);
            }
        }
    }
}

int main(){
	int T, K;
	scanf("%d", &T); //테스트케이스 개수
	
	while(T--){
		scanf("%d %d %d", &M, &N, &K);//가로, 세로, 배추 개수
		// 초기화
    memset(field, 0, sizeof(field));
    memset(visited, 0, sizeof(visited));

		for(int i = 0; i < K; i++){
			int X, Y;
			scanf("%d %d", &X, &Y); //각 배추의 위치
			field[Y][X] = 1; //배추가 있는 곳은 1
		}
		
		int count = 0; //필요한 지렁이 수
		
		//한 배추에 대해 X좌표가 같거나 Y좌표가 같은 경우 인접한 것
		for (int i = 0; i < N; i++) {
	    for (int j = 0; j < M; j++) {
				// 배추가 있고 아직 방문하지 않은 경우
				if (field[i][j] == 1 && !visited[i][j]) {
	        dfs(j, i); // 그 배추에서 DFS 시작
					count++; // 새 그룹 발견 → 지렁이 한 마리 추가
        }
	    }
		}
		printf("%d\\n", count);		
	}
}

</aside>

<aside> 2️⃣

문제: 1051번 숫자 정사각형

NxM 크기의 직사각형이 있고 각 칸에 한 자리 수가 적혀있을 때, 직사각형에서 꼭짓점의 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램 작성

• 정사각형은 행과 열에 평행
• 입력을 통해 직사각형의 크기와 각 칸에 적힌 수가 주어짐 </aside>

<aside> ✅

코드

#include <stdio.h>

int main(){
	int N, M;
	char rec[50][51]; //문자열로 받기 위해 열을 51로, 행은 50 
	scanf("%d %d", &N, &M);
	
	for(int i = 0; i < N; i++){
		scanf("%s", rec[i]);
	}
	
	int max = 1; //최대 크기는 최소 1
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++) {
	    //최대 변 길이: 끝까지 안 벗어나게
      for(int l = 1; i + l < N && j + l < M; l++){
	      // 네 꼭짓점 비교
        if(rec[i][j] == rec[i][j + l] &&
	        rec[i][j] == rec[i + l][j] &&
          rec[i][j] == rec[i + l][j + l]){
          int square = (l + 1) * (l + 1);
          if (square > max)
          max = square;
      }
    }
		printf("%d", max);
}

</aside>