whdtjq0101   9달 전

#include <stdio.h>
int M, N, K;
int matrix[55][55] = { 0 };             // 맵
int visit[55][55] = { 0 };                 // 방문여부
int queue[50000][2] = { 0 };        // 이동 방향을 표시할 큐
int T = 0;                                        // 테스트 케이스
int front = 0;                                 // 큐 사용을 위한 front 와 rear
int rear = 0;


int IsEmpty()                                // 큐가 비었는지 확인하는 함수
{
if (rear == front)
return 0;                // 비었다면 0 리턴
else
return 1;                // 비지 않았다면 1 리턴
}
void enqueue(int x, int y)        // 큐에 값 삽입
{
queue[rear][0] = x;
queue[rear][1] = y;
++rear;
}
void dequeue()                        // 큐에 값 제거
{
queue[front][0] = 0;
queue[front][1] = 0;
++front;
}
void KCheck()                          // K 범위 체크
{
while (K > 2500 || K < 1)
scanf("%d", &K);
}
void MCheck()                        // M 범위 체크
{
while (M > 50 || M < 1)
scanf("%d", &M);
}
void NCheck()                         // N 범위 체크
{
while (N > 50 || N < 1)
scanf("%d", &N);
}
void bfs(int i, int j)                  // bfs 함수 수행
{
while (IsEmpty())                    // 큐의 값이 빌 때 까지 수행
{
int x = queue[front][0];
int y = queue[front][1];              
if (matrix[y + 1][x] == 1 && visit[y + 1][x] == 0)           // 아래방향 탐색
{
enqueue(x, y + 1);
visit[y + 1][x] = 1;
}
if (matrix[y][x + 1] == 1 && visit[y][x + 1] == 0)           // 오른쪽방향 탐색
{
enqueue(x + 1, y);
visit[y][x + 1] = 1;
}
if (matrix[y - 1][x] == 1 && visit[y - 1][x] == 0)             // 위쪽방향 탐색
{
enqueue(x, y - 1);
visit[y - 1][x] = 1;
}
if (matrix[y][x - 1] == 1 && visit[y][x - 1] == 0)             // 왼쪽방향 탐색
{
enqueue(x - 1, y);
visit[y][x - 1] = 1;
}
dequeue();                  // 모든 방향 탐색 시 그 큐를 비운다.
}
}
int main(void)
{
int CaseCount = 0;
int i, j, n;
int count[500] = { 0 };
int C = 0;
scanf("%d", &T);
while (CaseCount < T)
{
scanf("%d %d %d", &M, &N, &K);           // 가로 세로 점의 개수 입력
MCheck();                                                   // 범위 체크
NCheck();
KCheck();
for (i = 0; i < K; ++i)
{
scanf("%d %d", &n, &j);                            // 배추의 좌표 입력
matrix[j][n] = 1;                                         // 해당 위치의 맵 값을 1로 초기화
}
for (i = 0; i < M; ++i)
{
for (j = 0; j < N; ++j)
{
if (matrix[j][i] == 1 && visit[j][i] == 0)          // Count 하는 부분
{
enqueue(i, j);
visit[j][i] = 1;
bfs(i, j);
count[C] += 1;        // 배열을 사용하여 떨어져있는 점이 있을 때 마다 근방의 배추들을 bfs 함수를 통해 탐색하고 갈 방향이 없어 bfs 함수가 종료되면 count 값을 올리게 된다.
}
}
}
++C;             // count 배열 증가를 위한 증가 연산
++CaseCount;     // 테스트케이스 증가를 위한 증가 연산
}
for (i = 0; i < C; ++i)
{
printf("%d\n", count[i]);     // 테스트케이스 들에 해당하는 지렁이 수 출력
}

return 0;
}

배추가 있는 곳 중 한 곳을 들리게 되면 BFS 함수를 통해서 방문을 하게됩니다. 그리고 더이상 갈 곳이 없을 시에 for문을 또 수행하게되는데 BFS 함수를 통해 이미 방문을 하였기 때문에 근방의 배추에서는 if문이 수행되지 않는 구조입니다.

mic1021   9달 전

코드 보기가 힘들어요 ㅠㅠ

whdtjq0101   9달 전

ㅠ 너무 함수 많이 써서 그런가유...?

댓글을 작성하려면 로그인해야 합니다.