글 읽기 - 알고리즘 다 짰는데 큰 오류가 있네요,,,! 제발 도와주세요

jsshin_17 4년 전 0

테트로미노 알고리즘을 DFS를 안쓰고 직접 짜보았습니다.

case 1, case 2, case 3으로 나누어 테트로미노의 경우를 다 만들어보았는데요,

우선 case 1은 현재 위치의 값을 더하고 오른쪽이나 아래쪽 칸으로 움직이는 것.

case 2는 현재 위치에서 현재 위치의 값과 오른쪽 혹은 아래쪽 둘 중 하나의 칸을 더하고 위치는 아래쪽 혹은 오른쪽(더하는 칸과 반대) 칸으로 움직이는 것(이렇게 하면 현재 위치와 오른쪽, 아래 세칸의 칸을 다 더할 수 있기 때문에 2x2짜리 정사각형 블록 등을 만들 수 있음) -> case1에서는 아래쪽이나 오른쪽 둘 중 하나만 더 할 수 있기 떄문에 중복 x

case 3은 현재 위치에서 현재 위치의 값은 더하지 않고 오른쪽 혹은 아래쪽 둘 중 하나의 칸을 더하고 위치는 아래쪽 혹은 오른쪽(더하는 칸과 반대) 칸으로 움직이는 것(이렇게 하면 현재 위치의 아래와 오른쪽 값을 더하고 시작하므로 ㅗ, ㅓ 등의 케이스와 지그재그의 케이스 등을 커버 가능)

이렇게 알고리즘을 짜 보았습니다.

여기서 문제는... 이 세 케이스를 모두 돌아야 하는데 각각 if문으로 만들고 안에서 리턴을 해주는 형태로 하였기 떄문에 맨 처음에 써주는 If문만 돌고 아래 if문들로 들어가지가 않습니다. DFS로도 해결할 수 있지만 제 알고리즘으로 맞았습니다를 보고싶어서..... 너무 오랜만에 풀어봤더니 감이 안잡히네요 이 if문들을 어떻게 수정해야 세 케이스가 다 돌아갈 수 가 있을까요?ㅜㅜ 부탁드립니다. 뾰족한 수가 안떠올라요

#include <iostream>
using namespace std;
int arr[500][500] = {0, };
int max(int a, int b){
    if(a>b)
        return a;
    else
        return b;
}

int tetro(int i, int j, int cnt, int sum, int (*arr)[500], int N, int M) {
    int case_1, case_2, case_3;
    if (((i != N - 1) && (cnt < 4)) || ((j != M - 1) && (cnt < 4))) {
        return max(tetro(i + 1, j, cnt + 1, sum + arr[i][j], arr, N, M),
                tetro(i, j + 1, cnt + 1, sum + arr[i][j], arr, N, M));
    }
    else if ((i != N - 1) && (j != M - 1) && (cnt < 3)) {
        return max(tetro(i + 1, j, cnt + 2, sum + arr[i][j + 1] + arr[i][j], arr, N, M),
                tetro(i, j + 1, cnt + 2, sum + arr[i + 1][j] + arr[i][j], arr, N, M));
    }
    else if ((i != N - 1) && (j != M - 1) && (cnt == 1)) {
        return max(tetro(i + 1, j, cnt + 1, sum + arr[i][j + 1], arr, N, M),
                tetro(i, j + 1, cnt + 1, sum + arr[i + 1][j], arr, N, M));
    }
    if(cnt==4){
        return sum+arr[i][j];
    }
}

int main(){
	int N, M;
	int temp;
	int max=0;
	scanf("%d %d", &N, &M);
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			scanf("%d", &arr[i][j]);
		}
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			temp = tetro(i, j, 1, 0, arr, N, M);
			if(temp>max){
				max = temp;
			}
		}
	}
	printf("%d\n", max);
}

palilo 4년 전 0

이런 방법을 말씀하시는건가요

int tetro(int i, int j, int cnt, int sum, int (*arr)[500], int N, int M) {
    int case_1, case_2, case_3;
    
    int ret;    ///
    
    if (((i != N - 1) && (cnt < 4)) || ((j != M - 1) && (cnt < 4))) {
        ret = max(tetro(i + 1, j, cnt + 1, sum + arr[i][j], arr, N, M),
                tetro(i, j + 1, cnt + 1, sum + arr[i][j], arr, N, M));
    }
    else if ((i != N - 1) && (j != M - 1) && (cnt < 3)) {
        ret = max(tetro(i + 1, j, cnt + 2, sum + arr[i][j + 1] + arr[i][j], arr, N, M),
                tetro(i, j + 1, cnt + 2, sum + arr[i + 1][j] + arr[i][j], arr, N, M));
    }
    else if ((i != N - 1) && (j != M - 1) && (cnt == 1)) {
        ret = max(tetro(i + 1, j, cnt + 1, sum + arr[i][j + 1], arr, N, M),
                tetro(i, j + 1, cnt + 1, sum + arr[i + 1][j], arr, N, M));
    }
    if(cnt==4){
        ret = sum+arr[i][j];
    }
    return ret;    ///
}

dotoleeoak 4년 전 0

1. case1에서 런타임 에러가 날 것 같네요. (i, j)가 (N-1, M-1) 범위를 벗어나지 않게 처리를 해주세요.

2. 각 if문 실행 시 바로 return하지 말고 값을 저장하면 3개의 if를 모두 실행할 수 있습니다.

3. else if로 연결하면 하나의 if가 실행되면 나머지 if문들은 처리되지 않고 건너뜁니다.

4. <algorithm>헤더에 이미 max 함수가 구현되어 있습니다.

5. tetro 함수인자 중 arr, N, M은 전역변수로 선언해두면 굳이 인자로 전달할 필요가 없습니다.

제가 코드를 완전히 이해하진 못해서 그런데 ┛모양의 블럭도 처리가 되는건지 모르겠네요...

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

문제

문제

출처

ICPC

알고리즘 다 짰는데 큰 오류가 있네요,,,! 제발 도와주세요

jsshin_17 4년 전 0

palilo 4년 전 0

dotoleeoak 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말