오늘의 문제
[PCCP 기출문제] 2번 / 석유 시추
리코쳇 로봇
당구 연습

[PCCP 기출문제] 2번 / 석유 시추

문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

시추관의 위치	획득한 덩어리	총 석유량
1	[8]	8
2	[8]	8
3	[8]	8
4	[7]	7
5	[7]	7
6	[7]	7
7	[7, 2]	9
8	[2]	2

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
  - 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
  - land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
  - land[i][j]는 0 또는 1입니다.
  - land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

정확성 테스트 케이스 제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
  - 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100
  

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, max_oil;
vector<vector<int>>  _land;
map<int, int> land_size;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int bfs(int x, int y, int k){
    queue<pair<int, int>> q;
    q.push({x, y});
    _land[x][y] = k;
    int sz = 1;
    
    while(!q.empty()){
        int nowx = q.front().first;
        int nowy = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int nx = nowx + dx[i];
            int ny = nowy + dy[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if( _land[nx][ny] != 1) continue;
            q.push({nx, ny});
            ++sz; _land[nx][ny] = k;
        }
    }
    return sz;
}

void bfs_all(){
    int k = 2;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(_land[i][j] == 1) {
                land_size.insert({k, bfs(i, j, k)});
                ++k;
            }
        }
    }
}


int solution(vector<vector<int>> land) {
    _land = land;
    n = land.size(); m = land[0].size();
    bfs_all();
    
    for(int i = 0; i < m; i++){
        set<int> t;
        for(int j = 0; j < n; j++){
            if(_land[j][i] != 0) t.insert(_land[j][i]);
        }
        int now = 0;
        for(int ti : t) now += land_size[ti];
        max_oil = max(max_oil, now);
    }
    
    return max_oil;
}

효율성 테스트로 인해 bfs로 석유에 번호를 매기고, 각 석유 덩어리의 크기 map에 저장했다.

각 열 별로 순회하며 해당 열에 속한 석유의 번호를 set(중복 X)에 저장하고, 해당 석유의 크기를 모두 더해 max 값을 찾았다.

리코쳇 로봇

문제 설명
리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

제한 사항

• 3 ≤ board의 길이 ≤ 100
  - 3 ≤ board의 원소의 길이 ≤ 100
  - board의 원소의 길이는 모두 동일합니다.
  - 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
  - "R"과 "G"는 한 번씩 등장합니다.
  

코드

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {0, 1, 0, -1};  // 동 남 서 북
int dy[4] = {1, 0, -1, 0};
int x, y, n, m;
vector<vector<int>> dis;
vector<string> _board;

int move(){
    queue<pair<int, int>> q;
    q.push({x, y});
    dis[x][y] = 0;
    
    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        if(_board[x][y] == 'G') return dis[x][y];
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || _board[nx][ny] == 'D') continue;
                 
            while(1){
                if(nx + dx[i] < 0 || nx + dx[i] >= n || ny + dy[i] < 0 || ny +dy[i] >= m || _board[nx + dx[i]][ny + dy[i]] == 'D') {
                    if(dis[nx][ny] != -1) break;
                    dis[nx][ny] = dis[x][y] + 1;
                    q.push({nx, ny});
                    break;
                }
                nx += dx[i];
                ny += dy[i];
            }
        }
    }
    return -1;
}

int solution(vector<string> board) {
    _board = board;
    n = board.size(); m = board[0].size();
    dis = vector<vector<int>>(n, vector<int>(m, -1));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(board[i][j] == 'R') {
                x = i; y = j;
                break;
            }
        }
    }
    return move();
}

당구 연습

문제 설명
프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다.

머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다.

오늘도 당구 학원에 나온 머쓱이에게 당구 선생님이"원쿠션"(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고, 벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라고 부릅니다) 연습을 하라면서 당구공의 위치가 담긴 리스트를 건네줬습니다. 리스트에는 머쓱이가 맞춰야 하는 공들의 위치가 담겨있습니다. 머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아가며 "원쿠션" 연습을 하면 됩니다. 이때, 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춥니다.

머쓱이와 달리 최근 취미로 알고리즘 문제를 풀기 시작한 당신은, 머쓱이가 친 공이 각각의 목표로한 공에 맞을 때까지 최소 얼마의 거리를 굴러가야 하는지가 궁금해졌습니다.

당구대의 가로 길이 m, 세로 길이 n과 머쓱이가 쳐야 하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY, 그리고 매 회마다 목표로 해야하는 공들의 위치 좌표를 나타내는 정수 쌍들이 들어있는 2차원 정수배열 balls가 주어집니다. "원쿠션" 연습을 위해 머쓱이가 공을 적어도 벽에 한 번은 맞춘 후 목표 공에 맞힌다고 할 때, 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다. 공의 크기는 무시하며, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단합니다. 공이 목표 공에 맞기 전에 멈추는 경우는 없으며, 목표 공에 맞으면 바로 멈춘다고 가정합니다.

위 그림은 친 공이 벽에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

위 그림은 친 공이 꼭짓점에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

제한사항

• 3 ≤ m, n ≤ 1,000
• 0 < startX < m
• 0 < startY < n
• 2 ≤ balls의 길이 ≤ 1,000
• balls의 원소는 [a, b] 형태입니다.
  - a, b는 머쓱이가 맞춰야 할 공이 놓인 좌표를 의미합니다.
  - 0 < a < m, 0 < b < n
  - (a, b) = ( startX, startY )인 입력은 들어오지 않습니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int m, int n, int startX, int startY, vector<vector<int>> balls) {
    vector<int> answer;
    for(vector<int> v : balls){
        int len = 0;
        if(startX == v[0]) {
            if(m - startX < startX) len = pow(2 * (m - startX), 2) + pow(startY - v[1], 2);
            else len = pow(2 * startX, 2) + pow(startY - v[1], 2);
            if(startY < v[1]) len = min(len, (int)(pow(startY + v[1], 2)));
            else len = min(len, (int)pow(2 * n - startY - v[1], 2));
        }
        else if(startY  == v[1]) {
            if(n - startY < startY) len = pow(startX - v[0], 2) + pow(2 * (n - startY), 2);
            else len = pow(startX - v[0], 2) + pow(2 * startY, 2);
            if(startX < v[0]) len = min(len, (int)(pow(startX + v[0], 2)));
            else len = min(len, (int)pow(2 * m - startX - v[0], 2));
        }
        else{
            len = min({pow(2 * m - startX - v[0], 2) + pow(startY - v[1], 2), pow(-startX - v[0], 2) + pow(startY - v[1], 2), pow(startX - v[0], 2) + pow(2 * n - startY - v[1], 2), pow(startX - v[0], 2) + pow(-startY - v[1], 2)});
        }
        answer.emplace_back(len);
    }
    
    return answer;
}

입사각과 반사각이 같은 최단 거리를 구하는 방법은 시작점을 x = 0, x = n, y = 0, y = m으로 대칭이동한 점과의 거리 중 가장 짧은 거리를 구하면 된다.

그런데! x 좌표나 y 좌표가 같은 경우 목표 좌표 방향으로는 이동할 수 없고(한 번 튕겨야하므로), 반대 방향으로 튕기는 것도 고려해야한다.(이거 안하면 31번 이후 테스트케이스가 터진다)