[DFS] 테트로미노 - 백준 14500번

14500번: 테트로미노

풀이

1) DFS 로 풀 수 있는것들

• 상하좌우 인접한 블럭으로 이동하면서 최댓값을 구함

    const int dx[] = {1, -1, 0, 0};
    const int dy[] = {0, 0, -1, 1};
    for(int i = 0; i < 4; i++){
    	int nx = x + dx[i];
      int ny = y + dy[i];
    }
  

• 주의) 방문한 블럭으로 다시 돌아갈 수 없음

    if(prev_x == nx && prev_y == ny) {
        continue;
    }
  

2) DFS 로 못 푸는 것

void makeWOOShape(int x, int y, int answer) {
  // 전제 : 맵의 범위를 넘어가지 않는 선에서
    
  // 'ㅜ' 모양 만들기
  // 'ㅏ' 모양 만들기
  // 'ㅓ' 모양 만들기
  // 'ㅗ' 모양 만들기
}

참고: https://velog.io/@christer10/알고리즘-백준-14500-테트로미노

실수 (시간 초과)

vector<vector<int>>&와 같이 참조를 사용할 때와 복사본을 사용할 때의 성능 차이는 큰 영향을 미칠 수 있습니다. 이 차이는 주로 두 가지 이유로 발생합니다:

1. 메모리 사용과 복사 비용

• 참조 (vector<vector<int>>\&):
  • 메모리 사용: 참조를 사용하면 원본 객체를 직접 참조하므로 추가적인 메모리를 사용하지 않습니다.
  • 성능: 객체의 복사 없이 직접 접근하므로 메모리 복사와 관련된 비용이 없습니다. 이는 특히 큰 데이터 구조체에서 성능을 크게 향상시킬 수 있습니다.
• 복사본 (vector<vector<int>>):
  • 메모리 사용: 복사본을 사용하면 원본 객체의 복사본이 생성되므로 메모리 사용이 증가합니다.
  • 성능: 데이터 복사에 따른 추가 비용이 발생합니다. 특히 큰 데이터 구조체에서는 이 복사 비용이 상당할 수 있습니다.

2. 함수 호출 시 성능 차이

• 참조를 사용할 때:
  • 시간 복잡도: 참조를 사용하면 함수 호출 시 데이터 복사 비용이 없으므로 함수의 실행 시간이 단축됩니다. 함수 내에서 데이터 변경이 필요할 경우, 원본 데이터가 직접 수정됩니다.
  • 효율성: 대규모 데이터 처리에서 성능 향상을 제공합니다.
• 복사본을 사용할 때:
  • 시간 복잡도: 함수 호출 시 객체의 복사본이 생성되므로, 객체가 클 경우 복사 비용이 시간 복잡도에 추가됩니다.
  • 효율성: 데이터 구조체가 클수록 성능 저하가 커집니다.

예제와 성능 차이

간단한 예를 통해 성능 차이를 살펴보겠습니다:

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;

// 참조를 사용하는 함수
void processReference(vector<vector<int>>& mat) {
    for (int i = 0; i < mat.size(); ++i) {
        for (int j = 0; j < mat[i].size(); ++j) {
            mat[i][j] += 1;
        }
    }
}

// 복사본을 사용하는 함수
void processCopy(vector<vector<int>> mat) {
    for (int i = 0; i < mat.size(); ++i) {
        for (int j = 0; j < mat[i].size(); ++j) {
            mat[i][j] += 1;
        }
    }
}

int main() {
    int n = 1000;
    int m = 1000;
    vector<vector<int>> matrix(n, vector<int>(m, 0));

    auto start = chrono::high_resolution_clock::now();
    processReference(matrix);
    auto end = chrono::high_resolution_clock::now();
    cout << "Reference time: " 
         << chrono::duration_cast<chrono::microseconds>(end - start).count()
         << " microseconds" << endl;

    start = chrono::high_resolution_clock::now();
    processCopy(matrix);
    end = chrono::high_resolution_clock::now();
    cout << "Copy time: " 
         << chrono::duration_cast<chrono::microseconds>(end - start).count()
         << " microseconds" << endl;

    return 0;
}

이 코드에서 processReference는 참조를 사용하고, processCopy는 복사본을 사용합니다. processReference가 더 빠르게 실행되는 것을 확인할 수 있을 것입니다.

결론

참조 (vector<vector<int>>\&)는 데이터 복사 비용이 없으므로 성능상 우수합니다.
복사본 (vector<vector<int>>)은 데이터 복사에 따른 성능 저하가 발생할 수 있습니다.
따라서, 성능을 고려할 때 대규모 데이터 처리에서는 참조를 사용하는 것이 일반적으로 더 효율적입니다.

코드

https://github.com/KimGyeongLock/CodingTest/blob/main/14500.cpp