글 읽기 - 고수님들 DFS 탐색 시 왜 세로축은 0부터 탐색을 해야 하나요?

sjy1602 6년 전 0

solve() 함수가 dfs로 구현한 내용입니다.

제 생각으로는

for (int i = 0; i < N; i++) 이 부분을 for (int i = y; i < N; i++) 이렇게 해도 같은 결과가 나와야 한다고 생각하는데

전혀 다른 결과가 나오더라고요;; 몇 시간째 고민해봐도 답이 안나오는데 왜 가로축은 재귀 전 인덱스부터 탐색해도 되고

세로축은 재귀 전 인덱스부터 탐색하면 안되고 0부터 탐색해야 하는 건가요;;;

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef struct position
{
	int x;
	int y;
}_position;

vector<position> virus;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int N, M;
int map[9][9];
int safe = -1;


int bfs(void);
void solve(int bi, int bj, int depth);

int main(void)
{
	int wall_cnt = 0;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
			

			if (map[i][j] == 2)
				virus.push_back({ j,i });
		}
	}

	solve(0, 0, 0);

	cout << safe << endl;
}

bool dfs_visit[9][9] = { false };
void solve(int x, int y, int depth)
{
	int tmp[9][9];

	if(depth < 3)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = x; j < M; j++)
			{
				if (map[i][j] == 0 && dfs_visit[i][j] == false)
				{
					for (int i = 0; i < N; i++)
						for (int j = 0; j < M; j++)
							tmp[i][j] = map[i][j];

					map[i][j] = 1;
					dfs_visit[i][j] = true;

					solve(j, i, depth + 1);

					dfs_visit[i][j] = false;

					for (int i = 0; i < N; i++)
						for (int j = 0; j < M; j++)
							map[i][j] = tmp[i][j];
				}
			}
		}
	}
	else
	{
		int result = 0;

		bfs();

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (map[i][j] == 0)
					result++;
			}
		}

		if (result > safe)
			safe = result;

		if (result == 27)
		{
			cout << endl;
			for (int i = 0; i < N; i++)
			{
				for (int j = 0; j < M; j++)
				{
					cout << map[i][j] << " ";
				}
				cout << endl;
			}
		}

	}
}
int bfs(void)
{
	bool visit[9][9] = { false };
	int retval = 0;
	int cnt = 1;
	queue<position> q;

	for (int i = 0; i < virus.size(); i++)
	{
		q.push({ virus[i] });
		visit[virus[i].y][virus[i].x] = true;
	}

	while (!q.empty())
	{
		position now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			position next;
			next.x = now.x + dx[i];
			next.y = now.y + dy[i];

			if (next.y >= 0 && next.x >= 0 && next.y < N && next.x < M)
			{
				if (map[next.y][next.x] != 1 && visit[next.y][next.x] == false)
				{
					q.push(next);
					map[next.y][next.x] = 2;
					visit[next.y][next.x] = true;
					cnt++;
				}
			}
		}
	}

	return cnt;
}

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

문제

문제

출처

ICPC

고수님들 DFS 탐색 시 왜 세로축은 0부터 탐색을 해야 하나요?

sjy1602 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말