글 읽기 - 예외가 무엇일까요???

kcl5363 6년 전 0

틀렸다는 예외가 뭔지 알 수있을까요?

#include <iostream>

using namespace std;

int BO[101][101];
bool check[101][101];
long long cnt;

void DFS(int x,int y,int num) {
	if (BO[x][y] == 0) {
		cnt++; 
		return;
	}
	check[x][y] = true;
	int k = x + BO[x][y];
	int l = y + BO[x][y];
	if (k <= num) {
		if (check[k][y] == false) {
			DFS(k, y, num);
		}
	}
	if (l <= num) {
		if (check[x][l] == false) {
			DFS(x, l, num);
		}
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> BO[i][j];
		}
	}
	DFS(1, 1, n);
	cout <<cnt<< "\n";
	return 0;
}

djm03178 6년 전 1

2가지 정도가 잘못됐습니다.

가장 오른쪽 아래 칸이 아니라도 0이 써있을 수 있습니다. 0이 나타났다고 cnt가 증가되면 안 됩니다.
이미 방문한 칸도 또 갈 수 있습니다. 다음과 같은 케이스의 답은 2여야 하는데 1이 출력됩니다.

kcl5363 6년 전 0

다시 짜봤는데 메모리초과가 뜹니다 방도가 없을까요????

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int BO[101][101];
unsigned long long DP[101][101];

void BFS(int N) {
	queue<pair<int,int>>que;
	que.push(make_pair(1, 1));
	DP[1][1] = 1;
	while (!que.empty()) {
		int x = que.front().first;
		int y = que.front().second;
		int dx[2] = { x,x + BO[x][y] };
		int dy[2] = { y + BO[x][y],y };
		que.pop();
		for (int i = 0; i < 2; i++) {
			if (0 < dx[i] && 0 < dy[i] && dx[i] <= N&&dy[i] <= N) {
				
				if (DP[dx[i]][dy[i]] == 0)
					DP[dx[i]][dy[i]] = DP[x][y];
				else
					DP[dx[i]][dy[i]] += DP[x][y] ;
				if (BO[dx[i]][dy[i]]!= 0)
					que.push(make_pair(dx[i], dy[i]));
				
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> BO[i][j];
		}
	}
	BFS(N);
	cout << DP[N][N]<<"\n";

	return 0;
}

djm03178 6년 전 0

이 코드라면 이미 갔던 칸을 또 방문하고, 다른 칸에서도 또 방문하고, 또 이 칸에서 두 방향으로 뻗어나가고... 를 반복하니 큐에 최대 O(2^n)개가 들어가겠죠.

이 문제는 BFS가 아니라 DP로 풀어야 됩니다.

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

문제

문제

출처

ICPC

예외가 무엇일까요???

kcl5363 6년 전 0

djm03178 6년 전 1

kcl5363 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말