글 읽기 - 침투문제 질문드립니다..(dfs 인듯요)

leedh2004 6년 전 0

icpc 예전 문제인데 어디가 잘못됬는지 모르겠습니다.

우선 코드 설명 대충하자면

string으로 받은 값을 배열로 넣고

2차원 배열에 배열판을 생성후에 ( (y,x)이고 (0,0)이 맨왼쪽위점, y증가할수록 밑으로 내려가고, x증가할수록 오른쪽 )

맨 위에서 0인 곳을 기준으로 탐색을 시작하고, 이미 탐색한 곳은 가지 않는걸로 구현하고 싶어서

재귀함수를 사용해서 구현해봤는데 백준 입력 예제에서는 올바른 출력이 나오는데

틀렸다고 나오네요.. 이제 막 알고리즘 공부하는 초보라 어디가 잘못됬는지 모르겠습니다.

그리고 혹시 손댈곳이 있거나 더 효율적으로 풀 수 있는 방법이나 알고리즘이름이라도 알려주시면 감사하겠습니다ㅠㅠ

감사합니다.

#include <iostream>
#include <string>
#include <cstdlib>
#define TURE 1
#define FALSE 0
using namespace std;


int arr[1000][1000];
int used[1000][1000] = { 0, };

using namespace std;

void move(int(*arr)[1000], int x, int y, int(*used)[1000], int *c);

int height;
int row;

int main() {

	string str;
	cin >> height >> row;
	int c = 0, s = 0, check[1] = { 0 };

	for (int i = 0; i < height; i++) {
		cin >> str;
		for (int j = 0; j < row; j++) {
			arr[i][j] = str[j] - '0';
		}
	}
	
	for (int i = 0; i < row; i++) {
		if (arr[0][i] == 0) {
			move(arr, i, 0, used, check);
		}
	}
	
	if (check[0] == 1)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	return 0;
}

void move(int(*arr)[1000], int x, int y, int(*used)[1000], int *c) {
	
	if (y + 1 == height) {
		c[0] = 1;
		return;
	}

	if (y + 1 < height) {
		if (arr[y + 1][x] == 0 && used[y + 1][x] == 0) {
			used[y + 1][x] = 1;
			move(arr, x, y + 1, used, c);
		}
		if (x + 1 < row) {
			if (arr[y][x + 1] == 0 && used[y][x + 1] == 0) {
				used[y][x + 1] = 1;
				move(arr, x + 1, y, used, c);
			}
		}
		if (x > 0) {
			if (arr[y][x - 1] == 0 && used[y][x - 1] == 0) {
				used[y][x - 1] = 1;
				move(arr, x - 1, y, used, c);
			}
		}
	}
}

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

문제

문제

출처

ICPC

침투문제 질문드립니다..(dfs 인듯요)

leedh2004 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말