글 읽기 - 어느 부분에서 잘못된지 궁금해서 질문올립니다!

smiley_bin 4년 전 0

반례가 된다고 생각하는 것도 다 해보았는데 실패합니다가 떠서 질문합니다 ㅠ.ㅠ 어느 부분에서 오류가 있는걸까요!

#include<iostream>
#include<algorithm>
using namespace std;

char map[500][500];
int visit[500][500];
int N;
char mola[5] = "MOLA";
int dx[2] = { 1,0 };
int dy[2] = { 0,1 };
int result = 0;

bool check(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < N) return true;
return false;
}

void DFS(int x, int y, int cnt, int total_cnt) {
if (!check(x, y)) return;
if (map[x][y] == mola[cnt]) {
if (cnt == 3) {
cnt = -1;
total_cnt++;
result = max(result, total_cnt);
}
for (int i = 0;i < 2;i++) {
    int next_x = x + dx[i];
    int next_y = y + dy[i];
    if (visit[next_x][next_y] != 1) {
    visit[next_x][next_y] = 1;
    DFS(next_x, next_y, cnt + 1, total_cnt);
    visit[next_x][next_y] = 0;
            }
        }
    }
}

int main() {
cin >> N;
for (int i = 0;i < N;i++) {
    for (int j = 0;j < N;j++) {
        cin >> map[i][j];
        }
    }
    
for (int i = 0;i < N;i++) {
    for (int j = 0;j < N;j++) {
        int total_cnt = 0;
        visit[i][j] = 1;
        DFS(i, j, 0, total_cnt);
        visit[i][j] = 0;
    }
}

cout << result;
return 0;

}​​

sait2000 4년 전 2

몰라를 못 만든다고 때려치면 안 됩니다

in:
5
MOLAQ
OLAQM
LAQMO
AQMOL
QMOLA

out:
2

smiley_bin 4년 전 0

아하 시작점에서 끝까지 갔을 때 그 전체 문자열에서 몰라를 찾는 문제였군요 ㅠ,ㅠ 감사합니다 !

smiley_bin 4년 전 0

말씀해주신대로 문제 이해후에 코드를 수정했는데 아쉽게도 시간 초과가 뜨네요 ㅠ,ㅠ 줄일 방법이 없을까요 ,,

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

char map[500][500];
int visit[500][500];
int N;
string mola = "MOLA";
int dx[2] = { 1,0 };
int dy[2] = { 0,1 };
int result = 0;


bool check(int x, int y) { //범위 확인 함수
	if (x >= 0 && x < N && y >= 0 && y < N) return true;
	return false;
}

void DFS(int x, int y,int cnt,int total_cnt) {
	if (map[x][y] == mola[cnt]) cnt++;
	else cnt = 0;

	if (cnt == 4) {
		total_cnt++;
		cnt = 0;
	}

	if (x==N-1&&y==N-1) { 
		result = max(result,total_cnt); //제일 길게 나온 MOLA의 개수를 설정 
		return;
	}

	for (int i = 0;i < 2;i++) { 
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		if (visit[next_x][next_y] != 1 && check(next_x,next_y)) { 
			visit[next_x][next_y] = 1; 
			DFS(next_x, next_y,cnt,total_cnt); 
			visit[next_x][next_y] = 0;
		}
	}
}


int main() {
	cin >> N;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			cin >> map[i][j];
		}
	}

	DFS(0,0,0,0);

	cout << result;
	return 0;
}

sait2000 4년 전 1

그냥 DFS로는 너무 크고 중복되는 계산이 많아서 안 될 겁니다. DP를 해보세요.

smiley_bin 4년 전 0

아직 코딩에 미숙해서 그런데 혹시 어느 부분에 DP를 적용하면 좋을까요 ㅠ,ㅠ ..

sait2000 4년 전 2

예를 들어 어떤 칸까지 가는 방법이 여러가지가 있는데 어떤 방법은 몰라를 2개 줍고 어떤 방법은 1.75(?)개 줍고 어떤 방법은 2.75개 줍는다고 해봅시다. 그럼 그 뒤를 알아봐야할 유일한 경로는 2.75개라는 걸 알 수 있습니다. 따라서 각 칸까지 왔을 때 주울 수 있는 몰라의 최대 개수를 DP하면 됩니다.

smiley_bin 4년 전 0

감사합니다 많이 배웠습니다:>

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

문제

문제

출처

ICPC

어느 부분에서 잘못된지 궁금해서 질문올립니다!

smiley_bin 4년 전 0

sait2000 4년 전 2

smiley_bin 4년 전 0

smiley_bin 4년 전 0

sait2000 4년 전 1

smiley_bin 4년 전 0

sait2000 4년 전 2

smiley_bin 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말