글 읽기 - DFS 방식도 가능할까요?

moonstar114 3년 전 0

먹이의 동일 조건하에 우선순위가 위쪽일수록 그리고 왼쪽일수록 이기때문에

맵의 원소를 행의 왼쪽부터 순회하면서 먹을 수 있는 물고기면 그것에 대한 최단경로를 계산하여 파악하려 했습니다.

시간초과의 원인을 아직 찾지 못해서 다른 분들의 코드를 찾아보았는데 거의 모든 분들이 BFS를 사용했더라구요..

궁금한 점은 두가지입니다.

1. 제 방식대로 하면 어떤 부분에서 시간이 잡히는걸까요? ( 테스트케이스의 답이 나오긴하는데 시간이 너무오래걸립니다.. )

2. DFS의 문제라면 BFS와 DFS 둘중에 택해야 할 때, 어떤 점을 보고 이건 BFS로 해결해야겠다라고 감이 잡힐까요?

살려주세요 ㅜㅜ

#include <iostream>
using namespace std;

int n, dist;
int map[21][21];
int dx[4] = {-1,0,0,1};
int dy[4] = {0,-1, 1,0};
int shark_r, shark_c;
int shark_size = 2;
int target_r, target_c;
bool available;
bool visit[21][21];

void is_available(int , int , int, int);
int main() {

	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 9) {
				shark_r = i, shark_c = j;
			}
		}
	}

	bool done = false;
	int sec = 0;
	int cnt = 0; 



	//DFS 브루트포스 실패코드 (시간초과)
	
	while (1) {
		if (done) break;
		int min_dist = 100000;
		int eat_r, eat_c;

		for (int r = 1; r <= n; r++) {
			for (int c = 1; c <= n; c++) {

				//1. 물고기가 아니고 벽이나 상어자신이라면 확인할 필요X
				if (map[r][c] == 0 || map[r][c] == 9) {
					continue;
				}
				//2. 상어 크기가 map[r][c] 보다 같거나 작으면 먹을 수 없음.
				if (shark_size <= map[r][c]) {
					continue;
				}

				//3. 먹을 수 있는 물고기라면, 이 위치까지 가는 최소거리 찾기.
				//DFS 초기화
				for (int i = 1; i <= n; i++) {
					for (int j = 1; j <= n; j++)
						visit[i][j] = false;
				}
				
				target_r = r, target_c = c, dist = 100000;
				available = false;
				is_available(shark_r, shark_c, 0, min_dist);

				//경로가 존재함.
				if (available) {
					cout << r << " ," << c << " is available, dist : " << dist << endl;
					// 최소거리 갱신이 필요하면 갱신함.
                    if (min_dist > dist) {
						eat_r = r, eat_c = c;
						min_dist = dist;
					}
				}
				else {
					cout << r << " ," << c << " is not available\n";
				}
			}
		}

		// 엄마상어 호출 조건 ( 먹이를 찾지 못함 )
		if (min_dist == 100000) done = true;
		else {
			//먹이가 있는거면 상어 이동하고, cnt 업데이트, 상어크기 업데이트

			cout << "eat ( " << eat_r << ", " << eat_c << " )" << endl;
			cout << "shark : ( " << shark_r << ", " << shark_c << " )" << endl;
			sec += min_dist;
			map[shark_r][shark_c] = 0;
			shark_r = eat_r, shark_c = eat_c;
			map[shark_r][shark_c] = 9;
			cnt++;
			if (cnt == shark_size) {
				shark_size++;
				cnt = 0;
			}
		}

	}
	
	cout << sec;
}

void is_available(int r, int c, int cnt, int min_dist) {
	
	visit[r][c] = true;

	//타겟 도달 시, distance 업데이트 
	if ((target_r == r) && (target_c == c)) {
		available = true;
		if (dist > cnt) dist = cnt;
		return;
	}

    //찾은 최소거리보다 cnt가 넘어가면 더이상 탐색하지 않음.
	if (available && (cnt >= min_dist)) return;

	//4방향 모두 갈 곳 없음. 종료.
	bool done = true;
	for (int dir = 0; dir < 4; dir++) {
		int tmp_r = r + dx[dir];
		int tmp_c = c + dy[dir];

		if (tmp_r < 1 || tmp_r > n || tmp_c < 1 || tmp_c > n) continue;
		if (!visit[tmp_r][tmp_c]) done = false;
	}
	if (done) return;

	//4방향 탐색
	for (int dir = 0; dir < 4; dir++) {
		int tmp_r = r + dx[dir];
		int tmp_c = c + dy[dir];
        
		if (tmp_r < 1 || tmp_r > n || tmp_c < 1 || tmp_c > n)
			continue;

		if (shark_size < map[tmp_r][tmp_c]) {
			visit[tmp_r][tmp_c] = true;
			continue;
		}

		if (!visit[tmp_r][tmp_c]) {
			is_available(tmp_r, tmp_c, cnt + 1, min_dist);
			visit[tmp_r][tmp_c] = false;
		}
	}
}

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

문제

문제

출처

ICPC

DFS 방식도 가능할까요?

moonstar114 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말