[1012] 유기농 배추

문제

1012번: 유기농 배추

 

 

 

해결 방법

[2667] 단지번호붙이기와 정말정말 유사한 문제 같아서, 유사한 문제여서 야심차게 도전했는데

예제와 질문 게시판의 모든 testcase들을 돌려보고 올바르게 실행이 됨에도 불구하고 자꾸 채점하자마자 틀렸다고 떠서짜증나서 하다가 포기했다.

그래서 질문 게시판에 결국.... 또 질문을 올렸는데 나는 내가 쓴 코드에 너무 빠져서 이게 맞다고만 생각이 드니까 틀린부분을 못찾아냈던 것 같은데 항상 질문 올릴 때마다 잘못된 부분을 콕콕 집어내시는 분들 정말 신기하다.

나도 나중에 후배들을 위해서 그런 사람이 되고 싶다..ㅎ

문제는 정말 간단하다.

dfs를 돌려서 connected components의 수를 출력하면 되는 것.

 

원래의 내 코드는 50번째, 54번째 줄 모두 범위를 width[i]라고 설정한 것이었다. (이것 때문에 계속 틀렸던 것이다ㅜㅜ)

단지번호붙이기 문제에서는 정사각형이었기 때문에 범위가 둘 다 같아도 상관없지만
이 문제 같은 경우는 밭의 가로와 세로의 길이가 다르기 때문에 범위도 다르게 설정해야 했던 것이다....

그리고 

1	2	3	4
5	6	7	8
9	10	11	12

밭을 탐색할 때는 위와 같은 순서대로 탐색할 것이기 때문에 
dfs(x, y)에서 x의 최댓값은 height[i], y의 최댓값은 width[i]를 따라야 하는 것이다.

끝!!

 

 

내 코드(C)

/*[1012] 유기농 배추*/
/*https://www.acmicpc.net/problem/1012*/
#include <stdio.h>

int matrix[51][51] = { 0, }, width[51], height[51];
int visit[51][51] = { 0, };
int i;
void dfs(int x, int y);

int main(void)
{
    int spot[51], arr[2501];
    int t, count; /*the number of test cases, number of connected components*/
    int x, y;
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        count = 0;
        scanf("%d %d %d", &width[i], &height[i], &spot[i]);
        for (int j = 0; j < spot[i]; j++) {
            scanf("%d %d", &x, &y);
            matrix[y][x] = 1;
        }
        
        for(int j = 0 ; j < height[i] ; j++) {
        	for(int k = 0 ; k < width[i] ; k++) }
            	if (matrix[j][k] == 1 & !visit[j][k]) {
                    dfs(j, k);
                    count++;
                }
            }
        }       
                
        /*initialization*/
        arr[i] = count;
        for (int j = 0; j < 51; j++) {
        	for (int k = 0; k < 51; k++) {
                matrix[j][k] = 0;
                visit[j][k] = 0;
            }
        }
    }
    
    for (int i = 0; i < t; i++) {
    	printf("%d\n", arr[i]);
    }
}

void dfs(int x, int y)
{
    visit[x][y] = 1;
    if (x - 1 >= 0 && !visit[x - 1][y] && matrix[x - 1][y] == 1) 
        dfs(x - 1, y);
    if (x + 1 < height[i] && !visit[x + 1][y] && matrix[x + 1][y] == 1) 
        dfs(x + 1, y);
    if (y - 1 >= 0 && !visit[x][y - 1] && matrix[x][y - 1] == 1)
        dfs(x, y - 1);
    if (y + 1 < width[i] && !visit[x][y + 1] && matrix[x][y + 1] == 1)
        dfs(x, y + 1);
}