[boj][c++] 4963 섬의개수

4963 섬의 개수

dfs로 풀었다. 코드 수정 전에는 set_visit() 함수에서 초기화를 visit 배열만 수행했는데, 이게 문제였다.

w와 h를 매번 갱신하므로 문제가 없을거라고 생각했는데 착각이었다. 문제를 없애기 위해 arr 배열도 초기화해주었다. 단순히 문제의 정답을 구하기 위해 다양한 조건을 추가해서 결과를 구했지만 왜 이게 틀린건지 모르겠다. 그림으로 그려봤을 때 arr배열을 초기화하지 않아서 혹시 범위 밖의 내용이 포함되어도 조건문에 걸리게 되므로 문제되지 않는다. 컴퓨터는 잘못이 없는데 내가 뭔가를 놓친 것 같다.

<22.07.22>

#include	<iostream>
using namespace std;

int arr[51][51];
int visit[51][51];
int dh[8] = { 0, 0, 1, -1, -1, -1, 1, 1 };
int dw[8] = { 1, -1, 0, 0, -1, 1, -1, 1 };
int w, h, ans;

void set_visit()
{
	for(int i=0;i<51;i++)
		for (int j = 0; j < 51; j++)
		{
			visit[i][j] = 0;
			arr[i][j] = 0;
		}
}

void	dfs(int hn, int wn)
{
	for (int i = 0; i < 8; i++)
	{
		int sh = hn + dh[i];
		int sw = wn + dw[i];
		if ((sh >= 0 || sh < h) && (sw >= 0 || sw < w))
		{
			if ((arr[sh][sw] == 1) && (visit[sh][sw] == 0))
			{
				visit[sh][sw] = 1;
				dfs(sh, sw);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	while (1)
	{
		cin >> w >> h;
		ans = 0;
		if (w == 0 && h == 0)
			return (0);
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> arr[i][j];
			}
		}
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (arr[i][j] == 1 && visit[i][j] == 0)
				{
					visit[i][j] = 1;
					ans++;
					dfs(i, j);
				}
			}
		}
		cout << ans << "\n";
		set_visit();
	}
}

(22.07.23추가) 논리연산자 이슈

arr배열을 초기화해야 문제가 해결됐던 이유는 논리연산자를 부적합하게 사용했기 때문이었다. 백준 질문 페이지에 질문을 등록했고 다음과 같은 답을 받았다. if ((sh >= 0 || sh < h) && (sw >= 0 || sw < w)) 는 범위를 벗어나는 구간도 조건문에 체크될 수 있으므로 if ((sh >= 0 && sh < h) && (sw >= 0 && sw < w))로 수정하면 arr배열을 초기화하지 않아도 내가 의도한 기능을 수행할 수 있다.

어제 작성한 코드도 문제없이 실행되지만 위에서 말한 코드는 사실상 불필요한 코드가 되므로 수정하였다.

<22.07.23>

#include	<iostream>
using namespace std;

int arr[51][51];
int visit[51][51];
int dh[8] = { 0, 0, 1, -1, -1, -1, 1, 1 };
int dw[8] = { 1, -1, 0, 0, -1, 1, -1, 1 };
int w, h, ans;

void set_visit()
{
	for(int i=0;i<51;i++)
		for (int j = 0; j < 51; j++)
		{
			visit[i][j] = 0;
		}
}

void	dfs(int hn, int wn)
{
	for (int i = 0; i < 8; i++)
	{
		int sh = hn + dh[i];
		int sw = wn + dw[i];
		if ((sh >= 0 && h < h) && (sw >= 0 && sw < w))
		{
			if ((arr[sh][sw] == 1) && (visit[sh][sw] == 0))
			{
				visit[sh][sw] = 1;
				dfs(sh, sw);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	while (1)
	{
		cin >> w >> h;
		ans = 0;
		if (w == 0 && h == 0)
			return (0);
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> arr[i][j];
			}
		}
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (arr[i][j] == 1 && visit[i][j] == 0)
				{
					visit[i][j] = 1;
					ans++;
					dfs(i, j);
				}
			}
		}
		cout << ans << "\n";
		set_visit();
	}
}