개발 블로그

문제 링크 : programmers.co.kr/learn/courses/30/lessons/49191#

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

접근 방법

자신의 순위를 알려면, 자신을 제외한 n-1명과의 승/패 관계를 모두 알아야한다.

vecArrWin[i] 에는 승리한 사람 i를 기준으로 잡고 i에게 진 사람들을 저장했다.

vecArrLose[i]에는 패배한 사람 i를 기준으로 잡고 i를 이긴 사람들을 저장했다.

입력 예시를 표현하면 아래와 같다.

vecArrWin[]

vecArrLose[]

1부터 n까지 BFS를 돌린다.

BFS안에서는 init 노드를 기준으로 init이 이긴 사람들과 Init에게 진 사람들을 카운트한다.

검사할 때는 init 노드에서 시작해서 벡터 배열 안에 있는 노드들을 queue에 넣으면서 탐색을 진행해 나간다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;

int cntArr[101] = {0};


int BFS(int init, vector<int>* vecArrWin, vector<int>* vecArrLose){
    queue<int> que;
    que.push(init);
    int cnt = 0;
    int visited[101] = {0};
    visited[init] = 1;
    while(!que.empty()){
        
        int startNode = que.front();
        que.pop();
        
        for(int i = 0; i<vecArrWin[startNode].size(); i++){	//i가 승리자 -> i에게 진 사람들 카운트
            if(visited[vecArrWin[startNode][i]] == 0){
                visited[vecArrWin[startNode][i]] = 1;
                que.push(vecArrWin[startNode][i]);
                cnt++;
            }
        }
    }
    memset(visited, 0, sizeof(visited));
    que.push(init);
    visited[init] = 1;
    while(!que.empty()){
        int startNode = que.front();
        que.pop();
        
        for(int i = 0; i<vecArrLose[startNode].size(); i++){ //i가 패배자 -> i가 이긴 사람들 카운트
            if(visited[vecArrLose[startNode][i]] == 0){
                visited[vecArrLose[startNode][i]] = 1;
                que.push(vecArrLose[startNode][i]);
                cnt++;
            }
        }
    }
    cout << endl;
    return cnt;
    
}



int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    vector<int> vecArrWin[101];
    vector<int> vecArrLose[101];
    
    int winner, loser;
    for(int i = 0; i<results.size(); i++){
        winner = results[i][0];
        loser = results[i][1];
        
        vecArrWin[winner].push_back(loser);
        vecArrLose[loser].push_back(winner);
    }
    for(int i = 1; i<=n; i++){
        if(n-1 == BFS(i, vecArrWin, vecArrLose)){		//자신을 제외한 n-1명과 승/패 관계 알아야 함
            answer++;
        }
    }
    return answer;
}

문제 링크 : programmers.co.kr/learn/courses/30/lessons/49189

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

접근 방법

벡터 배열을 이용해서 양방향으로 연결된 노드들간의 관계를 표현했다. 그 후 BFS로 depth를 1씩 증가시켜나갔다. 

while문 안에서 depth가 answer과 같으면 cnt를 증가시켰으며 depth가 바뀌면 answer를 바뀐 depth로 초기화시키고 cnt도 다시 1로 초기화 시켜서 가장 먼 노드들의 개수를 구할 수 있었다.

#include <string>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
int visited[20001] = {0};

queue<pair<int,int>> que;
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<int> vecArr[50000];					//벡터 배열
    
    int v1, v2;
    for(int i = 0; i<edge.size(); i++){			//양방향 엣지 연결
        v1 = edge[i][0];
        v2 = edge[i][1];
        vecArr[v1].push_back(v2);
        vecArr[v2].push_back(v1);
    }
    visited[1] = 1;
    que.push(make_pair(1,0));
    int cnt = 0;
    
    while(!que.empty()){
        
        pair<int,int> p = que.front();
        if(answer == p.second) cnt++;		//가장 먼 노드들의 개수 몇개인지 카운트
        else{								//depth 증가해서 바뀌면 값 재설정
            answer = p.second;
            cnt = 1;
        }
        que.pop();
        vector<int> vec = vecArr[p.first];
        for(int i = 0; i<vec.size(); i++){
            if(visited[vec[i]]==0){
                visited[vec[i]] = 1;
                que.push(make_pair(vec[i], p.second+1));
            }
        }
        
    }
    answer = cnt;
    
    return answer;
}

문제 링크 : programmers.co.kr/learn/courses/30/lessons/43164

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

접근 방법

테스트 케이스 중 3,4번만 맞았다면 그래프 연결이 끊긴 경우를 생각하지 않았을 것이다.  즉, 입력이 1,2 / 1,3 / 3,1 이라면 1->2까지만 탐색하고 종료해버리는 것이다.

이것을 DFS의 리턴 bool 값을 이용해서 처리해줘야 한다. 탐색을 하다가 끊겼을 경우엔 false 를 리턴해서 가장 뒤의 요소를 pop 하고 다시 탐색을 시작해서 1->2 가 아닌 1->3이 되도록 해준다. 제한사항인 "주어진 항공권은 모두 사용해야 합니다" 를 만족하면 DFS함수를 리턴 시킨다. 

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

using namespace std;

int visited[10000] = {0};

vector<string> res;

bool DFS(string start, vector<vector<string>> tickets, int chkcnt){
 
    if(chkcnt==tickets.size()) return true;		//1-1) 탐색 다 끝나면 true 리턴해서
   
   for(int i = 0; i<tickets.size(); i++){
       if(visited[i]==0 && start == tickets[i][0]){
           visited[i] = 1;
           res.push_back(tickets[i][1]);
           bool resbool = DFS(tickets[i][1], tickets, chkcnt+1);	
           if(resbool) return true;				//1-2) 더 이상 아래로 내려가지 않고 차례로 빠져나옴 
           
           visited[i] = 0;						//2-2) false 리턴됐으면 이 라인으로 내려오게 됨
       }
   }
    res.pop_back();	//길 끊겨서 항공권 다 탐색해도 이을게 없으면 마지막에 연결된 곳 pop
    return false;	//2-1) false 리턴해서 길 끊겼음을 알림
}


vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    sort(tickets.begin(), tickets.end());

    string start = "ICN";
    res.push_back(start);

    DFS(start, tickets, 0);
    answer = res;
       
    return answer;
}

참고 : yabmoons.tistory.com/528

nanyoungkim.tistory.com/91

문제 링크 : www.acmicpc.net/problem/16236

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

접근 방법

fishVec에 pair를 활용해 <거리, 행, 열>  정보 담은 후 sort함수 이용해 정렬하면 자동으로 우선순위가 적용되는 점을 이용했다.

물고기를 한 마리 먹을 때마다 현재 위치에서 BFS함수 돌려서 먹을 수 있는 물고기들을 fishVec에 넣는다. 그 후 sort로 정렬해서 가장 앞의 물고기 먹고 위치와 아기상어 크기 등 조건들을 조정해준다.

fishVec에 물고기가 없으면 더 이상 먹을 물고기가 없는 것이므로 while(1)을 종료한다.

주의할 점은 맨 처음 아기상어의 위치를 입력받아서 다른 변수에 저장한 후 해당 칸 0으로 설정해야하는 점이다. 아기상어의 현재 위치가 계속 바뀌므로 처음 위치를 빈칸으로 바꿔줘야한다.

sort() 활용 전에 노가다로 하다가 시간초과가 났는데 sort() 를 활용하니 코드와 조건식이 간단해져서 시간 안에 해결할 수 있었다.

//
//  SM_BOJ16236_아기상어.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/25.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

//fishVec에 거리, 행, 열 정보 담아서 sort함수 이용해 정렬하면 자동으로 우선순위 적용됨
//물고기 한 마리 먹을 때마다 현재 위치에서 BFS함수 돌려서 먹을 수 있는 물고기들 fishVec에 넣고 sort 후 가장 앞의 물고기 먹고 위치 조정
//fishVec에 물고기 없으면 종료
//맨 처음 아기상어의 위치 저장 후 해당 칸 0으로 설정해서 빈칸으로 바꿔줘야함. (아기상어의 현재 위치 바뀌므로)

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

using namespace std;

int N;
int map[20][20];

//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};


int nowR, nowC;
int babySize = 2;
int toEat = 2;
int resSec = 0;

vector<pair<pair<int,int>,int>> fishVec;        //거리, 가장 위쪽, 가장 왼쪽


void BFS(int row, int col){ //현재 위치에서 먹을 수 있는 물고기까지의 거리와 위치 저장
    
    fishVec.clear();                //현재 위치 바뀌었으므로, 벡터 비운 후 바뀐 현재위치 중심으로 가장 가까운 물고기들 push
    queue<pair<int,int>> que;
    que.push(make_pair(row,col));       //다음에 어디 방문할지 저장하는 큐
    
    int fromStart[20][20] = {0};
    int visited[20][20] = {0};
    visited[row][col] = 1;      //현재 위치는 이미 방문함
    
    int minDist = 1000;
    
    while(!que.empty()){
        
        int r = que.front().first;
        int c = que.front().second;
        que.pop();
        
        for(int i = 0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr<0 || nr>=N || nc<0 || nc>=N || visited[nr][nc]==1 || babySize<map[nr][nc]) continue;  //범위 넘어가거나, 방문했거나, 크기 크면 못 지나감
            
            fromStart[nr][nc] = fromStart[r][c] + 1;
            visited[nr][nc] = 1;
            que.push(make_pair(nr,nc));
            
            if(map[nr][nc]>0 && babySize>map[nr][nc]){  //먹을 수 있는 물고기 (작은거)
                
                //먹을 수 있는 물고기 중 가장 가까운 물고기 먹기
                if(minDist>=fromStart[nr][nc]){
                    minDist = fromStart[nr][nc];
                    fishVec.push_back(make_pair(make_pair(minDist, nr),nc));
                    
                   // cout << nr << " " << nc << "  거리 : " << minDist << "\n";
                }
            }
        }
    }
}


int main(){
    

    cin >> N;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            scanf("%d", &map[i][j]);
            if(map[i][j] == 9) {
                map[i][j] = 0;
                nowR = i; nowC = j;}    //아기상어 위치 저장
        }
    }
    
    
    while(1){
        
        
        BFS(nowR, nowC);            //현재 위치에서 가장 가까운 물고기들 탐색
        if(fishVec.size()==0){      //먹을 수 있는 물고기 없을 때까지
            
            break;
        }
        else{
            
            sort(fishVec.begin(), fishVec.end());   //거리 같은 물고기들 중 위/ 왼 우선순위 적용해서 정렬 후 가장 앞의 요소 먹기
            
            resSec += fishVec[0].first.first;       //이동거리 = 걸린 초
            
            
            //잡아 먹음
            toEat-=1;
            if(toEat==0){
                babySize+=1;
                toEat = babySize;
            }
            
            
            //잡아먹었으니 아기상어 위치 바뀜
            nowR = fishVec[0].first.second;
            nowC = fishVec[0].second;
            
            map[nowR][nowC] = 0;        //해당 칸 물고기 없어져서 빈칸됨
            
        }
    }
    cout <<resSec;
    
    
    
    return 0;
}

참고 : rile1036.tistory.com/90

문제 링크 : www.acmicpc.net/problem/16967

문제

크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐진다.

즉, 배열 B의 (i, j)에 들어있는 값은 아래 3개 중 하나이다.

• (i, j)가 두 배열 모두에 포함되지 않으면, Bi,j = 0이다.
• (i, j)가 두 배열 모두에 포함되면, Bi,j = Ai,j + Ai-X,j-Y이다.
• (i, j)가 두 배열 중 하나에 포함되면, Bi,j = Ai,j 또는 Ai-X,j-Y이다.

배열 B와 정수 X, Y가 주어졌을 때, 배열 A를 구해보자.

입력

첫째 줄에 네 정수 H, W, X, Y가 주어진다. 둘째 줄부터 H + X개의 줄에 배열 B의 원소가 주어진다.

항상 배열 A가 존재하는 경우만 입력으로 주어진다.

출력

총 H개의 줄에 배열 A의 원소를 출력한다.

제한

• 2 ≤ H, W ≤ 300
• 1 ≤ X < H
• 1 ≤ Y < W
• 0 ≤ Bi,j ≤ 1,000

접근 방법

프로그램이 시작하면 arrB에 입력을 받고 그 중 (H x W) 만큼만 map배열에 옮긴다. 

그 후, 행은 X부터 H+X 까지 / 열은 Y부터 W+Y까지 돌면서 즉, 배열 A끼리 겹치는 부분에 한해서 요소끼리 뺄셈 연산을 해준다. (겹친 부분 처리)

이때 주의할 점은 A에서 A를 빼야하고, 뺀 결과를 즉시 반영해 배열 값을 갱신하면서 매 행을 진행해나가야 한다는 것이다. 

아래의 예를 들어서 설명해보겠다.

입력이 다음과 같이 주어졌다고 하자.

3 4 1 1
1 2 3 4 0
5 7 9 11 4
9 15 17 19 8
0 9 10 11 12

그럼 배열 B는 아래와 같다.

아래 배열은 map 배열로, (H x W) 만큼 배열 B에서 복사해온것이다. (H x W)만큼을 제외한 곳은 0으로 채웠다.

X=1, Y=1이므로 색으로 표시한 곳이 겹치는 부분이다. 

우리는 배열 A를 쉽게 알 수 있는데, 이 배열 A를 이용해서 거꾸로 생각해보면 코드를 쉽게 구현할 수 있다. 배열 A는 아래와 같다.

이걸 X=1, Y=1만큼 옮겨서 겹친 것을 구현해보면, 다음과 같다. 

매 행을 진행해 나가면서 겹친 부분끼리 뺀 값을 갱신해줘야, 다음 행을 계산할 때 그 값이 반영돼서 올바른 값이 나온다.

다시 말하면, map[1][1]에서 map[1-X][1-Y]를 빼서 map[1][1]을 6으로 갱신해줘야, 그 다음 행의 map[2][2]-map[2-X][2-Y]를 계산할 때 올바르게 11에서 6을 뺄 수 있다. (매 행마다 값을 갱신해주지 않으면 11에서 (6+1) 을 뺀 것으로 계산된다.)

문제에서 주어진 예제로만 생각했을 때는 

for(int row = X; row<=rowB; row++){
        bool chk=false;
        for(int col = Y; col<=colB; col++){
            if(map[row][col] != 0){
                map[row][col] -= map[row-X][col-Y];
                chk = true;
            }
        }
        
        if(!chk) break;
    }

이 코드에서 map[row][col] -= arrB[row-X][col-Y]로 계산해도 결과값이 잘 나와서 어디가 틀린줄 몰랐는데,

배열 A끼리 겹친것이므로 겹친 부분에 대해서는 배열 A끼리 빼줘야하는걸 놓쳐서 틀린것이었다. 

//
//  SM_BOJ16976_배열 복원하기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/25.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>

using namespace std;

int arrB[610][610];
int map[610][610];

int H,W,X,Y;

int main(){
    
    cin >> H >> W  >> X >> Y;
    int rowB = H+X;
    int colB = W+Y;
    
    for(int i = 0; i<rowB; i++){
        for(int j = 0; j<colB; j++){
            scanf("%d", &arrB[i][j]);
            map[i][j]= 0;
        }
    }
    
    for(int i = 0; i<H; i++){
        for(int j = 0; j<W; j++){
            map[i][j] = arrB[i][j];
        }
    }
    
    
    for(int row = X; row<=rowB; row++){
        bool chk=false;
        for(int col = Y; col<=colB; col++){
            if(map[row][col] != 0){
                map[row][col] -= map[row-X][col-Y];
                chk = true;
            }
        }
        
        if(!chk) break;
    }

    
    for(int i = 0; i<H; i++){
        for(int j = 0; j<W; j++){
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
    

    return 0;
}

문제 링크 : www.acmicpc.net/problem/20055

문제

길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다.

벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다. i번 칸의 내구도는 Ai이다. 위의 그림에서 1번 칸이 있는 위치를 "올라가는 위치", N번 칸이 있는 위치를 "내려가는 위치"라고 한다.

컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올라가는 위치에만 땅에서 올라가고, 내려가는 위치에서만 땅으로 내려갈 수 있다. 내려가는 위치에 로봇이 있는 경우 로봇은 반드시 땅으로 내려가야 한다. 로봇이 어떤 칸에 올라가거나 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다. 내구도가 0인 칸에는 로봇이 올라갈 수 없다.

로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다.

컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려고 한다. 로봇을 옮기는 과정에서는 아래와 같은 일이 순서대로 일어난다.

1. 벨트가 한 칸 회전한다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
   1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.

입력

첫째 줄에 N, K가 주어진다. 둘째 줄에는 A1, A2, ..., A2N이 주어진다.

출력

몇 번째 단계가 진행 중일때 종료되었는지 출력한다.

제한

• 2 ≤ N ≤ 100
• 1 ≤ K ≤ 2N
• 1 ≤ Ai ≤ 1,000

접근 방법

문제에서 주어진 조건대로만 잘 구현하면 되는 문제이다.

beltArr[1]에 로봇이 들어오고 beltArr[N]에서 로봇이 나가는 것에 유의하자.

내구도는 beltArr[1] ~ beltArr[2N] 에서 숫자가 돌고, 

로봇은 isRobot[1] ~ isRobot[N] 에서만 도는 것도 주의해야한다.

(처음에 로봇도 1부터 2N까지 돌려서 계속 헤맸었다.)

나머지는 주석을 참고하면 된다.

#include <iostream>
#include <utility>

using namespace std;

int beltArr[201] = {0};
pair<int,bool> isRobot[101]; //몇번째인지, 로봇 있는지여부
int N,K;

bool cntZero(){			//내구도 0인 곳이 K개 이상이면 true 리턴
    
    int cnt = 0;
    bool res = false;
    for(int i = 1; i<=2*N; i++){
        if(beltArr[i]==0){
            cnt++;
        }
        if(cnt>=K) {
            res = true;
            break;
        }
    }
    return res;
    
}

int findFirstRobot(){		//1~N 칸에서 가장 먼저 들어간 로봇 찾기
    
    for(int i = N; i>=1; i--){
        if(isRobot[i].second==true){
            return i;
        }
    }
    return 0;
}

//2번 : 로봇 한칸 전진 : 먼저 올라간 로봇부터 / 이동 가능하면(로봇 없고, 내구도 1이상) / 로봇&내구도 바꿈
void shiftRobot(){
    
    
    int minIdx = findFirstRobot();

    if(minIdx!=0){
        for(int i = minIdx; i>=1; i--){
            if(isRobot[i].second==true){    //현재 자리에 로봇이 있고
                
                if(i==N){					//마지막 로봇은 그냥 내림
                    isRobot[i].first = 0;
                    isRobot[i].second = false;
                }
                else{
                    if(isRobot[i+1].second==false && beltArr[i+1]>=1){  //다음 자리에 로봇 없고, 내구도 1 이상이면
                        isRobot[i+1] = isRobot[i];	//다음 칸으로 옮기고
                        beltArr[i+1] -= 1;
                        isRobot[i].first = 0;		//옮겼으니까 초기화
                        isRobot[i].second = false;
                    }
                }
                
            }
        }
    }
    
}
//1번 : 회전 : 내구도 & 로봇 위치 shift
void shiftNumber(){
    
    //내구도 이동
    int tmp = beltArr[2*N];
    for(int i = 2*N -1; i>=1; i--){
        beltArr[i+1] = beltArr[i];
    }
    beltArr[1] = tmp;
    
    
    //로봇 이동
    //내리는 위치의 로봇 처리
    isRobot[N].first = 0;
    isRobot[N].second = false;
    
    for(int i = N-1; i>=1; i--){
        isRobot[i+1] = isRobot[i];
    }
    isRobot[1].first=0;
    isRobot[1].second = false;
    
}

//3번 : beltArr[1]에 로봇없으면 로봇 하나 올림
bool putRobot(int order){
    
    if(beltArr[1]>=1 && isRobot[1].second==false) {	//처음칸의 내구도 1 이상이고 로봇 없으면
        beltArr[1]-=1;  //내구도 1 감소
        
        isRobot[1].first = order;
        isRobot[1].second = true;
        return true;
    }
    return false;
}

int solution(){
    
    int ord = 1;
    int step = 1;
    while(1){
        
        //한칸회전
        
        shiftNumber();
        if(cntZero()){break;}
        
        
        //먼저 올라간 로봇부터 전진
        shiftRobot();

        if(cntZero()){break;}
        
        //1번 비었으면 로봇 올림
        if(putRobot(ord)){		//로봇 올릴 수 있었으면 ord++
            ord++;
        }
        
        if(cntZero()){break;}
        step+=1;
    }
    
    return step; 
}

int main(){
    
    
    cin>>N>>K;
    
    for(int i = 1; i<=N; i++){
        scanf("%d", &beltArr[i]);
        isRobot[i].first = 0;
        isRobot[i].second = false;
    }
    for(int i = N+1; i<=2*N; i++){
        scanf("%d", &beltArr[i]);
    }
    
    cout << solution();
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/15685

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

접근 방법 

(0,0) -> (1,0) / 오(d = 0)

(0,0) -> (1,0) / 오(d=0) -> (1,-1) / 위(d=1) 

(0,0) -> (1,0) / 오(d=0) -> (1,-1) / 위(d=1) -> (0,-1) / 왼(d=2) -> (0,-2) / 위(d = 1)

이때 d의 변화를 잘 보면 가운데를 중심으로 (왼쪽d + 1) % 4 가 오른쪽 d인 것을 알 수 있다.

즉, 예시를 들면 아래와 같다.

0, 1, 2, 1에서

(0+1) % 4 = 1

(1+1) % 4 = 2

//
//  SM_BOJ15685_드래곤커브.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/21.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <stack>
#include <utility>

using namespace std;

#define MAX 100
int map[MAX+1][MAX+1];

//오 위 왼 아
int dr[4] = {0,-1,0,1};
int dc[4] = {1, 0, -1, 0};

//정사각형 네꼭지점 검사
bool chkFour(int r, int c){
    if(map[r][c] && map[r][c+1] && map[r+1][c] && map[r+1][c+1]) return true;
    else return false;
}

//스택 카피 함수
stack<int> copyFunc(stack<int> stk){
    
    stack<int> tmp, res;
    while(!stk.empty()){
        tmp.push(stk.top());
        stk.pop();
    }
    
    while(!tmp.empty()){
        res.push(tmp.top());
        tmp.pop();
    }
    return res;
}


int main(){
    
    for(int i = 0; i<=MAX; i++){
        for(int j = 0; j<=MAX; j++){
            map[i][j] = 0;
        }
    }
    
    
    int N; cin >> N;
    
    int x, y, d ,g, row, col, nextR, nextC, nextD;
    for(int i = 0; i<N; i++){
        
        stack<int> stkD;
        
        cin >> x >> y >> d >> g;
        map[y][x] = 1;
        //0세대
        nextR = y + dr[d];
        nextC = x + dc[d];
        map[nextR][nextC]  = 1;
        stkD.push(d);
        
        row = nextR;
        col = nextC;
        
        //1세대 ~ g세대
        for(int i = 1; i<=g; i++){
            
            stack<int> copyStkD = copyFunc(stkD);
            
            while(!stkD.empty()){
                
                nextD = (stkD.top()+1) % 4;		//핵심 규칙
                copyStkD.push(nextD);
                stkD.pop();
                
                nextR = row + dr[nextD];
                nextC = col + dc[nextD];
                map[nextR][nextC] = 1;
                
                row = nextR;
                col = nextC;
                
            }
            stkD = copyFunc(copyStkD);
        }
        
        
        
    }
    
    int ans = 0;
    for(int i = 0; i<MAX; i++){
        for(int j = 0; j<MAX; j++){
            if(chkFour(i,j)) ans++;
        }
    }
    
    cout << ans;
    
    
    
    
    
    return 0;
}