[programmers] 250136번 - PCCP 기출문제 2번(BFS, PCCP 기출문제)

1. 문제 및 예제

 

 Level 2 문제들을 쭉 풀어가던 도중 PCCP 기출문제  두 문제가 공개되어 바로 풀어보았다. BFS 알고리즘이 핵심이지만, 더 빠른 알고리즘을 위해 범위를 저장하는 부분이 필요하였다.

---

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

프로그래머스

---

2. 풀이과정

 

 시간 복잡도 때문에 BFS로는 풀 수 없다. O(N^3)이기 때문에 다른 방법을 생각해야 했다. 내가 생각한 방법은 다음과 같다.

 

아래와 같은 입력이 주어졌다고 가정하자.

---

---

이렇게 되면 다음과 같이 석유의 시작열과 끝열을 따로 저장할 수 있다.

---

시작열	끝열	석유의 크기
4	6	7
1	3	8
7	8	2

---

따로 저정한 자료를 이용하여 해당 범위에 겹치는 열에 석유의 크기를 전부 더해주면 된다. 문제를 나누면 다음과 같다.

 

1. 석유의 크기와 해당 크기에 해당하는 시작열과 끝열을 구한다. (BFS)

2. 1부터 끝열까지 모든 열을 탐색하며 해당하는 석유의 크기를 더해준다.

 

- 정답 코드

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

using namespace std;

int dir_x[4] = {0 ,1, 0, -1};
int dir_y[4] = {1, 0, -1, 0};

bool check_range(int row, int col, int max_row, int max_col){
    if(row < 0 || row >= max_row || col < 0 || col >= max_col)
        return false;
    return true;
}

int solution(vector<vector<int>> land) {
    int answer = 0;
    vector<pair<pair<int, int>, int>> dic;
    
    int row_size = land.size();
    int col_size = land[0].size();
    
    //덩어리 찾기
    for(int i = 0; i < row_size; i++){
        for(int j = 0; j < col_size; j++){
            //탐색 시작
            if(land[i][j] == 1){
                queue<pair<int, int>> q;
                int start_col = j;
                int end_col = j;
                int count = 0;
                land[i][j] = 0;
                q.push(make_pair(i, j));
                
                while(!q.empty()){
                    int row = q.front().first;
                    int col = q.front().second;
                    //cout << "cor: " << row << ' ' << col << endl;
                    count++;
                    q.pop();
                    
                    for(int k = 0; k < 4; k++){
                        int next_row = row + dir_x[k];
                        int next_col = col + dir_y[k];
                        
                        if(check_range(next_row, next_col, row_size, col_size) &&
                          land[next_row][next_col] == 1){
                            land[next_row][next_col] = 0;
                            start_col = min(start_col, next_col);
                            end_col = max(end_col, next_col);
                            q.push(make_pair(next_row, next_col));
                        }
                    }
                }
                
                dic.push_back(make_pair(make_pair(start_col, end_col), count));
            }
        }
    }

    for(int i = 0; i < col_size; i++){
        int tmp = 0;
        for(auto it : dic){
            if(it.first.first <= i && it.first.second >= i)
                tmp += it.second;
        }
        answer = max(answer, tmp);
    }
    
    return answer;
}

 

O(N^2)로 완성할 수 있다.

 

3. 결어

 

 PCCP 기출 문제가 두 문제 공개되었지만, 한 문제는 아직 풀지 못했다. 최대한 빨리 풀어보았으면 좋겠다.