글 읽기 - 2178 DFS문제좀 ㅠ

kdhsong 9년 전 0

예제랑 다른예제다넣어보ㅏ도 잘돌아가는데 왜 틀렸다고나오는지모르겠어여ㅠㅠ

혹시 안되는 경우가있으면 가르쳐주시면 정말감사할게여 ㅠ

#include <stdio.h>

char arr[101][101];
int visit[101][101];

int result = 9999;
int n,m;

void DFS(int i,int j,int num){
	
	if(i == n-1 && j == m-1){
		if(result > num){
			result = num;
			return ;
		}
		
	}
	if(j-1 >= 0 && visit[i][j-1] != -1)
	{
		if(arr[i][j-1] == '1'){
			visit[i][j-1] = -1;
			
			DFS(i,j-1,num+1);
		}
	}
	if(j+1 < m && visit[i][j+1] != -1){
		if(arr[i][j+1] == '1'){
			visit[i][j+1] = -1;
			
			DFS(i,j+1,num+1);
		}
	}
	if(i-1 >= 0 && visit[i-1][j] != -1){
		if(arr[i-1][j] == '1'){
			visit[i-1][j] = -1;
			
			DFS(i-1,j,num+1);
		}
	}
	if(i+1 < n && visit[i+1][j] != -1){
		if(arr[i+1][j] == '1'){
			visit[i+1][j] = -1;
	
			DFS(i+1,j,num+1);
		}
	}
	return;
}

int main(){

	scanf("%d %d",&n,&m);
	if(n < 2 || n > 100 || m < 2 || m > 100)
		return 0;
	int i,j;

	for(i = 0; i < n; i++){
		scanf("%s",arr[i]);
	}
	
	visit[0][0] = -1;
	DFS(0,0,1);
	
	printf("%d",result);
}

pichulia 9년 전 1

5 5

11100

00100

11100

10100

11111

이 경우 9가 나와야 할텐데 13이 출력될거 같네요..테스트는 안해봤지만..

DFS 끝나기 전에

visit[i-1][j] = -1;

를 원상태로 복귀시키는 코드가 있어야 할거 같습니다.

...그러면 정상적으로 TLE를 받겠죠

amugeona 9년 전 1

마지막 한마디에서 진심이 느껴지네요...

DFS 접근은 아니라도 저렇게 얘기할수 있군요...

kdhsong 9년 전 0

제가 푼방식이 아에 틀린건가여 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

WeissBlume 9년 전 1

이 문제는 bfs로 해결하는 쪽이 dfs보다 쉬울 수도 있어요(bfs는 최단경로가 보장되므로).

그러니 일단 bfs로 맞고 dfs로 해결한 사람의 코드를 보는것도 추천합니다.

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

문제

문제

출처

ICPC

2178 DFS문제좀 ㅠ

kdhsong 9년 전 0

pichulia 9년 전 1

amugeona 9년 전 1

kdhsong 9년 전 0

WeissBlume 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말