글 읽기 - 1012 유기농 배추 DFS로 풀었습니다.

persona_k 5년 전 2

DFS 재귀로 풀어서, 답도 제대로 나옵니다.

다만 계속 틀렸다고 해서 무엇이 문제인지 알고 싶습니다.

다른 글들도 많이 봤으나 해결이 나지 않아서 질문을 드립니다. ㅠㅠ

#include<iostream>
using namespace std;

#define MAX 51
int mp[MAX][MAX];
bool visit[MAX][MAX];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int T, M, N, K;
int cnt;
int column, row;


//세로, 가로
void dfs(int x, int y)
{
	//시작지점을 방문했다고 체크
	visit[x][y] = true;
	for (int k = 0; k < 4; k++)
	{
		//다음 좌표값을 정해주고
		int nx = x + dx[k];
		int ny = y + dy[k];
		//다음 방향이 범위 내에 있다면
		if (0 <= nx && nx < N && 0 <= ny && ny < M)
		{
			//그 방향이 배추가 있고, 방문하지 않았다면
			if (mp[nx][ny]&&!visit[nx][ny])
			{
				visit[nx][ny] = true;
				//탐색
				dfs(nx, ny);
			}
		}
	}
}
//초기화
void init()
{
	//지렁이초기화
	cnt = 0;
	//맵 초기화
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			mp[i][j] = 0;
}

int main()
{
	//테스트 케이스 입력
	cin >> T;

	//테스트 케이스 대로 입력을 받음
	while (T--)
	{
		//초기화
		init();
		cin >> M >> N >> K;
		//배추가 있는 좌표 입력
		for (int i = 0; i < K; i++)
		{
			//가로, 세로 입력순
			cin >> column >> row;
			if (0 <= column && column < M && 0 <= row && row < N)
			{
				mp[row][column] = 1;
			}
		}
		//세로의 길이
		for (int i = 0; i < N; i++)
		{
			//가로의 길이
			for (int j = 0; j < M; j++)
			{
				//배추가 심어져 있는 곳부터 dfs탐색시작
				if (mp[i][j] && !visit[i][j])
				{
					dfs(i, j);
					//지렁이 추가
					cnt++;
				}

			}
		}
		//지렁이 출력
		cout << cnt;
	}
	return 0;
}

persona_k 5년 전 1

아 깨달았습니다!!

혹시나 저처럼 헤매실까바 댓글을 작성합니다

여기서의 문제점은

지렁이 출력할 때

cout<< cnt << endl; 로 출력형식을 지켜줘야하는 미스가 있었습니다.

또, 초기화 부분해서 함수 init()을 보시면

visit배열을 초기화 해주지 않았네요 ㅋㅋ..

저처럼 해결되셨으면 좋겠습니다!!

감사합니다~

persona_k 5년 전 2

혹시나 맞는 소스가 궁금하실까바 올려드립니다.

#include<iostream>
using namespace std;

#define MAX 51
int mp[MAX][MAX];
bool visit[MAX][MAX];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int T, M, N, K;
int cnt;
int column, row;


//세로, 가로
void dfs(int x, int y)
{
	//시작지점을 방문했다고 체크
	visit[x][y] = true;
	for (int k = 0; k < 4; k++)
	{
		//다음 좌표값을 정해주고
		int nx = x + dx[k];
		int ny = y + dy[k];
		//다음 방향이 범위 내에 있다면
		if (0 <= nx && nx < N && 0 <= ny && ny < M)
		{
			//그 방향이 배추가 있고, 방문하지 않았다면
			if (mp[nx][ny]&&!visit[nx][ny])
			{
				visit[nx][ny] = true;
				//탐색
				dfs(nx, ny);
			}
		}
	}
}
//초기화
void init()
{
	//지렁이초기화
	cnt = 0;
	//맵 초기화
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			mp[i][j] = 0;
			visit[i][j] = false;
		}
	}
}

int main()
{
	//테스트 케이스 입력
	cin >> T;

	//테스트 케이스 대로 입력을 받음
	while (T--)
	{
		//초기화
		init();
		cin >> M >> N >> K;
		//배추가 있는 좌표 입력
		for (int i = 0; i < K; i++)
		{
			//가로, 세로 입력순
			cin >> column >> row;
			if (0 <= column && column < M && 0 <= row && row < N)
			{
				mp[row][column] = 1;
			}
		}
		//세로의 길이
		for (int i = 0; i < N; i++)
		{
			//가로의 길이
			for (int j = 0; j < M; j++)
			{
				//배추가 심어져 있는 곳부터 dfs탐색시작
				if (mp[i][j] && !visit[i][j])
				{
					dfs(i, j);
					//지렁이 추가
					cnt++;
				}

			}
		}
		//지렁이 출력
		cout << cnt << endl;
	}
	return 0;
}

progress 4년 전 0

슬픕니다...

https://www.acmicpc.net/board/view/47979

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

문제

문제

출처

ICPC

1012 유기농 배추 DFS로 풀었습니다.

persona_k 5년 전 2

persona_k 5년 전 1

persona_k 5년 전 2

progress 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말