인프런 커뮤니티 질문&답변

안녕하세요 민아님 ㅎㅎ

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

	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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.