글 읽기 - 틀렸습니다가 나오는 DFS입니다.

dong_s 6년 전 1

안녕하세요 ㅠㅠ 알고리즘 초짜 열공중인 학생입니다.

BFS문제이지만, 우선 DFS로 짜려고 했습니다.

그런데 틀렸습니다라는 에러가 떴구요.

타 질문글들을 읽었으나 BFS인 경우가 많고, 답글에 반례로 나온 케이스들을 돌렸을때도 정상적으로 나와서 어디서 틀렸나 감이 안옵니다.

#include <iostream>
#include <string>
#include <climits>
#include <cstring>
using namespace std;
int n, m;
int maze[102][102];
bool visited[102][102];
int movex[4] = {0,1,0,-1};
int movey[4] = {1,0,-1,0};
int mini = INT_MAX;

void dfs(int x,int y, int count){
    if(x == n && y == m){
        if(mini > count)
            mini = count;
    }
    if(maze[x][y]==0||visited[x][y]){
        return;
    }
    visited[x][y] = true;
    for (int i = 0; i < 4; ++i){
        dfs(x+movex[i],y+movey[i], count + 1);
    }
}

int main(int argc, char const *argv[])
{
    string s;
    cin >> n >> m;
    memset(maze, 0, sizeof(maze));
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        for (int j = 1; j <= m; ++j) {
            maze[i][j] = s[j-1] - 48;
        }
    }
    memset(visited, false, sizeof(visited));
    dfs(1,1,1);
    cout << mini;
    return 0;
}

lyzqm 6년 전 2

일단 이문제는 최단거리를 구하는 문제로 bfs를 풀면 훨씬 쉽게풀립니다.

위의 코드의 문제점은 일단 2가지가 있습니다.

1. 범위 설정 : x,y값이 0이하 또는 범위 밖일 경우의 조건이 없습니다.

2. dfs탐색은 순서에따라서만 이동하기 때문에 운이 좋으면 최단거리로 이동할 수 있겠지만 값이 제대로 갱신되지 않을경우가 생깁니다.

예를 들어 x=2,y=2에서 -> (2,3) -> (3,3) -> (3,4) -> (4,4) 로 이동하는데 10의 cost가 소모됬다고 생각해봅시다.

하지만 x=2,y=2 -> (3,2) -> (3,3) -> (3,4)->(4,4)로 이동하는데 5의 cost가 소모될 수도있습니다. 위의 코드에서는 (3,3)에 대한 방문체크를 위의 탐색에서 이미 했기 때문에 새로운 값이 갱신되지 않을 수 있죠..

방문배열을 없애고 dist[i][y] ( = (1,1)에서 (i,y)까지의 거리) 배열을 수정해서 풀은 소스 올려드립니다.

다익스트라 알고리즘도 찾아보시면 좋을 거같네요.

#include <iostream>
#include <string>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int maze[102][102];
int movex[4] = { 0, 1, 0, -1 };	
int movey[4] = { 1, 0, -1, 0 };
int dist[102][102];
void dfs(int x, int y){
	if (x == n && y == m){
		return;
	}
	for (int i = 0; i < 4; ++i){
		if (x <= 0 || x > n || y <= 0 || y > m || maze[x][y] == 0) continue;
		if (dist[x + movex[i]][y + movey[i]] > dist[x][y] + 1){
			dist[x + movex[i]][y + movey[i]] = dist[x][y] + 1;
			dfs(x + movex[i], y + movey[i]);
		}
	}
	return;
}

int main(int argc, char const *argv[])
{
	string s;
	cin >> n >> m;
	memset(maze, 0, sizeof(maze));
	for (int i = 1; i <= n; ++i) {
		cin >> s;
		for (int j = 1; j <= m; ++j) {
			maze[i][j] = s[j - 1] - 48;
			dist[i][j] = INT_MAX;
		}
	}
	dist[1][1] = 0;
	dfs(1, 1);
	printf("%d\n", dist[n][m] + 1);
	return 0;
}

dong_s 6년 전 0

정말 감사합니다 :)

BFS와 다익스트라를 사용해서 문제 해결해보았습니다.

DFS코드를 보니 이해가 아주 잘되네요 !!

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