글 읽기 - 1012번 DFS로 접근 도움부탁드립니다!

semo_semo 5년 전 0

DFS로 접근한 풀이인데 정답은 틀리고 반례나 오류를 찾지 못하고있습니다.

도움 부탁드리겠습니다.

그리구 이런 유형의 문제에서 X Y와 배열에서의 ROW COLUMN이 너무 헷갈리는데 헷갈리지 않고 코딩할 수 있는 자신만의 팁? 같은거 있으신 분들 조언 부탁드립니다ㅜ

#include <stdio.h>
#include <string.h>

int map[50][50] = { 0, };
int visited[50][50] = { 0, };
int udlr[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };	//for checking up,down,left,right


int T;			//number of testcases
int M, N;		//width and height of the map
int K;			//the number of baechoo
int cnt = 0;	//the number of whitebaechoobug that we need

int check_is_in_the_map(int Y, int X)
{
	if (X < 0 || X >= M || Y < 0 || Y >= N) return 0;
	return 1;
}

void dfs(int Y, int X)
{
	visited[Y][X] = 1;
	int updateX, updateY;
	int i;
	for (i = 0; i < 4; i++)
	{
		updateX = X + udlr[i][0];
		updateY = Y + udlr[i][1];
		if ((check_is_in_the_map(updateY, updateX) == 1) && (map[updateY][updateX] == 1) && (visited[updateY][updateX] != 1))
		{
			dfs(updateY, updateX);
		}
	}


}

void solution()
{
	int i, j;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (visited[i][j] == 1) continue;
			else if (map[i][j] == 1)
			{
				dfs(i, j);
				cnt++;
			}
		}
	}
}

int main()
{
	int X, Y;		//the positions of baechoos

	scanf("%d", &T);

	int i,j;

	for (i = 0; i < T; i++)
	{
		scanf("%d %d %d", &M, &N, &K);
		for (j = 0; j < K; j++)
		{
			scanf("%d %d", &X, &Y);
			map[Y][X] = 1;
		}
		solution();
		printf("%d\n", cnt);

		//initialize for the next testcase
		cnt = 0;
		memset(map, 0, sizeof(int));
		memset(visited, 0, sizeof(int));
	}

	return 0;
}

ploffer11 5년 전 2

76, 77번째줄이 틀렸습니다

memset(map, 0, sizeof(int));

memset(visited, 0, sizeof(int)); 를

memset(map, 0, sizeof(map));

memset(visited, 0, sizeof(visited)); 로

바꾸시면 바로 AC를 받습니다

전 모든 2차원 배열 문제는 row column으로 일관성 있게 풉니다. 헷갈리지 않으려고요.

semo_semo 5년 전 0

앗 감사합니다!

모든 2차원 배열 문제를 row column으로 푸신다는게 X나 Y같은 변수를 사용하지 않고 애초에 문제속 X Y를 (이 문제 같은 경우엔 Y를 ROW로 X를 COLUMN이라는 변수로) 정의하고 푸신다는 말씀이신가요?

ploffer11 5년 전 1

네. 문제에서 x나 y, n이나 m을 row column으로 바꿔서 일관적인 풀이를 유지합니다.

이건 제 취향이라 그렇고, 편하신 방법으로 일관적인 풀이를 유지하면 덜 헷갈립니다.

semo_semo 5년 전 0

0 <= ROW(=Y) < N

0 <= COLUMN(=X) < M

map[ROW][COLUMN]

답변 감사합니다. 좋은하루 되세요!

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

문제

문제

출처

ICPC

1012번 DFS로 접근 도움부탁드립니다!

semo_semo 5년 전 0

ploffer11 5년 전 2

semo_semo 5년 전 0

ploffer11 5년 전 1

semo_semo 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말