코딩 테스트 일기 - 12일 차

김혁·2025년 7월 17일

목록 보기

12/65

미로 탈출

문제 링크 : 미로 탈출

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한 사항

5 ≤ maps의 길이 ≤ 100
-> 5 ≤ maps[i]의 길이 ≤ 100
-> maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
S : 시작 지점
E : 출구
L : 레버
O : 통로
X : 벽
-> 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
-> 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

풀이 방법

최단 거리를 구하는 문제이면서 레버를 갔다가 출구를 가야하기 때문에, 시작 지점에서 레버를 가는 최단 거리를 구하고, 레버에서 출구를 가는 최단 거리를 구하면 될 것으로 보인다. 최단 거리를 구하는 알고리즘은 bfs 알고리즘을 통해서 구할 것이고, 만약에 두가지 중에 하나라도 도달하지 못한다면 -1로 반환할 것이다.
-> bfs 알고리즘은 O(N*M)의 시간복잡도를 가지고, 그것을 두 번 실행할 것이기 때문에 문제 전체의 시간복잡도는 O(N*M)으로 보인다. N, M의 최대값은 100이기 때문에 이는 알맞은 알고리즘으로 보인다.

구현

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

using namespace std;

struct node{
    int x;
    int y;
    int dist;
};

int bfs(int& start_x, int& start_y, int w, int h, char end_Char, vector<string>& maps){
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    
    vector<vector<bool>> visited(h, vector<bool>(w, false));
    queue<node> Q;
    
    Q.push({start_x, start_y, 0});
    
    while(!Q.empty()){
        node k = Q.front(); Q.pop();
        
        for(int i = 0; i < 4; i++){
            int tempX = k.x + dx[i];
            int tempY = k.y + dy[i];
            if(tempX >= 0 && tempX < w && tempY >= 0 && tempY < h
               && maps[tempY][tempX] != 'X' && !visited[tempY][tempX]){
                if(maps[tempY][tempX] == end_Char){
                    start_x = tempX; start_y = tempY;
                    return k.dist + 1;
                }else{
                    visited[tempY][tempX] = true;
                    Q.push({tempX, tempY, k.dist + 1});
                }
            }
        }
    }
    
    return -1;
}


int solution(vector<string> maps) {
    int h = maps.size();
    int w = maps[0].size();
    int start_x, start_y;
    
    // S 위치 찾기
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(maps[i][j] == 'S'){
                start_x = j;
                start_y = i;
            }
        }
    }
    
    // 레버까지의 최소 거리 구하기(bfs)
    int lever = bfs(start_x, start_y, w, h, 'L', maps);
    
    if(lever == -1){
        return -1;
    }
   
    // 출구까지의 최소 거리 구하기(bfs)
    int end = bfs(start_x, start_y, w, h, 'E', maps);
    
    if(end == -1){
        return -1;
    }
    
    return lever + end;
}

혼자 놀기의 달인

문제 링크 : 혼자 놀기의 달인

문제 설명

혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.

숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.

준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.

그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.

그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.

1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.

상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

2 ≤ cards의 길이 ≤ 100
cards의 원소는 cards의 길이 이하인 임의의 자연수입니다.
cards에는 중복되는 원소가 존재하지 않습니다.
cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.

입출력 예

cards	result
[8,6,3,7,2,5,1,4]	12

풀이 방법

상자에 있는 번호를 따라서 다음 상자를 검색하는 방식이어서 dfs와 조금 유사하다고 생각했다. 이를 활용해 재귀함수를 통해 각 상자에 대한 방문 여부를 저장하고 방문하지 않은 경우에만 검사해서 모든 상자 그룹을 검사해서 가장 큰 값 2개만 찾아서 2개의 수를 곱해서 답을 도출했다.
-> 시간복잡도는 cards의 모든 값들을 한 번씩 순회하면서, dfs처럼 다른 값을 검사할 수도 있기 때문에 O(N)만큼 걸릴 것으로 추정되고, N은 최대 100이기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>

using namespace std;

int countBox(int i, vector<int>& cards, vector<bool>& visited){
    if(visited[i]) return 0;
    
    visited[i] = true;
    return (1 + countBox(cards[i] - 1, cards, visited));
}

int solution(vector<int> cards) {
    int n = cards.size();
    vector<bool> visited(n, false);
    int max1 = 0, max2 = 0;
    
    for(int i = 0; i < n; i++){
        int count = countBox(i, cards, visited);
        if(count > max1){
            max2 = max1;
            max1 = count;
        }else if(count > max2){
            max2 = count;
        }
    }
    
    return max1 * max2;
}