프로그래밍

https://www.acmicpc.net/problem/15664

[난이도] Silver2
[유형] 백트래킹

[풀이]
오름차순으로 출력해야 하기 때문에 정렬 후에 백트래킹을 해주면 됩니다.
중복 제거를 위해 set을 이용하였습니다.

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int N,M,a[8];
set<vector<int>> st;
vector<int> ans;
void sol(int n){
    if(n==N){
        if(ans.size()==M) {
            if(st.find(ans) == st.end()){
                st.insert(ans);
                for(auto k : ans) printf("%d ",k);
                puts("");
            }
        }
        return;
    }
    ans.push_back(a[n]);
    sol(n+1);
    ans.pop_back();
    sol(n+1);
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);
    sol(0);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/15664.cpp

https://programmers.co.kr/learn/courses/30/lessons/92342

[난이도] level2
[유형] 백트래킹

[풀이]
라이언이 N개의 화살을 각 과녁에 쏠 수 있는 모든 경우의 수를 백트래킹으로 구해주면 됩니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
vector<int> info,ans;
int ansv=-1,n;
void cmp(vector<int> v){
    int a=0,b=0;
    for(int i=0;i<=10;i++){
        if(info[i]==0&&v[i]==0) continue;
        if(info[i]>=v[i]){
            a+=10-i;
        }else{
            b+=10-i;
        }
    }
    if(b>a){
        if(ansv<b-a){
            ansv=b-a;
            ans=v;
        }else if(ansv==b-a){
            vector<int> rans=ans,rv=v;
            reverse(rans.begin(),rans.end());
            reverse(rv.begin(),rv.end());
            if(rv>=rans){
                ans=v;
            }
        }
    }
}
void sol(int m,int cur,vector<int> v){
    if(m==11){
        if(cur!=0) return;
        cmp(v);
        return;
    }
    for(int i=0;i<=cur;i++){
        v.push_back(i);
        sol(m+1,cur-i,v);
        v.pop_back();
    }
}
vector<int> solution(int _n, vector<int> _info) {
    info=_info;
    n=_n;
    sol(0,n,{});
    if(ansv==-1) ans={-1};
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/양궁대회.cpp

https://www.acmicpc.net/problem/7682

[난이도] Gold5
[유형] 백트래킹

[풀이]
보드가 3x3 밖에 되지 않으므로 백트래킹을 이용해
나올 수 있는 모든 경우의 수를 해보면서 게임이 끝나는 보드의 모양이 나올 때, 정답 set에 넣어주면 됩니다.

#include <iostream>
#include <string>
#include <cstring>
#include <set>
using namespace std;
int a[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
int board[3][3];
string s;
set<string> ans;
bool check(string t,int i){
    if(t[a[i][0]]=='.') return 0;
    for(int j=1;j<3;j++){
        if(t[a[i][0]]!=t[a[i][j]]) return 0;
    }
    return 1;
}
void sol(int n){
    string tmp;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(board[i][j]==1) tmp+='X';
            else if(board[i][j]==2) tmp+='O';
            else tmp+='.';
        }
    }
    for(int i=0;i<8;i++){
        if(check(tmp,i)){
            ans.insert(tmp);
            return;
        }
    }
    if(n==9) {
        ans.insert(tmp);
        return;
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(board[i][j]!=0) continue;
            board[i][j] = n%2+1;
            sol(n+1);
            board[i][j]=0;
        }
    }
}
int main(){
    sol(0);
    while(1){
        cin >> s;
        if(s=="end") return 0;
        if(ans.find(s) !=ans.end()) puts("valid");
        else puts("invalid");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/7682.cpp

https://www.acmicpc.net/problem/1278

[난이도] Gold3
[유형] 백트래킹

[풀이]
N이 17밖에 되지 않기 때문에 백트래킹 함수의 인자로 비트마스크를 전달해서
현재 연극에 몇번 사람이 참여하고 있는지 체크할 수 있고, 비트연산을 이용해
한명씩 추가하거나 뺄 수 있습니다.
visit 배열을 선언하여 체크한 비트마스크는 체크를 해서 중복해서 방문하지 않도록 해줍니다.

#include <cstdio>
#include <vector>
using namespace std;
int N,visit[1000000],ansn;
vector<int> cur,ans;
void sol(int n,int m){
    if(n!=0&&m==0&&n>ansn){
        ansn=n;
        ans=cur;
        return;
    }
    for(int i=0;i<N;i++){
        if(((1<<i)&m)>0){
            int k=(~(1<<i))&m;
            if((n!=0&&k==0)||!visit[k]){
                visit[k]=1;
                cur.push_back(i);
                sol(n+1,k);
                cur.pop_back();
            }
        }
        if(((1<<i)&m)==0){
            int k=(1<<i)|m;
            if(!visit[k]){
                visit[k]=1;
                cur.push_back(i);
                sol(n+1,k);
                cur.pop_back();
            }
        }
    }
}
int main(){
    scanf("%d",&N);
    sol(0,0);
    printf("%d\n",ansn-1);
    for(auto a : ans) printf("%d ",a+1);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/1278.cpp

https://www.acmicpc.net/problem/2026

[난이도] Gold3
[유형] 백트래킹

[풀이]
인접행렬에 친구관계를 저장 해준 뒤, 재귀를 이용한 백트래킹을 해주면 됩니다.
현재까지 확정된 친구를 frd vector에 저장해준 뒤, 현재 친구가 될 수 있는지 확인중인 친구가
이 frd vector의 친구와 모두 친구인지 확인해서, 모두 친구이면 다음 함수를 호출해줍니다.
frd vector의 크기가 K(<=62)가 되면 조건을 만족하는 친구집합을 구한 것이므로 출력하고 종료해줍니다.
frd vector의 크기가 최대 62를 넘어갈 수 없으므로 시간내에 해결이 가능합니다.

#include <cstdio>
#include <vector>
using namespace std;
int K,N,F,adj[901][901];
vector<int> frd;
bool sol(int cur){
    if(frd.size()==K) return 1;
    for(int i=cur+1;i<=N;i++){
        bool ok=1;
        for(auto a : frd){
            if(!adj[i][a]){
                ok=0;
                break;
            }
        }
        if(ok) {
            frd.push_back(i);
            if(sol(i)) return 1;
            frd.pop_back();
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&K,&N,&F);
    while(F--){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u][v]=adj[v][u]=1;
    }
    for(int i=1;i<=N;i++){
        frd.push_back(i);
        if(sol(i)){
            for(auto f : frd) printf("%d\n",f);
            return 0;
        }
        frd.clear();
    }
    puts("-1");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2026.cpp

https://www.acmicpc.net/problem/7490

[난이도] Gold5
[유형] 백트래킹

[풀이]
현재 값에 숫자를 한개만 사용해서 더하거나 빼주는 경우,
두개를 합쳐서 더하거나 빼주는 경우를 모두 해주는 백트래킹 함수를 작성하면 됩니다.
식을 출력해야 하기 때문에 전체 식을 함수의 인자로 전달하면서
정답인 경우에는 vector에 저장해줍니다.
오름차순으로 출력하려면  vector를 정렬해주기만 하면 됩니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int tc,N;
vector<string> ans;
void sol(int n,int v,string str){
    if(n==N+1) {
        if(v==0) ans.push_back(str.substr(1));
        return;
    }
    sol(n+1,v+n,str+"+"+to_string(n));
    if(n<=N-1) sol(n+2,v+10*n+n+1,str+"+"+to_string(n)+" "+to_string(n+1));
 
    if(n==1) return;
 
    sol(n+1,v-n,str+"-"+to_string(n));
    if(n<=N-1) sol(n+2,v-(10*n+n+1),str+"-"+to_string(n)+" "+to_string(n+1));
}
int main(){
    cin >> tc;
    while(tc--){
        cin >> N;
        sol(1,0,"");
        sort(ans.begin(),ans.end());
        for(auto a : ans) cout << a << '\n';
        cout << '\n';
        ans.clear();
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/7490.cpp

https://www.acmicpc.net/problem/6987

[난이도] Gold5
[유형] 백트래킹

[풀이]
총 6개의 0~5번 팀이 있다고 했을 때, 게임은 아래와 같이 총 15개가 나옵니다.
{{0,1},{0,2},{0,3},{0,4},{0,5},
 {1,2},{1,3},{1,4},{1,5},
 {2,3},{2,4},{2,5},
 {3,4},{3,5},
 {4,5}}

(p,q)가 게임하는 게임에 대해 p승,q패 / p패, q승 / p무, q무 총 3가지 경우가 나옵니다.
15개의 각 게임에 대해 백트래킹을 이용하여 3가지 경우를 모두 해보는 방식으로 문제를 해결할 수 있습니다.
3^15 = 14348907 이므로 시간내에 해결이 가능합니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int a[6][3];
pair<int,int> g[] = {{0,1},{0,2},{0,3},{0,4},{0,5},
                     {1,2},{1,3},{1,4},{1,5},
                     {2,3},{2,4},{2,5},
                     {3,4},{3,5},
                     {4,5}};
bool sol(int n){
    if(n==15){
        for(int i=0;i<6;i++)
            for(int j=0;j<3;j++) if(a[i][j]) return false;
        return true;  
    }
    auto [p,q] = g[n];
    if(a[p][1] && a[q][1]) {
        a[p][1]--,a[q][1]--;
        if(sol(n+1)) return true;
        a[p][1]++,a[q][1]++;
    }
    if(a[p][0] && a[q][2]) {
        a[p][0]--,a[q][2]--;
        if(sol(n+1)) return true;
        a[p][0]++,a[q][2]++;
    }
    if(a[p][2] && a[q][0]) {
        a[p][2]--,a[q][0]--;
        if(sol(n+1)) return true;
        a[p][2]++,a[q][0]++;
    }
    return false;
}
int main(){
    for(int i=0;i<4;i++){
        for(int j=0;j<6;j++)
            for(int k=0;k<3;k++) scanf("%d",&a[j][k]);
        printf("%d ",sol(0));
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/6987.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=577

[난이도] level3
[유형] 백트래킹

[풀이]
먼저 파악해야 할 것이 로봇은 '#' 로 표시된 점 이외에는 절대로 방문하지 않고
한붓그리기 처럼 '#' 점을 한방에 방문해야 합니다.
로봇이 두칸씩 전진하고, 사용한 명령어를 저장해야 하기 때문에 BFS 혹은 DFS 푸는 것은 어렵다고 판단하여
백트래킹을 이용하였습니다.

'#'인 점만 방문하고, 두칸씩 전진함에 따라 많은 경로가 제외되기 때문에 시간내에 해결이 가능합니다.

커맨드를 최소로 하기 위해 어느 점에서 시작해야 최적인지
'#'인 모든 점에 대해 모든 4방향을 시작점으로 백트래킹을 돌려봐야 합니다.

백트래킹 함수 void sol(int y,int x,int d,int cnt,string cmd)
에서 d는 방향, cnt는 현재까지 방문한 '#' 개수, cmd는 현재까지 사용한 커맨드 string입니다.

어떤 점에 도착했을 때 할 수 있는 전진은 총 4가지 입니다.
좌측으로 회전 뒤 전진("LA")
좌측으로 두번 회전 뒤 전진("LLA")
우측으로 한번 회전 뒤 전진("RA") <- ("LLLA)와 같지만 연산 횟수가 역방향으로 돌리는 "RA"가 더 적습니다.
현재 방향으로 전진 ("A")

위 4가지 케이스에 대해 백트래킹 함수를 다시 호출해주면 됩니다.

#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
int H,W,ansd,ansy,ansx,sd,sy,sx;
char map[27][27];
bool visit[27][27];
vector<pair<int,int>> cand;
string ret="-1";
 
void sol(int y,int x,int d,int cnt,string cmd){
 
    if(cand.size()==cnt){
        if(ret=="-1" || cmd.size() < ret.size()){
            ret=cmd;
            ansy=sy,ansx=sx,ansd=sd;
            ansd=sd;
        }
        return;
    }
 
    for(int i=0;i<4;i++){
        int nd=(d+i)%4;
        string nxt="A";
        if(i==1) nxt="LA";
        else if(i==2) nxt="LLA";
        else if(i==3) nxt="RA";
 
        int ny1=y+dy[nd], nx1=x+dx[nd];
        int ny2=y+2*dy[nd], nx2=x+2*dx[nd];
 
        if(ny2<1||nx2<1||ny2>H||nx2>W) continue;
        if(map[ny1][nx1]!='#' || map[ny2][nx2]!='#' || visit[ny1][nx1] || visit[ny2][nx2]) continue;
 
        visit[ny1][nx1] = visit[ny2][nx2] = 1;
        sol(ny2,nx2,nd,cnt+2,cmd+nxt);
        visit[ny1][nx1] = visit[ny2][nx2] = 0;
    }
}
int main(){
    scanf("%d%d",&H,&W);
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='#') cand.push_back({i,j});
        }
    }
    for(auto [y,x] : cand){
        sy=y, sx=x;
        for(int k=0;k<4;k++){
            sd=k;
            memset(visit,0,sizeof(visit));
            visit[y][x]=1;
            sol(y,x,k,1,"");
        }
    }
    char cd = 'v';
    if(ansd==1) cd= '>';
    else if(ansd==2) cd='^';
    else if(ansd==3) cd='<';
 
    printf("%d %d\n",ansy,ansx);
    printf("%c\n",cd);
    printf("%s",ret.c_str());
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/로봇이_지나간_경로.cpp