글 읽기 - dfs 로 구현했는데 어디가 틀린걸까요?

shinbian11 3년 전 0

입력받은 k와 같은 수가 항상 출력되는것 같습니다...

//C++

#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.1415926535

using namespace std;
typedef long long ll;
int m, n, k, cnt;
int arr[54][54];
int visited[54][54];
int dir[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };
queue<pair<int, int> > q;
void dfs(int i, int j)
{
	visited[i][j] = true;
	for (int k = 0; k < 4; k++)
	{
		int next_i = i + dir[i][0];
		int next_j = j + dir[i][1];
		if (next_i >= 0 && next_i < n && next_j <= 0 && next_j < m && visited[next_i][next_j]==0 && arr[next_i][next_j]==1)
		{
			visited[next_i][next_j] = 1;
			dfs(next_i, next_j);
		}
	}
}
int main()
{
	F_I;
	int tc;
	cin >> tc;
	while (tc--)
	{
		cnt = 0;
		cin >> m>>n>>k;
		for (int i = 0; i < k; i++)
		{
			int a, b;
			cin >> a >> b;
			arr[b][a] = 1;
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (visited[i][j] == 0 && arr[i][j] == 1)
				{
					++cnt;
					dfs(i, j);
					
				}
			}
		}
		cout << cnt << '\n';
	}

}

djm03178 3년 전 1

19, 20번째 줄 dir[i]가 아닌 dir[k]가 되어야 할 것 같습니다.

shinbian11 3년 전 0

고쳐도 똑같네요.. 어떤 부분에서 또 문제가 있는건지....x랑 y를 생각하는데 헷갈리네요.

djm03178 3년 전 0

21번째 줄 next_j <= 0이 아니라 next_j >= 0이어야 합니다.

djm03178 3년 전 0

또한 매 케이스마다 arr과 visited를 초기화도 해줘야 합니다.

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

문제

문제

출처

ICPC

dfs 로 구현했는데 어디가 틀린걸까요?

shinbian11 3년 전 0

djm03178 3년 전 1

shinbian11 3년 전 0

djm03178 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말