글 읽기 - 1278_dfs로 푼 미로탐색 질문이요

mbc0481 4년 전 0

4개 테스트 케이스는 모두 통과했는데 틀렸습니다가 나오네욤 -3-

어디가 틀렸는지 잘 모르겠습니다 ... 못찾겠어요 ㅜㅜ 게시판 보니깐 dfs로 풀면 안된다고 들어서 bfs버전도 봤는데 별 차이가 없는것 같더라구요.

무슨 차이가 있는건가요??

혹시 아래 코드 반례좀 찾아주실분 계신가요 ? ㅜㅜ

#include <iostream>
#include <queue>
#define MAX 1000000
using namespace std;

int N, M, minValue = MAX;
int arr[101][101];
int direct[3][2] = { {1, 0}, {0, 1}, {0, -1} };

//DFS로 풀이
//테스트 케이스 답은 나오지만 효율성이 문제인지 정답 체크가 안됨
void dfs(int x, int y, int cnt) {
	
	if (arr[x][y] == 0) return ;
    
    //최솟값을 구해서 출력
	if (x >= M - 1 && y >= N - 1) {
		if (cnt < minValue) {
            //마지막 arr[M-1][N-1]은 방문하지 않으므로 1을 추가
			minValue = cnt+1;
			return ;
		}
	}
	arr[x][y] = 0;
	/*
    cout << "cnt : " << cnt << "\n";

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << arr[j][i] << " ";
		}
		cout << "\n";
	}
    */
    
	for (int i = 0; i < 3; i++) {
		int nextX = x + direct[i][0];
		int nextY = y + direct[i][1];
        
		if (arr[nextX][nextY] == 1) {
			dfs(nextX, nextY, cnt+1);
		}
	}
}


int main() {
	//INPUT
	cin >> N >> M;
	if (N > 100 || N < 2 || M >100 || M < 2) return 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &arr[j][i]);
		}
	}

	dfs(0, 0, 0);
	
    //OUTPUT
	cout << minValue;
    
	return 0;
}

ha_ram 4년 전 2

https://www.acmicpc.net/board/...

이 글을 읽어보시고 왜 bfs로 해야하는지 다시 생각해 보시길 바랍니다..

그리고 위의 코드에 대한 반례도 드립니다.

5 6

111111

100001

100011

100010

011111

답 : 12

mbc0481 4년 전 1

//ha_ram

감사합니다 ㅎㅎ

그래프 문제 어렵네요 ㅜㅜ

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

문제

문제

출처

ICPC

1278_dfs로 푼 미로탐색 질문이요

mbc0481 4년 전 0

ha_ram 4년 전 2

mbc0481 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말