Junnnho

2020 KAKAO BLIND RECRUITMENT 문제 중 하나인

블록 이동하기 문제를 풀어봤습니다.

막힘없이 코드를 작성하긴 했지만,, 정말 오랜 시간이 걸렸기 때문에

이 문제를 풀면서 제 실력이 어느 수준인지 느낄 수 있었습니다.

움직일 수 있는 것은 문제에 주어졌듯이 2가지 형태입니다.

로봇 전체를 동서남북으로 움직이거나 // 둘 중 하나의 축을 기준으로 회전시키는 것입니다.

회전을 좀 더 간단하게 구현할 수 있었다면 좋았겠지만

딱히 방법이 떠오르지 않아 노가다로 조건을 주었습니다..

#include <string>
#include <vector>
#include <queue>
using namespace std;
struct robot{
    int y,x,side,time;
    /*
    side : 0, 1, 2, 3 // N, E, S, W
    */
};

int N;
int mx[4] = {0,0,-1,1};
int my[4] = {1,-1,0,0};
bool visit[100][100][4];
vector<vector<int> > board;

int getY(int y, int side){return side==0?y-1:(side==1?y:(side==2?y+1:y));}
int getX(int x, int side){return side==0?x:(side==1?x+1:(side==2?x:x-1));}

// ccw true : ccw || ccw false : cw
bool canMove(int y, int x, int side, int ccw){
    if(side==0){
        if(ccw){
            if(x-1>=0&&!board[y-1][x-1]&&!board[y][x-1]&&!visit[y][x][3]) return true;
        }
        else{
            if(x+1<N&&!board[y-1][x+1]&&!board[y][x+1]&&!visit[y][x][1]) return true;
        }
    }
    if(side==1){
        if(ccw){
            if(y-1>=0&&!board[y-1][x+1]&&!board[y-1][x]&&!visit[y][x][0]) return true;
        }
        else{
            if(y+1<N&&!board[y+1][x+1]&&!board[y+1][x]&&!visit[y][x][2]) return true;
        }
    }
    if(side==2){
        if(ccw){
            if(x+1<N&&!board[y+1][x+1]&&!board[y][x+1]&&!visit[y][x][1]) return true;
        }
        else{
            if(x-1>=0&&!board[y+1][x-1]&&!board[y][x-1]&&!visit[y][x][3]) return true;
        }
    }
    if(side==3){
        if(ccw){
            if(y+1<N&&!board[y+1][x-1]&&!board[y+1][x]&&!visit[y][x][2]) return true;   
        }
        else{
            if(y-1>=0&&!board[y-1][x-1]&&!board[y-1][x]&&!visit[y][x][0]) return true;
        }
    }
    return false;
}

int solution(vector<vector<int>> arr) {
    int answer = 0;
    board = arr;
    N = board.size();
    
    queue<robot> q;
    q.push({0,0,1,0});
    while(!q.empty()){
        int fy = q.front().y;
        int fx = q.front().x;
        int side = q.front().side;
        int sy = getY(fy, side);
        int sx = getX(fx, side);
        int time = q.front().time;
        q.pop();
        
        if((fy==N-1 && fx==N-1)||(sy==N-1&&sx==N-1)){
            answer = time;
            break;
        }
        
        if(visit[fy][fx][side]) continue;
        visit[fy][fx][side] = true;
        
        // move E,W,S,N
        for(int i = 0; i<4; i++){
            int ffy = fy+my[i];
            int ffx = fx+mx[i];
            int ssy = sy+my[i];
            int ssx = sx+mx[i];
            if(!(ffy>=0&&ffy<N&&ffx>=0&&ffx<N&&!board[ffy][ffx])) continue;
            if(!(ssy>=0&&ssy<N&&ssx>=0&&ssx<N&&!board[ssy][ssx])) continue;
            if(visit[ffy][ffx][side]) continue;
            q.push({ffy,ffx,side,time+1}); // use side var
        }
        
        // move one point
        // based fy, fx
        if(canMove(fy,fx,side,true)){
            for(int i = 0; i<4; i++){
                if(side == i) q.push({fy,fx,(i+3)%4,time+1});
            }
        }
        if(canMove(fy,fx,side,false)){
            for(int i = 0; i<4; i++){
                if(side==i) q.push({fy,fx,(i+1)%4,time+1});
            }
        }
        // based sy, sx
        if(canMove(sy,sx,(side+2)%4,true)){
            for(int i = 0; i<4; i++){
                if((side+2)%4 == i) q.push({sy,sx,(i+3)%4,time+1});
            }
        }
        if(canMove(sy,sx,(side+2)%4,false)){
            for(int i = 0; i<4; i++){
                if((side+2)%4 == i) q.push({sy,sx,(i+1)%4,time+1});
            }
        }
    }
    
    return answer;
}

이분탐색을 직접 구현하는데 자꾸 헷갈리는 부분이 많아서 정리를 해야겠다.

이분탐색은 원하는 값을 찾는 형태로 범위에 신경쓰지 않고 바로 구현하면 된다.

int s = 0;
int e = MAX;
int m;
while(s<=e){
	m = (s+e)/2;
    if(array[m] == wantValue) return;
    if(array[m] > wantValue) e = m-1;
    else if(array[m] < wantValue) s = m+1;
}

lower bound는 찾고자하는 값 이상의 첫번째 인덱스를 찾는 개념 

1 2 3 4 5 5 6 7 8 에서 5에 대한 lower bound의 인덱스는 4가 된다.

upper bound는 찾고자하는 값을 초과하는 첫번째 값의 인덱스를 찾는 개념

1 2 3 4 5 5 6 7 8 에서 5에 대한 upper bound의 인덱스는 6이 된다.

lower bound는 start<=end 단위가 아니라 start<end 단위로 사용해야 한다.

또한 중간값이 찾고자하는 값보다 크거나 같은 경우

특히 같은 경우에는 그 위치가 lower bound index가 될 수 있으므로 end = mid - 1 이 아닌 end = mid 를 적용

upper bound는 마찬가지로 start<end 단위를 사용하며

이상이 아닌 초과된 인덱스를 찾으므로

중간값이 찾고자하는 값보다 작거나 같은 경우는 무조건 start = mid + 1을 하여 인덱스를 계산하게 된다.

//lower_bound

int s = 0;
int e = MAX;
int m;

while(s<e){
	m = (s+e)/2;
    if(array[m] >= wantValue) e = m;
    else s = m+1;
}

return e;

// upper_bound

while(s<e){
	m = (s+e)/2;
    if(array[m] > wantValue) e = m;
    else s = m+1;
}

return e;

Programmers : https://programmers.co.kr/learn/courses/30/lessons/42627

level 3 , Heap 에 해당하는 문제입니다.

학부 수업시간 때, FIFO 부터 시작해서 OS 컨트롤러를 공부할 때 접해봤던 비슷한 문제입니다.

평균시간을 줄이기 위해 접근한 방법은

대기큐에 있는 작업 중에서! 가장 수행시간이 짧은 것 부터 처리하는 것! 으로 접근해봤습니다.

좀더 자세한 설명은 코드와 함께 주석으로 설명하였습니다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<int, int> pii;

int solution(vector<vector<int>> v) {
    int answer = 0;
    int time = 0;

    // 우선 큐에 대기 중인 프로세스 중에서 소요시간이 가장 짧은 것들을 우선적으로 처리하도록 접근
    // => 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
    // 힙의 조건은 시간을 우선적으로 처리하되, 시간이 동일하면 사용시간이 짧은 녀석을 먼저 가져온다

    priority_queue<pii, vector<pii>, greater<pii> > q;

    // 내 나름 사용하기 편하게 변경
    vector<pii> jobs;
    for (int i = 0; i < v.size(); i++)
        jobs.push_back({ v[i][0], v[i][1] });
    
    // jobs의 값이 작업요청 순서대로 들어왔다는 말이 없으므로 정렬부터 함
    sort(jobs.begin(), jobs.end());

    // 먼저 들어온 작업부터 처리
    time = jobs[0].first + jobs[0].second;
    answer = jobs[0].second;
    
    int finish_task = 1;
    int task = 1;
    
    while(finish_task < jobs.size()){
        // 현재 time 까지 요청이 들어온 작업들을 큐에 넣고 작업
        for(int i = task; i < jobs.size(); i++){
            if(jobs[i].first <= time){
                // greater 로 꺼낼때 작업시간이 짧은 순으로 꺼내기 위해 swap 해서 푸쉬
                q.push({jobs[i].second, jobs[i].first});
                task++;
           }
            // time 보다 후에 들어온 작업은 우선처리 조건에 포함되지 않음
            else break;
        }
        
        // 현재 대기큐에 작업이 없다 -> 다음 작업을 가져옴 task        
        if(q.empty()){
            time = jobs[task].first+jobs[task].second;
            answer += jobs[task++].second;
            finish_task++;
        }
        // 현재 대기큐에 작업이 있다
        else{
            pii now_task = q.top();
            q.pop();
            finish_task++;
            answer += (time - now_task.second) + now_task.first;
            time += now_task.first;
        }
    }

    return answer/jobs.size();
}

BOJ : https://www.acmicpc.net/problem/2194

스타크래프트와 같은 게임을 하다 보면 어떤 유닛을 목적지까지 이동시켜야 하는 경우가 종종 발생한다. 편의상 맵을 N×M 크기의 2차원 행렬로 생각하자. 또한 각각의 유닛은 크기를 가질 수 있는데, 이를 A×B 크기의 2차원 행렬로 생각하자. 아래는 5×5 크기의 맵과 2×2 크기의 유닛에 대한 한 예이다. S는 시작점을 나타내며 E는 끝점을 나타낸다.

유닛은 상하좌우의 네 방향으로만 움직일 수 있다. 단, 유닛의 일부분이 장애물이 설치된 부분(위의 예에서 색이 칠해진 부분)을 지날 경우, 위의 예에서는 시작 위치에서 위로 이동하는 경우는 허용되지 않는다.

위의 예는 유닛을 오른쪽으로 세 칸, 위쪽으로 세 칸 움직이면 목적지에 도달할 수 있고, 이 경우가 가장 적은 이동 회수를 거치는 경우이다. 이동하는 도중에 유닛이 맵 밖으로 나가는 경우는 허용되지 않는다.

맵의 정보와 유닛의 정보가 주어졌을 때, 유닛을 목적지까지 움직이기 위해 필요한 최소의 이동 회수를 구하는 프로그램을 작성하시오.

백준 2194번 유닛 이동시키기 문제입니다.

구현부류에 해당하고 간단한 BFS 문제였습니다.

시작지점의 유닛 좌측상단의 좌표를 기준으로 하기 때문에

BFS 탐색간에 유닛의 크기만큼 전체가 장애물을 피해서 이동이 가능한지 판단해주시면서 탐색해주시면 됩니다.

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

queue<pair<pii, int> > q;

int n, m, a, b, k, dx, dy;
bool visit[502][502];
bool arr[502][502];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };

bool test(int y, int x) {

	for (int i = 0; i < a; i++)
		for (int j = 0; j < b; j++)
			if (arr[y + i][x + j]) return false;

	return true;
}


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m >> a >> b >> k;

	for (int i = 0; i < k; i++) {
		cin >> dy >> dx;
		arr[dy][dx] = true;
	}

	int sy, sx, ey, ex;
	cin >> sy >> sx >> ey >> ex;
	q.push({ {sy,sx},0 });
	int answer = -1;

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (y == ey && x == ex) {
			answer = cnt;
			break;
		}

		for (int i = 0; i < 4; i++) {
			int yy = y + my[i];
			int xx = x + mx[i];
			if (yy > 0 && yy + a - 1 <= n && xx > 0&& xx + b - 1 <= m && !visit[yy][xx] && test(yy, xx)) {
				visit[yy][xx] = true;
				q.push({ {yy,xx},cnt + 1 });
			}
		}
	}

	cout << answer;

	return 0;
}