2024 - 09- 26 C++ 코딩테스트 10주완성 D+42

백준 1987 문제 - 알파벳

 

세로 R$R$칸, 가로 C$C$칸으로 된 표 모양의 보드가 있다.

 

보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1$1$행 1$1$열) 에는 말이 놓여 있다.

 

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

 

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오.

 

말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

입력

 

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1<=R, C<=20)

둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

출력

 

첫째 줄에 말이 지날 수 있는 최대 칸 수를 출력한다.

#include <bits/stdc++.h>

using namespace std;

//1. 변수 목록
//보드의 행과 열의 정보를 입력받을 정수형 변수 R,C
//보드의 정보를 입력받을 2차원 문자열 행렬 board
//지나간 칸을 카운트할 정수형 변수 Cnt
//지나간 알파벳을 집어넣을 문자열 queue q
//상하좌우 이동할 방향의 정보를 담을 1차원 정수형 배열 dy,dx
int R,C,Cnt;
char board[24][24];
queue<pair<int,int>> q;
int dy[4] = {-1, 0 , 1 ,0};
int dx[4] = {0 , 1 , 0 , -1};
int visited[24][24];
vector<pair<int,char>> vfind;

//각각의 탐색루틴마다 내부 queue를 선언하여서 그 queue 랑 비교하여서 알파벳이 있는 확인한후
//나온 결괏값중에 최대를 출력
// void go(int y,int x)
// {
//     for(int i = 0; i < 4; i++)
//     {
//         int ny = y + dy[i];
//         int nx = x + dx[i];

//         if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;

//         for(char a : q)
//         {
//             if(a == board[ny][nx]) return;
//         }
//     }
    
// }

int main()
{
    cin >> R >> C;

    for(int i =0; i < R; i++)
    {
        string str = "";
        cin >> str;
        for(int j =0; j < str.size(); j++)
        {
            board[i][j] = str[j];
        }
    }
    q.emplace(0,0);
    visited[0][0] = 1;
    //맨처음 단어를 넣어준다.
    vfind.emplace_back(0,board[0][0]);
    
    while(q.size())
    {
        
        bool isflag = false;
        
        int y = q.front().first / 1000;
        int x = q.front().first % 1000;        
        int prevy = q.front().second / 1000;
        int prevx = q.front().second % 1000;
        
        q.pop();
        
        

        for(int i =0 ;  i< 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];            
            
            if(ny < 0 || ny >= R || nx < 0 || nx >= C || (ny == prevy && nx == prevx)) continue;            

            for(pair<int,char> a : vfind)
            {
                if(a.second == board[ny][nx]) 
                {
                    isflag = true;
                    if(Cnt < visited[y][x]) Cnt = visited[y][x];
                    break;
                } 
            }
            if(!isflag) 
            {               
                q.emplace(ny*1000 + nx,y * 1000 + x);
                visited[ny][nx] = visited[y][x] + 1;
                //가면서 방문한곳을 초기화
                visited[y][x] = 0;
            }
        }
        
        
    }
    cout << Cnt;
        
}

 

이 코드는 BFS 탐색으로 각 탐색마다 지나간 경로의 알파벳을 저장하는 것이 핵심로직이다.

 

근데 각 탐색마다 지나간 경로의 알파벳을 저장하는 로직이 아무리 생각해도 잘 모르겠다..

 

이번에도 나혼자 문제 푸는 것은 실패하였다.... ㅠㅠ

 

강의 실습코드를 한번 보자.

 

#include <bits/stdc++.h>
using namespace std;
int R, C, ret, ny, nx, visited[30];
char a[21][21];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = { 0, 1, 0, -1}; 
void go(int y, int x, int cnt){
    ret = max(ret, cnt);
    for(int i = 0; i < 4; i++){
        ny = y + dy[i], nx = x + dx[i];
        if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
        int next = (int)(a[ny][nx] - 'A');
        
        if(visited[next] == 0){
            visited[next] = 1; 
            go(ny, nx, cnt + 1);
            visited[next] = 0;  
        } 
    }
    return;
}
int main(){
    cin >> R >> C;
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> a[i][j];
        }
    }
    visited[(int)a[0][0] - 'A'] = 1;
    go(0, 0, 1);
    cout << ret << '\n';
    return 0;
}

 

강사님이 이 문제는 되게 쉽다고 말씀하시길래.. 1차 현타..

 

그리고 이 강의 코드를 보면서 2차현타가 왔다..

 

BFS 탐색으로 추측한것도 틀렸고, 코드자체도 되게 간단하고 명료하다..

 

이 문제에서는 1차원 정수형 배열 visited 를 이용하여 탐색의 알파벳 여부를 판단하는게 핵심로직이다.

 

visited 를 이용하여, 완전탐색으로 재귀함수를 쓰기전에 visited[해당알파벳] 이 0이면 그 알파벳이

 

그 탐색에서 없었다는 말이 되니, visited[해당알파벳] = 1 을 해주고 다시 재귀함수를 돌린다.

 

그리고 재귀함수 밑 코드에 visited[해당알파벳] = 0 을 써줌으로써 재귀함수가 끝난다음에 탐색한 끝 위치부터 처음까지

 

전부 0으로 만들어버리고 다음 탐색으로 넘어가므로.. 문제가 없다..!! 재귀함수에 대해 조금 안다고 생각했지만,

 

내가 이해하고 있는 한계점이 너무나 큰 것 같다... 복습하고 또 복습하자! 

 

---

 

백준 2529 문제 - 부등호

 

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다.

 

우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

 

A ⇒ < < < > < < > < >

 

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다.

 

아래는 부등호 순서열 A를 만족시키는 한 예이다. 

 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

 

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다.

 

예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

 

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다.

 

앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

 

입력

 

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다.

그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

 

출력

 

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다.
(단, 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.) 

 

실습코드

 

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, check[10];
char a[20];
vector<string> ret;  
bool good(char x, char y, char op){ 
	if(x < y && op == '<') return true; 
	if(x > y && op == '>') return true; 
	return false; 
}
void go(int idx, string num){ 
	if(idx == n + 1){
		
		ret.push_back(num); return;
	}
	for(int i = 0; i <= 9; i++){
		if(check[i]) continue; 
		if(idx == 0 || good(num[idx - 1], i + '0', a[idx - 1])){
			check[i] = 1;
			go(idx + 1, num + to_string(i));
			check[i] = 0;
		}
	}
	return;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    cin >> n; 
    for(int i = 0; i < n; i++) cin >> a[i]; 
    go(0, "");
    sort(ret.begin(), ret.end());
    cout << ret[ret.size() - 1] << "\n" << ret[0] << "\n";
}

 

이 코드는 DFS 탐색을 이용한 탐색과 ret이라는 벡터를 이용한 최대 최솟값을 도출하는 것이 핵심 로직이다.

 

void go(int idx, string num) 이라는 함수안에 들어 있는 반복문으로

 

부등호안에 들어갈 맨 처음 숫자를 0 ~ 9 까지 반복문을 돌려서 ret 이라는 벡터값에 저장해둔다.

 

그리고 ret안의 원소를을 오름차순으로 정렬해주면

 

최솟값과 최댓값을 도출해낼 수 있다.. 정말 간단한데 생각이 나질 않았다.. 계속 노력해봐야겠다