인프런 커뮤니티 질문&답변

안녕하세요 레페님 ㅎㅎ

시도는 좋았습니다. ㅎㅎ

또 당연한 질문인 것 같지만.. 그래프 문제를 풀 때 dfs나 bfs 둘 중 하나로만 푸는 것이 효율적이겠지요?

>> 아니요. 둘 다 해야 하는 문제도 있습니다.

그러나 이 로직은 굳이 2개가 필요하지 않은 로직입니다.

void dfs(int y, int x)
{
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++)
	{
		ny = y + dy[i];
		nx = x + dx[i];

		// 유효하지 않은 좌표거나 방문한 좌표면 continue
		if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[ny][nx]) continue;

		// 치즈에 닿으면 continue
		if (cheese[ny][nx] == -1) continue;

		// 공기에 닿으면 dfs
		if (cheese[ny][nx] == 0)
		{
			// BFS를 위한 큐에 push
			q.push({ ny, nx });

			dfs(ny, nx);
		}
	}
	return;
}

dfs로 연이여서 탐색이 가능한데 굳이 q를 사용해야 하는지.. 불필요한 코드라고 보시면 됩니다.

또한 굳이 공기층부터 시작하는 이유가 있을까요? 공기부터 시작해서 가장자리의 치즈부터 시작해야 하는게 아닐까요?

		// 공기에 닿으면 dfs
		if (cheese[ny][nx] == 0)
		{
			// BFS를 위한 큐에 push
			q.push({ ny, nx });

이미 dfs에서 q푸시를 했을 때 방문처리가 되어있는데

			// BFS를 위한 큐에 push
			q.push({ ny, nx });

			dfs(ny, nx);

중복해서 한 부분도 비효율적입니다.

	while (q.size())
	{
		tie(y, x) = q.front();
		q.pop();

		// 방문 처리
		visited[y][x] = 1;

이런 코드를 디버깅하는게 사실 제일 어렵습니다.

분명히 맞는데 왜 틀릴까 하는 것이죠..

그 때는 코드에서 불필요한 부분이 있는지. 를 중심으로 탐색해야 합니다.

얼핏 봤을 때 레페님의 로직은 저도 괜찮다고 생각했지만.. 이런식으로 불필요한 부분이 있는지 탐색했고 아 이런 반례를 처리하지 못하겠구나 생각했습니다.

반례는 다음과 같습니다.

8 7
0 0 0 0 0 0 0
0 1 1 1 1 1 0 
0 1 0 0 0 1 0 
0 1 0 1 0 1 0 
0 1 0 1 0 1 0 
0 1 0 0 0 1 0 
0 1 1 1 1 1 0 
0 0 0 0 0 0 0 

정답 : 2 2

레페님 코드 : 1 20

감사합니다.