글 읽기 - 고슴도치 이동 - DFS, 물의 이동 - BFS 로 접근해보았습니다. .

ggolong 4년 전 0

DFS 로 고슴도치의 이동방향을 예측하고, BFS 로 물의 이동을 생각해보며 풀어보았습니다.

무조건 BFS로만 풀어야 하는 건가요?? 제가 생각했을 때 이런 방식으로도 가능할 것 같아서 시도해봤는데 TC는 다 통과하는데 틀렸다고 나와서.. 방법이 잘못된 건지 아니면 코드상에 생각하지 못한 부분이 있는건지 궁금합니다!

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

char map[100][100];
int sunk[100][100];
int dx[4] = { -1, 0, 1, 0 }; // the order is N,W,S,E
int dy[4] = { 0, -1, 0, 1 };

pair<int, int> d_pos, s_pos;
int row, col, min_cnt=9999;
int isValid(int x, int y)
{
	if (x < 0 || x >= row || y < 0 || y >= col) // 장외
		return 0;
	if (map[x][y] == 'X') // 바위
		return 0;
	return 1;
}
void dfs(int x, int y, int cnt, queue<pair<int, int>> water)
{
	if (!isValid(x, y)) return ;
	if (map[x][y] == 'D')
		if (min_cnt > cnt)
			min_cnt = cnt;
	/* 현재 잠긴 물의 위치에서 다음 잠길 위치들 파악 */

	int size = water.size();
	for (int i = 0; i < size; i++)
	{
		pair<int, int> cur = water.front();
		water.pop();
		/* 현재 물의 위치에서 잠시 뒤 잠길 위치 좌표 저장. */
		for (int i = 0; i < 4; i++)
		{
			int nx = cur.first + dx[i], ny = cur.second + dy[i];
			if (isValid(nx, ny) && sunk[nx][ny] == 0 && map[nx][ny] != 'D')
			{
				sunk[nx][ny] = 1; // 잠겼음을 표시
				water.push(make_pair(nx, ny));
			}
		}
	}
	/* 만약 고슴도치가 잠시 뒤 잠길 위치에 도달했다면 이 길은 건널 수 없음. */
	if (sunk[x][y] == 1)
	{
		while (!water.empty()) // 잠겼던 지점들 다시 복구.
		{
			pair<int, int> temp = water.front();
			water.pop();
			sunk[temp.first][temp.second] = 0;
		}
		return;
	}
	/* 고슴도치가 다음 위치로 이동할 수 있다면 */
	else
	{
		for (int i = 0; i < 4; i++)
		{
			sunk[x][y] = 1; // 방문 체크
			dfs(x + dx[i], y + dy[i], cnt + 1, water);
		}
		return;
	}
}
int main()
{
	int time = 0;
	queue<pair<int, int>> initial_water;
	scanf("%d %d", &row, &col);
	getchar();
	for (int i = 0; i < row; i++)
	{
		scanf("%s", map[i]);
		getchar();
	}
	for(int i=0; i<row; i++)
		for (int j = 0; j < col; j++)
		{
			if (map[i][j] == 'D') d_pos = make_pair(i, j);
			if (map[i][j] == 'S') s_pos = make_pair(i, j);
			if (map[i][j] == '*') {
				initial_water.push(make_pair(i, j));
				sunk[i][j] = 1;
			}
		}
	sunk[s_pos.first][s_pos.second] = 1;
	for (int i = 0; i < 4; i++)
		dfs(s_pos.first + dx[i], s_pos.second + dy[i], 1, initial_water);
	if (min_cnt == 9999)
		printf("KAKTUS\n");
	else
		printf("%d\n", min_cnt);
	return 0;
}

hyun11732 4년 전 0

DFS로는 최단거리를 찾을 수 없습니다.

BFS만 최단거리가 나옵니다. 인터넷에 찾아보시면 자세한 내용이 나올겁니다~~

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

문제

문제

출처

ICPC

고슴도치 이동 - DFS, 물의 이동 - BFS 로 접근해보았습니다. .

ggolong 4년 전 0

hyun11732 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말