https://www.acmicpc.net/problem/1012
아이디어
처음에는 배열을 50x50칸주고 배열의 첫칸부터 시작해서
array[i][j]가 1이라면 에벌레의 수를 +1하고 array[i + 1][j]와 array[i][j + 1]을 2하여 0이라면 변화를 주지 않고 1이라면 2하려고 했다.
그리고 array가 1보다 크면 에벌레의 수를 더하지 않고 똑같이 아래쪽과 오른쪽을 *2하려 했다.
그런데 이렇게 하니까
이런 모양일 때 처음 만나는 1보다 왼쪽의 것들은 *2가 되지 않아 카운트가 늘어나는 것을 알게되었다.
그래서 사용자 정의함수를 만들어 어떤 수가 1임을 찾으면 그 수를 0으로 만들고 왼쪽 오른쪽 위쪽 아래쪽을 탐색해 1이 있으면 그 칸에서 다시 함수를 실행하도록 하였다.
그 때의 코드
#include <stdio.h>
void Find(int array[][50],int X, int Y)
{
array[X][Y] = 2;
if (array[X + 1][Y] == 1) Find(array, X + 1, Y);
if (array[X][Y + 1] == 1) Find(array, X, Y + 1);
if (array[X - 1][Y] == 1) Find(array, X - 1, Y);
if (array[X][Y - 1] == 1) Find(array, X, Y - 1);
}
int main()
{
int i, j, k, M, N, K, T ,X, Y;
scanf("%d", &T);
for (i = 0; i < T; i++)
{
int array[50][50] = { 0 };
int count = 0;
scanf("%d %d %d", &M, &N, &K);
for (j = 0; j < K; j++)
{
scanf("%d %d", &X, &Y);
array[X][Y] = 1;
}
for (j = 0; j < M; j++)
{
for (k = 0; k < N; k++)
{
if (array[j][k] == 1)
{
Find(array, j, k);
count++;
}
}
}
printf("%d\n", count);
}
return 0;
}그런데 이렇게 해도 오류가 생길 수 있다.
왜냐하면
이렇게 배열에 포함되지 않은 칸도 함수의 영향을 받게 되는데 만약 저헣게 1이 연속으로 세칸있으면 배열안에서 인접하지 않은 칸까지 0이 될 수 있기 때문이다.
즉, 위 아래로 여유를 한칸씩 두고 모두 0으로 만들어주는게 필요하다.
내 최종 코드
#include <stdio.h>
void Find(int array[][52], int X, int Y)
{
array[X][Y] = 2;
if (array[X + 1][Y] == 1) Find(array, X + 1, Y);
if (array[X][Y + 1] == 1) Find(array, X, Y + 1);
if (array[X - 1][Y] == 1) Find(array, X - 1, Y);
if (array[X][Y - 1] == 1) Find(array, X, Y - 1);
}
int main()
{
int i, j, k, M, N, K, T, X, Y;
scanf("%d", &T);
for (i = 0; i < T; i++)
{
int array[52][52] = { 0 };
int count = 0;
scanf("%d %d %d", &M, &N, &K);
for (j = 0; j < K; j++)
{
scanf("%d %d", &X, &Y);
array[X + 1][Y + 1] = 1;
}
for (j = 1; j <= M; j++)
{
for (k = 1; k <= N; k++)
{
if (array[j][k] == 1)
{
Find(array, j, k);
count++;
}
}
}
printf("%d\n", count);
}
return 0;
}실수로 잘못 짰던 코드
#include <stdio.h>
int array[50][50];
void Find(int X, int Y)
{
array[X][Y] = 0;
if (array[X + 1][Y] == 1) Find(array, X + 1, Y);
if (array[X][Y + 1] == 1) Find(array, X, Y + 1);
if (array[X - 1][Y] == 1) Find(array, X - 1, Y);
if (array[X][Y - 1] == 1) Find(array, X, Y - 1);
}
int main()
{
int i, j, k, M, N, K, T, X, Y;
scanf("%d", &T);
for (i = 0; i < T; i++)
{
int count = 0;
scanf("%d %d %d", &M, &N, &K);
for (j = 0; j < K; j++)
{
scanf("%d %d", &X, &Y);
array[X][Y] = 1;
}
for (j = 0; j < M; j++)
{
for (k = 0; k < N; k++)
{
if (array[j][k] == 1)
{
Find(j, k);
count++;
}
}
}
printf("%d\n", count);
}
return 0;
}코드를 수정하다가 아주 어이없는 실수를 저질렀다.
전역변수로 두고 메모리를 아껴보려다가
Find 함수를 정수 변수 두개를 받는다고 해놓고
함수 내에서 다시 불러오는 부분에서 array를 변수에 넣어버렸다.
이랬더니 printf문에 들어가기 전에 종료가 되어버리던데 아마 array를 x값으로 받아와서 배열의 범위를 한참 초과해서 터진게 아닐까 싶다.
다른 사람 코드
drestar2님의 코드다
https://www.acmicpc.net/user/drestar2
#include <stdio.h> // 처음에 메인 함수부터 읽어볼 것이다.
int dy[4] = {-1, 1, 0, 0};// 메인함수를 읽고 여기로 돌아왔다. dy dx가 뭘 의미하는걸까? 통상적인 의미로 생각하면 x와 y의 변화량인데
int dx[4] = { 0, 0,-1, 1};
void del(char a[][52], int y, int x) {
int i, y1, x1;
a[y][x]--; // a[y][x]는 일단 0 이 된다.
왜 y,x이냐 앞쪽이 행 뒤쪽이 열이므로 직관적으로 y값 x값이기 때문
for (i=0; i<4; i++) {
y1=y+dy[i], x1=x+dx[i]; //이렇게 코드의 길이를 줄이다니 참신하다.
if (a[y1][x1])
del(a, y1, x1);// 이동한 칸이 1일 때만 del실행
나랑 완벽히 같은 아이디어이나 구현이 조금 다르다.
}
}
int main() {
char a[52][52] = {0, };// 일단 char배열을 사용하여 메모리를 아꼈다.
int t, m, n, k, i, j, c;
scanf("%d", &t);
while (t--) { //테스트 케이스 개수만큼
c = 0; //내 코드의 카운트와 같은 역할
scanf("%d%d%d", &m, &n, &k);
while (k--) { //k는 다시 안 쓰니까 이렇게 써먹을 수 있다.
scanf("%d%d", &j, &i);
a[i+1][j+1]++;
}
for (i=1; i<=n; i++) {
for (j=1; j<=m; j++) {
if (a[i][j]) { //a배열의 그 칸의 수가 0이 아니면
del(a, i, j); //딜리트 함수 실행
c++; //c++, 아 이걸 보니 딜리트 함수는 인접한 칸들을 0으로 만들겠구나
}
}
}
printf("%d\n", c);
}
}이게 C언어 2등 코드인데 나랑 아이디어는 거의 완벽히 같았다.
하지만 행렬의 칸들이 1아니면 0이게 만들어 if( == 1)을 쓸 필요없다는 걸 이용한다던가
char배열을 이용하여 메모리를 아끼거나 하는 등의 소소한 점들이 나와 차이가 났다.
