글 읽기 - 1012번 유기농배추 질문이요

choi0712 3년 전 0

2차원 배열 2개를 잡고 visited를 체크하면서 연결되어진 덩어리들을 찾는 방식으로 짯는데

어디가 틀린건지 잘 모르겠습니다

고수분들 도와주세요 ㅜ

											#include <iostream>
using namespace std;

int cnt;
void DFS(int x, int y, int g[][50], bool v[][50]) {
	v[x][y] = true;
	for(int i=x-1; i<x+2; i++) {
		if(i < 0)
			continue;
		if(g[i][y] == 1 && v[i][y] == false)
			DFS(i,y,g,v);
	}
	for(int i=y-1; i<y+2; i++) {
		if(i<0)
			continue;
		if(g[x][i] == 1 && v[x][i] == false)
			DFS(x,i,g,v);
	}
}

int main() {
	int T;
	int M,N,K;
	int x,y;
	cin>>T;

	while(T--) {
		cin>>M>>N>>K;
		cnt = 0;
		int ground[50][50] = {0,};
		bool visited[50][50] ={0,};
		for(int i=0; i<K; i++) {
			cin>>x>>y;
			ground[x][y] = 1;
		}
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				if(ground[i][j] == 1 && visited[i][j] == false) {
					DFS(i,j,ground,visited);
					cnt++;
				}
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}
										

kesakiyo 3년 전 0

row와 col을 넘어가는 크기에 대해서 제한을 안걸어 두신거 같은데요?

kokorin 3년 전 0

이 배추문제에서는 x,y를 받았을때

ground[x][y]=1로 넣으셨는데 이걸 반대로 하여야 합니다.

ground[y][x]=1로 바꾸셔야합니다.

행렬로 따져보면 지금 배추문제는 반대로 되어있거든요 ㅎ 직접그려보시면 이해하실겁니다.

choi0712 3년 전 0

예시에서 보면 (4,2) (4,3) (4,5) 가 나오는데

그걸로 보면 행열로 따지는게 아니라 앞에 수는 가로좌표의 위치 뒤는 세로좌표의 위치를 나타내는게 맞지 않나요??

kokorin 3년 전 0

제가 말씀드린건 34번째 줄의 ground부분입니다.

프로그램에서 사용하는 행렬과 문제에서의 행렬은 다른부분이 있습니다.

<프로그램에서 사용하는 행렬>

(0,0)	(0,1)
(1,0)	(1,1)

<문제에서 사용하는 행렬>

(0,0)	(1,0)
(0,1)	(1,1)

보시면 반대로 되어있으니 x,y값 받은것을 반대로 하시면 되겠죠??

밑에는 제가 성공한 c소스입니다. 참고 바랍니다 ㅎ

					#include <stdio.h>
 
int M, N;
int G[50][50];
void Check(int a,int b){
        G[a][b]=0;
        if(a-1>=0 && G[a-1][b]==1) Check(a-1,b);    
        if(b+1 < M && G[a][b+1]==1) Check(a,b+1);
        if(a+1 < N && G[a+1][b]==1) Check(a+1,b);
        if(b-1>=0 && G[a][b-1]==1) Check(a,b-1);
         
    }
int main(){
    int T;
    int K;
 
    int x,y;
    int count=0;
 
    scanf("%d",&T);
    for(int i=0; i<T; i++){
        scanf("%d %d %d",&M,&N,&K);
        for(int a=0; a<N; a++)
            for(int b=0; b<M; b++)
                G[a][b]=0;
        for(int c=0; c<K; c++){
            scanf("%d %d",&x,&y);
            G[y][x]=1;
        }
     
    for(int d=0; d<N; d++)
        for(int e=0; e<M; e++)
            if(G[d][e]==1){
            Check(d,e);
            count++;
    
        }
    printf("%d\n",count);
    count=0;
     
     
    }
}
				

choi0712 3년 전 0

아 이해했습니다. x,y가 바뀐거랑 최대값 제한이 없었던게 문제였네요

도움주신분들 정말 감사합니다.

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

문제

문제

출처

ACM-ICPC

1012번 유기농배추 질문이요

choi0712 3년 전 0

kesakiyo 3년 전 0

kokorin 3년 전 0

choi0712 3년 전 0

kokorin 3년 전 0

choi0712 3년 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

서버 상태