[C++] 프로그래머스 바탕화면 정리

https://school.programmers.co.kr/learn/courses/30/lessons/161990

풀이

바탕화면 정보 wallpaper가 주어집니다. 빈 칸은 '.' 파일이 있다면 '#"으로 표기될 때, 모든 파일을 선택할 수 있는 맨하탄 거리가 최소가 되도록 드래그 시작점과 끝점을 결정하는 문제입니다.

 

아이디어는 파일이 존재하는 가장 최소 행과 열, 최대 행과 열을 찾고 최대 행, 열 +1을 해주는 것입니다.

wallpaper의 행, 열 크기가 50 이하이므로 2중 for문 완전탐색으로 문제를 해결할 수 있습니다.

 

완전탐색 전에, 최소 행, 열 변수 min_row, min_col은 MAX 매크로 상수로 정의하고, 최대 행, 열 변수 max_col, max_row는 0으로 초기화 해둡니다. 이 후, 완전탐색을 하며 '#'을 찾을때마다 min, max 함수를 사용해 인덱스를 업데이트 해주면 알고리즘이 완성됩니다.

 

탐색이 끝난 후에는 max_row, max_col 에 +1을 해주고 답을 리턴해줍니다.

 

리뷰

find 및 rfind 함수를 사용해 구현해보려 했다가 더 앞 또는 뒤의 값을 찾지 못하는 상황이 있어 완전탐색으로 코드를 구현했습니다. 

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>

#define MAX 123456789
using namespace std;
// 빈칸 ".", 파일 "#"
vector<int> solution(vector<string> wallpaper) {
    vector<int> answer;
    // wallpaper에서 행, 열 최소 최대 찾기
    // 끝점은 행,열 +1
    
    int min_row = MAX, min_col = MAX, max_row =0, max_col=0;
    // 완전탐색
    for (int i=0; i<wallpaper.size(); i++) {
        int row, col;
        for (int j=0; j<wallpaper[i].size(); j++) {
            if (wallpaper[i][j] == '#') {
                row = i;
                col = j;
                min_row = min(min_row, row);
                min_col = min(min_col, col);
                max_row = max(max_row, row);
                max_col = max(max_col, col);
            }
        }
        
    }
    
    max_row++;
    max_col++;
    answer.push_back(min_row);
    answer.push_back(min_col);
    answer.push_back(max_row);
    answer.push_back(max_col);
    return answer;
}