2024 - 09- 26 C++ 코딩테스트 10주완성 D+42
백준 1987 문제 - 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다.
보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (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안의 원소를을 오름차순으로 정렬해주면
최솟값과 최댓값을 도출해낼 수 있다.. 정말 간단한데 생각이 나질 않았다.. 계속 노력해봐야겠다