• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

5-X 시간초과 질문입니다!

24.02.29 23:20 작성 24.02.29 23:27 수정 조회수 87

1

https://www.acmicpc.net/source/74215560
안녕하세요 ㅠ
시간 초과가 왜 나는 건지 잘 모르겠습니다...

제가 계산한 것에 따르면

1. 모든 경우의수 4^8

2. 기준 방향 설정 x4

3. 기준 방향을 중심으로 4방향 탐색 후 감시 방향 기록 (최대 3방향, 가로,세로 8칸) x (64+64(복사))


=> 34백만 정도

맞왜틀일까요..ㅠㅠ

답변 1

답변을 작성해보세요.

0

안녕하세요 민아님 ㅎㅎ

시간복잡도 계산은 맞긴하지만.. 코드상 효율적이지 않은 부분 때문에 시간초과가 뜨는 것 같습니다.

	for (int d = 0; d < 4; d++) {
		if (v == 1 && dir != d) continue;
		if (v == 2 && ((dir != d) && dir != ((d + 2) % 4))) continue;
		if (v == 3 && ((dir != d) && (dir != (d + 1) % 4)))continue;
		if (v == 4 && dir == d)continue;
		int ny = y;
		int nx = x;
		while (true) {
			ny += dy[d];
			nx += dx[d];
			if (ny >= N || ny < 0 || nx >= M || nx < 0) break;
			if (board[ny][nx] == 6)break;
			if (board[ny][nx] == 0) {
				n_board[ny][nx] = 10;
			}
		}

	}

	if (n+1 >= CCTV.size()) {

지금 코드 구조를 보면 기저사례가 밑에 있죠? 그러면 계산하지 않아도 될 부분에서 계산을 무조건 하게 됩니다. n + 1이라면 계산을 안해도 되는 것 아닌가요? 그 때도 해당 로직이 수행되는 것이죠.

기저사례는 항상 함수 맨 위쪽 부분에 있어야 합니다.

 

그리고... 제생각에는

	for (int i = 0; i < 4; i++) {
		find_MinNum(0, i, 0, board);
	}

초기에 이부분 때문에 꼬인 것 같은데요.

 

	for (int i = 0; i < 4; i++) {
		if (CCTV[n+1].first == 2 && (i == 2 || i == 3)) return 0;
		find_MinNum(n+1, i, cnt, n_board);
	}

이렇게가 아니라

 

find자체를

int find_MinNum(int n, int dir, int cnt, int _board[8][8]) {

여기서

int find_MinNum(int n, int cnt, int _board[8][8]) {

이런식으로 바꾸면서 idx를 안넘기는 식으로 바꿔야 합니다.

그러면 초기에 4번호출하는게 아니라 1번 호출할 수 있겠죠?

4번 호출 -> 4방향확인 -> ...

에서...

1번 호출 -> 4방향확인 -> ...

 

로 바꾸는 것이죠.

 

제가 민아님 코드를 다듬어 봤는데요. ㅎㅎ

참고 부탁드립니다.

모듈화 + updateboard부분 로직 수정 + 매개변수 수정

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int board[8][8];
int N, M;
int min_cnt = 2e9;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, -1, 0, 1};
typedef pair<int, int> pii;

vector<pair<int, pii>> CCTV;

void updateBoard(int dir, int y, int x, int _board[8][8]) {
    while (true) {
        y += dy[dir];
        x += dx[dir];
        if (y < 0 || y >= N || x < 0 || x >= M || _board[y][x] == 6) break;
        if (_board[y][x] <= 0) _board[y][x] = -1;
    }
}

void find_MinNum(int index, int _board[8][8]) {
    if (index == CCTV.size()) {
        int cnt = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (_board[i][j] == 0) ++cnt;
            }
        }
        min_cnt = min(min_cnt, cnt);
        return;
    }

    int type = CCTV[index].first;
    int x = CCTV[index].second.second;
    int y = CCTV[index].second.first;
    int temp_board[8][8];
    
    for (int dir = 0; dir < 4; ++dir) {
        copy(&_board[0][0], &_board[0][0] + 8*8, &temp_board[0][0]);

        if (type == 1) {
            updateBoard(dir, y, x, temp_board);
        } else if (type == 2) {
            updateBoard(dir, y, x, temp_board);
            updateBoard((dir+2)%4, y, x, temp_board);
        } else if (type == 3) {
            updateBoard(dir, y, x, temp_board);
            updateBoard((dir+1)%4, y, x, temp_board);
        } else if (type == 4) {
            updateBoard(dir, y, x, temp_board);
            updateBoard((dir+1)%4, y, x, temp_board);
            updateBoard((dir+2)%4, y, x, temp_board);
        } else if (type == 5) {
            updateBoard(dir, y, x, temp_board);
            updateBoard((dir+1)%4, y, x, temp_board);
            updateBoard((dir+2)%4, y, x, temp_board);
            updateBoard((dir+3)%4, y, x, temp_board);
        }
        find_MinNum(index + 1, temp_board);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
            if (board[i][j] >= 1 && board[i][j] <= 5)
                CCTV.push_back({board[i][j], {i, j}});
        }
    } 
    find_MinNum(0, board);
    cout << min_cnt;
    return 0;
}


또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.


박밍님의 프로필

박밍

질문자

2024.03.01

안녕하세요 큰돌님..!
큰돌님께서 고쳐주신 코드처럼 수정해도 시간초과가 나서 이것저것 바꾸면서 돌려보니까
제가 int 값 반환 함수로 만들어서 시간이 더 걸렸던 것 같더라구요..!!

void find_MinNum으로 했더니 제가 작성한 코드도 바로 돌아갔습니다

강의에서 알려주셨을 수도 있지만... 저의 뇌 속에는 없어서 혹시 추후에 도움이 될까 해서 댓글 남깁니다^.T

비전공자여서 주변에 도움 받을만한 곳이 많이 없는데 많이 도움 받고 있어요. 감사합니다 ㅎㅎ!!

통과한 코드도 링크 올리겠습니다..!
++기저 조건은 처음에는 맨 위에 썼었는데 시간 복잡도 줄이려고 이것저것 하다가 아래로 내려갔었습니다..ㅎ...

https://www.acmicpc.net/source/74231473

안녕하세요 민아님 ㅎㅎ

정말 휴일 - 삼일절인데도 열심히 하시네요 ㅎㅎ

혹시나 해서 들어와봤는데 답글달린거 보고 정말 감동 먹었습니다.. ㅎㅎ

앞으로도 이렇게 꾸준히 열심히 부탁드립니다. 꼭 성과가 있으실거에요.

 

제가 int 값 반환 함수로 만들어서 시간이 더 걸렸던 것 같더라구요..!!

>> 이건 아닙니다. void -> int로 한다고 해서 시간이 더 걸리지는 않습니다.

제가 민아님 고치신 코드 기반으로 다시 int타입으로 고쳐봤는데요. 통과합니다.

http://boj.kr/de6bc72899f44a8db28485fd74a6f188

 

++기저 조건은 처음에는 맨 위에 썼었는데 시간 복잡도 줄이려고 이것저것 하다가 아래로 내려갔었습니다..ㅎ...

>> 기저는 무조건 위에 있어야 되긴 해요 ㅠㅠ..

이는 다음과 같은 부분 때문인데요.

1.효율성

기저 -> 재귀함수를 종료시킵니다. 이를 상단에 배치하면 함수가 더 복잡한 논리(메인로직)로 진행해야 하는지 재귀 호출로 진행해야 하는지 더 빠르게 판단하고 종료시킬 수 있습니다. -> 이는 효율적인 코드가 됩니다.

 

2.무한재귀방지
재귀함수는 반복적으로(재귀적으로) 실행되다 종료를 해야 합니다. 이 때 메인로직이 재귀보다 더 앞에 있어버리면 일단은 메인로직이 먼저 실행되기 때문에 무한재귀가 될 가능성이 높은 코드가 됩니다.

 

  1. 논리적 흐름
    보통 재귀함수는 어떤 문제를 쪼개어서 더 작은 사례에 대한 해결책을 푸는 방법의 해결책 중 하나로 씁니다. 이 때문에 재귀함수의 매개변수 자체가 계속 작게 되다가 결국 1 또는 문제에서 주어진 작은 최솟값이 되버리는 것이죠. 이 때 종료를 시켜야 되기 때문에 해당 매개변수가 작아졌다? 혹은 커졌다 -> 종료 해야 하기 때문에 맨 앞에 있어야 합니다.( + 1을 하면서 index가 커져서 최댓값이 되는 경우도 마찬가지입니다. 문제에서 주어진 어떠한 범위를 벗어날 때 종료를 반드시 시키는 코드로 만들어야 합니다.)

     

감사합니다.