프로그래밍

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

[난이도] Gold5
[유형] BFS

[풀이]
1~N의 모든 회원을 시작점으로 BFS를 돌리면서 가장 먼 회원과의 거리를 구한 뒤 point[i]에 저장한다.
point[i] (i:1~N) 중 가장 적은 값을 가지고 있는 회원들이 회장 후보이다.

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int N,point[51],visit[51];
vector<int> adj[51];

int sol(int k){
    memset(visit,0,sizeof(visit));
    queue<int> q;
    visit[k]=1;
    q.push(k);
    int ret=0;
    while(!q.empty()){
        int qf = q.front(); q.pop();
        ret=max(ret,visit[qf]);
        for(int nxt : adj[qf]){
            if(!visit[nxt]){
                visit[nxt]=visit[qf]+1;
                q.push(nxt);
            }
        }
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    while(1){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a==-1) break;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int mv = 1e7;
    vector<int> ans;
    for(int i=1;i<=N;i++) {
        point[i]=sol(i);
        mv=min(mv,point[i]);
    }
    for(int i=1;i<=N;i++) 
        if(point[i]==mv) ans.push_back(i);

    printf("%d %d\n",mv-1,ans.size());
    for(auto a : ans) printf("%d ",a);
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
visit[a][b] 배열을 이용해 BFS를 진행한다. a:현재 이모티콘의 수, b:클립보드에 복사되어 있는 이모티콘의 수
S의 최댓값이 1000이므로 배열의 크기는 1500으로 여유롭게 잡는다. 클립보드에 있는 이모티콘을 복사하면 1000을 넘을 수 있지만 2000을 넘기는 것은 의미가 없으므로 1500으로 잡았더니 AC를 받았다.

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int S,visit[1500][1500];
int main(){
    scanf("%d",&S);

    queue<pair<int,int>> q;
    visit[1][0]=1;
    q.push({1,0});
    int ans =0;
    while(!q.empty()){
        int sz=q.size();
        while(sz--){
            int a = q.front().first;
            int b = q.front().second; q.pop();
            if(a==S) {
                printf("%d",ans);
                return 0;
            }
            if(a-1>=0 && !visit[a-1][b]){
                visit[a-1][b]=1;
                q.push({a-1,b});
            }
            if(b>0 && a+b < 1500 && !visit[a+b][b]){
                visit[a+b][b]=1;
                q.push({a+b,b});
            }
            if(!visit[a][a]){
                visit[a][a]=1;
                q.push({a,a});
            }
        }
        ans++;
    }
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
모든 가능한 경우를 구해야 하므로 단순 특정 점에 방문했는지 유무만 기록하면 안되고
몇 초만에 처음 방문했는지를 기록해놔야 모든 경우에 대해 구할 수 있다. (dist[nxt] = dist[cur]+1 과 같이..)

#include <cstdio>
#include <queue>
using namespace std;
int N,K,visit[100001];
int main(){
    scanf("%d%d",&N,&K);

    queue<int> q;
    q.push(N);
    int t=0,ans=0;
    while(!q.empty()){
       
        int sz=q.size();   
        while(sz--){
            int cur=q.front(); q.pop();
            if(cur==K) ans++;
            
            for(auto nxt : {cur-1,cur+1,cur*2}){
                if(nxt<0 || nxt>1e5) continue;
                if(!visit[nxt] || visit[nxt]==visit[cur]+1){
                    visit[nxt]=visit[cur]+1;
                    q.push(nxt);
                }
            }
        }
        if(ans>0) break;
        t++;
    }
    printf("%d\n%d",t,ans);
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
x2를 하는 연산에는 시간이 들지 않으므로
BFS를 하면서 queue에 넣을 때 x2를 해주면서 도착할 수 있는 모든 지점을
넣어주면 답을 구할 수 있다.

#include <cstdio>
#include <queue>
using namespace std;
int N,K;
bool visit[100001];
queue<int> q;
void push(int k){
    while(k<=1e5){
        if(!visit[k]){
            visit[k]=1;
            q.push(k);
        }
        if(k==0) return;
        k*=2;
    }
}
int main(){
    scanf("%d%d",&N,&K);
    push(N);
    int cnt=0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            int cur = q.front(); q.pop();
            if(cur==K){
                printf("%d",cnt);
                return 0;
            }
            int k;
            if(cur+1<=1e5) {
                k=cur+1;
                push(k);
            }
            if(cur-1>=0){
                k=cur-1;
                push(k);
            }
        }
        cnt++;
    }
}

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

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

[난이도] Gold4
[유형] BFS

[풀이]
1~9999의 숫자중에 소수를 미리 구해 놓은 뒤.
visit[10000] 와 같은 배열을 선언해서
처음 주어진 숫자부터 한 자리씩 바꿔가며 BFS를 진행하면 된다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int T,a,b;
bool visit[10000],prime[10000];
int main(){
    
    prime[1]=1;
    for(int i=2;i<10000;i++){
        if(prime[i]) continue;
        for(int j=i*2;j<10000;j+=i) prime[j]=1;
    }
    scanf("%d",&T);
    while(T--){
        
        scanf("%d%d",&a,&b);
        memset(visit,0,sizeof(visit));

        queue<int> q;
        q.push(a);
        visit[a]=1;
        int cnt=0;
        bool ok=0;
        while(!q.empty()){

            int sz=q.size();
            while(sz--){

                int qf = q.front(); q.pop();
                if(qf==b){
                    printf("%d\n",cnt);
                    ok=1;
                    break;
                }
                string cur = to_string(qf);
                for(int i=0;i<cur.size();i++){
                    for(int j=0;j<10;j++){
                        if((i==0&&j==0) || (cur[i]-'0')==j) continue;
                        string nxt = cur;
                        nxt[i]=j+'0';
                        int ni= stoi(nxt);
                        if(prime[ni] || visit[ni]) continue;
                        visit[ni]=1;
                        q.push(ni);
                    }
                }
            }
            if(ok) break;
            cnt++;
        }
        if(!ok) puts("Impossible");
    }
}

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

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

[난이도] Gold2
[유형] BFS

[풀이]
check[10][10][10][10] 크기의 배열을 선언해서 메모제이션 해주면서 BFS를 돌려준다.
빨간공의 (y,x) , 파란공의 (y,x) 좌표를 메모제이션 한다. 범위가 10까지이기 때문에 무리없이 가능하다.
공을 골리는 시뮬레이션 시, 빨간공이 구멍에 통과하더라도 파란공과 같은 선에 있으면 파란공도 통과하게 되어
실패하게 되는 것에 주의해야 한다.

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int N,M;
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int ans=9e8;
bool check[10][10][10][10];
char map[10][10];
struct P{
    int y,x,rd;
};
struct RB{
    P r,b;
    int k;
};

int main(){

    scanf("%d%d",&N,&M);
    RB p;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='R') {
                p.r.y=i,p.r.x=j,p.r.rd=1;
                map[i][j]='.';
            }
            if(map[i][j]=='B') {
                p.b.y=i,p.b.x=j,p.b.rd=0;
                map[i][j]='.';
            }
        }
    }

    queue<RB> q;
    q.push(p);
    check[p.r.y][p.r.x][p.b.y][p.b.x]=1;

    int cnt=1;
    while(!q.empty()){

        int sz=q.size();
        while(sz--){

            auto qf = q.front(); q.pop();
            P r=qf.r, b=qf.b;
            for(int k=0;k<4;k++){
                P u=r,v=b;
                if(k==0) {
                    if(u.y>v.y) swap(u,v);
                }else if(k==1){
                    if(u.y<v.y) swap(u,v);
                }else if(k==2){
                    if(u.x<v.x) swap(u,v);
                }else {
                    if(u.x>v.x) swap(u,v);
                }

                int ny=u.y,nx=u.x;
                int fy,fx,fr,sy,sx,sr;
                bool ctn=0,t=0;
                while(1){
                    ny+=dy[k],nx+=dx[k];

                    if(map[ny][nx]=='#'){
                        ny-=dy[k],nx-=dx[k];
                        fy=ny,fx=nx,fr=u.rd;
                        break;
                    }
                    if(map[ny][nx]=='O'){
                        if(!u.rd) {
                            ctn=1;
                            break;
                        }
                        t=1;
                        break;
                    }
                }
                if(ctn) continue;

                ny=v.y,nx=v.x;
                while(1){
                    ny+=dy[k],nx+=dx[k];
                    if(map[ny][nx]=='#' || (ny==fy && nx==fx)){
                        ny-=dy[k],nx-=dx[k];
                        sy=ny,sx=nx,sr=v.rd;
                        break;
                    }

                    if(map[ny][nx]=='O'){
                        if(!v.rd){
                            ctn=1;
                            break;
                        }
                        t=1;
                        break;
                    }
                }
                if(ctn) continue;

                if(t) {
                    printf("%d",cnt);
                    return 0;
                }
                u={fy,fx,fr};
                v={sy,sx,sr};
                if(!u.rd) swap(u,v); 

                if(!check[u.y][u.x][v.y][v.x]){
                    check[u.y][u.x][v.y][v.x]=1;
                    RB nxt;
                    nxt.r=u;
                    nxt.b=v;
                    nxt.k=k;
                    q.push(nxt);
                }
            }
        }
        cnt++;
    }
    puts("-1");
}

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

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

[난이도] Gold2
[유형] BFS

[풀이]
모든 경우에 6가지 물통간 이동이 가능하다. 6^k 개씩 계속 경우가 늘어날 것 같지만
(p,q)를 현재 A,B 물통의 물의 양이라고 했을 때, (p,q)의 경우의 수가 몇개 나오지 않는다고 한다.
(정확한 증명은 어렵지만 물을 전체 다넣거나, 전체 다빼거나, 전체 다옮기거나 하는 단순한 연산들만 반복해서 그렇게 되는 것 같다.)

BFS인 것을 눈치채도 A,B가 최대 100000까지 나오므로 배열로는 메모리 초과를 당하게 된다.

그러므로 set memo[100001]; 와 같이 set을 이용해야 한다.
(1,3)이라면 mem[1].insert(3) 과 같이 저장할 수 있다.
이후 풀이는 일반 BFS와 동일하다.

#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
int cap[2],tar[2];
set<int> memo[100001];
queue<pair<int,int>> q;
int main(){
    scanf("%d%d%d%d",&cap[0],&cap[1],&tar[0],&tar[1]);

    q.push({0,0});
    memo[0].insert(0);
    int ret=0;
    while(!q.empty()){

        int sz=q.size();
        while(sz--){
            auto qf = q.front(); q.pop();
            int v[2];
            v[0]=qf.first, v[1]=qf.second;
            if(v[0]==tar[0] && v[1]==tar[1]){
                printf("%d",ret);
                return 0;
            }
            for(int i=0;i<6;i++){
                int a,b;
                if(i==0) a=cap[0],b=v[1];
                else if(i==1) a=v[0],b=cap[1];
                else if(i==2) a=0,b=v[1];
                else if(i==3) a=v[0],b=0;
                else if(i==4) a=min(cap[0],v[0]+v[1]), b=v[1]-min(cap[0]-v[0],v[1]);
                else a=v[0]-min(cap[1]-v[1],v[0]),b=min(cap[1],v[1]+v[0]);

                if(memo[a].find(b) == memo[a].end()){
                    memo[a].insert(b);
                    q.push({a,b});
                }
            }
        }
        ret++;
    }
    puts("-1");
}

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

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

[난이도] Gold3
[유형] BFS

[풀이]
각 물건이 5개밖에 되지 않으므로 11111 이런식의 bitmask로 처리할 수 있다.
visit[50][50][1<<5] 크기의 배열을 선언해서 BFS를 해준다.
각 물건에 0~4 의 번호를 먹인 뒤 bit연산을 이용해 어떤 물건들을 챙긴 상태인지를
체크할 수 있다.

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

#include <cstdio>
#include <queue>
using namespace std;
int N,M,S,E,sy,sx,ey,ex,visit[50][50][1<<5];
char map[50][50];
int pos[50][50],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
struct P{
    int y,x,bmsk;
};
int main(){
    scanf("%d%d",&N,&M);
    int p=0;
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='S') sy=i,sx=j;
            else if(map[i][j]=='E') ey=i,ex=j;
            else if(map[i][j]=='X') pos[i][j]=p++;
        }
    }
    queue<P> q;
    visit[sy][sx][0]=1;
    q.push({sy,sx,0});
    int cnt = 0;
    while(!q.empty()){
        int qsz = q.size();
        while(qsz--){

            P f = q.front(); q.pop();
            if(f.y==ey&&f.x==ex&&f.bmsk==(1<<p)-1){
                printf("%d",cnt);
                return 0;
            }
            for(int i=0;i<4;i++){
                int ny=f.y+dy[i], nx=f.x+dx[i];
                if(ny<0||nx<0||ny>=M||nx>=N||map[ny][nx]=='#') continue;

                if(map[ny][nx]=='X'){
                    int b = f.bmsk|(1<<pos[ny][nx]);
                    if(!visit[ny][nx][b]){
                        visit[ny][nx][b]=1;
                        q.push({ny,nx,b});
                    }
                }else{
                    if(!visit[ny][nx][f.bmsk]){
                        visit[ny][nx][f.bmsk]=1;
                        q.push({ny,nx,f.bmsk});
                    }
                }
            }
        }
        cnt++;
    }
}