프로그래밍

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

[난이도] Gold4
[유형] BFS

[풀이]
최초 유포자들부터 queue에 넣고 bfs를 돌려주면 됩니다.
주의할 점이 루머를 믿는 사람에 인접한 사람을 검사할 때,
그 사람의 주변에 루머를 믿는 사람이 절반 이상이어도 바로 visit 체크를 하면 안되고
모든 검사가 끝난 뒤에 한번에 q에 넣고, visit 체크를 해주어야 합니다.
왜냐하면 다음 검사에 영향을 받을 수 있기 때문입니다.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
vector<int> adj[200001];
int N,M,visit[200001],ip,ans[200001];
queue<int> q;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        while(1){
            scanf("%d",&ip);
            if(ip==0) break;
            adj[i].push_back(ip);
        }
    }
    memset(ans,-1,sizeof(ans));
    scanf("%d",&M);
    for(int i=0;i<M;i++) {
        scanf("%d",&ip);
        q.push(ip);
        visit[ip]=1;
        ans[ip]=0;
    }
    int time=1;
    while(!q.empty()){
        int sz = q.size();
        vector<int> tmp;
        while(sz--){
            auto qf = q.front(); q.pop();
 
            for(auto nxt : adj[qf]){
                if(!visit[nxt]){
                    int cnt=0;
                    for(auto nadj : adj[nxt]){
                        cnt+=visit[nadj];
                    }
                    if(adj[nxt].size() <= 2*cnt){
                        tmp.push_back(nxt);
                        ans[nxt]=time;
                    }
                }
            }
        }
        for(auto t : tmp){
            q.push(t);
            visit[t]=1;
        }
        time++;
    }
    for(int i=1;i<=N;i++) printf("%d ",ans[i]);
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
간단한 Greedy + BFS 문제입니다.

그냥 BFS를 돌리면 N 범위가 10000000 이고, tc개수가 100이므로 시간초과가 발생합니다.
잘 생각해보면 0에서 N을 만들 때, ADDH 연산 (t+60)을 가장 많이 사는것이 연산 횟수를
줄이는데 유리합니다.

N/60 만큼 ADDH 연산을 사용한 뒤, N%60 을 ADDH 외의 연산으로 만들때의 최적값과,

N/60+1만큼 ADDH 연산을 사용한 뒤, 60-N%60을 ADDH 외의 연산으로 만들때의 최적값을

BFS를 이용해 각각 구해준 뒤, 연산 횟수가 더 적은 케이스를 답으로 출력해주면 됩니다.

예를 들어, N이 134라면 60*2 + 14 와 60*3 - 46 을 비교하는 것과 같습니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,N,a[]={10,-10,1,-1},visit[80];
vector<int> bfs(int k,int m){
    memset(visit,0,sizeof(visit));
    queue<vector<int>> q;
    visit[0]=1;
    q.push({0,0,0,0,0});
    while(1){
        int sz = q.size(); 
        while(sz--){
            auto cur = q.front(); q.pop();
            if(cur[4]==m) {
                vector<int> r = {k};
                for(int i=0;i<4;i++) r.push_back(cur[i]);
                return r;
            }
            for(int i=0;i<4;i++){
                int nxt = cur[4]+a[i];
                if(nxt<0 || nxt>70 || visit[nxt]) continue;
                visit[nxt]=1;
                auto nv = cur;
                nv[i]++;
                nv[4]=nxt;
                q.push(nv);
            }
        }
    }
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
 
        int k = N/60;
        int mod = N%60;
 
        auto ret1 = bfs(k,mod);
        int cnt1=0;
        for(int i=0;i<5;i++) cnt1+=ret1[i];
 
        auto ret2 = bfs(k+1,60-mod);
        int cnt2=0;
        for(int i=0;i<5;i++) cnt2+=ret2[i];
        swap(ret2[1],ret2[2]);
        swap(ret2[3],ret2[4]);
 
        if(cnt1>cnt2){
            for(int i=0;i<5;i++) printf("%d ",ret2[i]);
        }else{
            for(int i=0;i<5;i++) printf("%d ",ret1[i]);
        }
        puts("");
    }
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
visit[y][x][k] 배열을 이용해서 0,0부터 시작하는 BFS를 해주면 됩니다.
k==0인 경우는 검을 줍지 않은 상태라 벽을 통과 못하는 상태이고,
k==1인 경우는 검을 주워 벽을 무시할 수 있는 상태입니다.

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int N,M,T,board[101][101],visit[101][101][2];
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
struct P{
    int y,x,k;
};
int main(){
    scanf("%d%d%d",&N,&M,&T);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf("%d",&board[i][j]);
    queue<P> q;
    visit[0][0][0]=1;
    q.push({0,0,0});
    int cnt=0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            auto [y,x,k] = q.front(); q.pop();
            if(y==N-1&&x==M-1){
                printf("%d",cnt);
                return 0;
            }
            for(int i=0;i<4;i++){
                int ny=y+dy[i], nx=x+dx[i],nk=k;
                if(board[ny][nx]==2) nk=1;
                if(ny<0||nx<0||ny>=N||nx>=M||visit[ny][nx][nk]) continue;
                if(board[ny][nx]==1&&nk==0) continue;
                visit[ny][nx][nk]=1;
                q.push({ny,nx,nk});
            }
        }
        cnt++;
        if(cnt>T) break;
    }
    puts("Fail");
}

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

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

[난이도] Gold4
[유형] BFS

[풀이]
왼쪽 끝점을 기준으로 BFS를 돌려줍니다.
직사각형을 옮길 수 있을지 판단할 때, 세로H, 가로W의 모든 점을 검사하면 시간초과가 발생하게 되므로
누적합 배열을 미리 만들어 놓은 뒤, 옮길 위치의 사각형에 1(벽)이 포함되어 있는지를 O(1)에 판별하도록 해줍니다.

#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,board[1001][1001],H,W,sy,sx,ey,ex,sum[1001][1001];
bool visit[1001][1001];
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
bool check(int y,int x){
    if(y<1||x<1||y>N||x>M||y+H-1<1||x+W-1<1||y+H-1>N||x+W-1>M) return 0;
    if(sum[y+H-1][x+W-1]-sum[y-1][x+W-1]-sum[y+H-1][x-1]+sum[y-1][x-1]>0) return 0;
    return 1;
}
int bfs(){
    queue<pair<int,int>> q;
    q.push({sy,sx});
    visit[sy][sx]=1;
    int ret=0;
    while(!q.empty()){
        int sz= q.size();
        while(sz--){
            auto [y,x] =q.front(); q.pop();
            if(y==ey&&x==ex) return ret;
            for(int i=0;i<4;i++){
                int ny=y+dy[i];
                int nx=x+dx[i];
                if(!check(ny,nx) || visit[ny][nx]) continue;
                q.push({ny,nx});
                visit[ny][nx]=1;
            }
        }
        ret++;
    }
    return -1;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++) {
            scanf("%d",&board[i][j]);
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+board[i][j];
        }
 
    scanf("%d%d%d%d%d%d",&H,&W,&sy,&sx,&ey,&ex);
    printf("%d",bfs());
}

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

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

[난이도] Gold4
[유형] BFS

[풀이]
K마리의 소로 만들 수 있는 모든 쌍에 대해
길을 건너지 않고 서로 방문할 수 있는 쌍의 개수를 찾으면 됩니다.
길을 저장할 때 adj[101][101][101][101] 형식의 배열로 저장하는 것은 배열의 메모리 문제로
불가능 하므로 (r1,c1)<->(r2,c2) 의 길은 set<int> adj[20001] 형태의 set을 선언하여
adj[r1*N+c1].insert(r2*N+c2) 와 같이 set을 이용하여 저장해줍니다.

그 뒤, 모든 쌍의 소 간에 BFS를 통해 위에 미리 저장해놓은 길을 이용하지 않고 방문할 수 있는지를
구해주어, 정답에 방문할 수 있으면 0, 방문할 수 없으면 1을 더해주면
길을 건너지 않으면 만날 수 없는 소의 쌍을 구할 수 있습니다.

#include <cstdio>
#include <queue>
#include <set>
#include <vector>
#include <cstring>
using namespace std;
int N,K,R;
bool visit[101][101];
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
set<int> adj[20001];
vector<pair<int,int>> v;
int sol(int s,int e){
    memset(visit,0,sizeof(visit));
    queue<pair<int,int>> q;
    q.push({v[s].first,v[s].second});
    visit[v[s].first][v[s].second]=1;
    while(!q.empty()){
        auto [y,x] = q.front(); q.pop();
        if(y==v[e].first && x==v[e].second) return 0;
        for(int i=0;i<4;i++){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<1||nx<1||ny>N||nx>N||visit[ny][nx]||adj[y*N+x].find(ny*N+nx) != adj[y*N+x].end()) continue;
            q.push({ny,nx});
            visit[ny][nx]=1;
        }
    }
    return 1;
}
int main(){
    scanf("%d%d%d",&N,&K,&R);
    while(R--){
        int r1,c1,r2,c2;
        scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
        adj[r1*N+c1].insert(r2*N+c2);
        adj[r2*N+c2].insert(r1*N+c1);
    }
    while(K--){
        int y,x;
        scanf("%d%d",&y,&x);
        v.push_back({y,x});
    }
    int ans=0;
    for(int i=0;i<v.size()-1;i++)
        for(int j=i+1;j<v.size();j++) ans+=sol(i,j);
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
2인 점부터 시작해 갈수 있는 1인 점들을 순차적으로 방문하는 BFS를 이용하면 답을 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int N,M,board[1001][1001],sy,sx;
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
int visit[1001][1001];
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            scanf("%d",&board[i][j]);
            if(board[i][j]==2) sy=i,sx=j;
        }
    queue<pair<int,int>> q;
    q.push({sy,sx});
 
    int dist=1;
    while(!q.empty()){
        int sz=q.size();
        while(sz--){
            auto [y,x] = q.front(); q.pop();
            for(int i=0;i<4;i++){
                int ny=y+dy[i];
                int nx=x+dx[i];
                if(ny<0||nx<0||ny>=N||nx>=M||board[ny][nx]!=1||visit[ny][nx]) continue;
                q.push({ny,nx});
                visit[ny][nx]=dist;
            }
        }
        dist++;
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(visit[i][j]==0 && board[i][j]==1) printf("-1 ");
            else printf("%d ",visit[i][j]);
        }
        puts("");
    }
}

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

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

[난이도] Gold5
[유형] BFS

[풀이]
*,+,-,/를 모두 사용하면서 연산을 진행하면 굉장히 많은 경우의 수가 나올 것 같지만
생각해보면 '-'는 사용할 일이 없습니다. '-' 연산을 사용하면 무조건 0이 되는데
결과값인 t이 1 이상이기 때문에 어떤 입력에도 0을 만들 일이 없습니다.
'/'의 사용시 무조건 1을 만들기 때문에 최초 1회에만 사용하는 것이 의미가 있습니다.

결국 시작 숫자 s에서 *,+를 이용해 t를 만드는 경우와, 처음에 '/' 연산을 사용해
1을 만든 뒤 *,+를 이용해 t를 만드는 경우 둘 중 최적의 경우를 찾으면 됩니다.

수의 범위가 10^9이므로 많은 수가 등장할 것 같지만 +,* 연산을 이용할 경우 수가 큰 폭으로 증가하므로
10^9에 도달할 때까지 10^9만큼 많은 수가 등장하지는 않을 것입니다.
이를 이용해 set으로 visit한 숫자에 체크를 해주는 BFS를 사용할 수 있습니다.

s부터 시작해 t를 만든 경우, '/' 연산을 사용해 1부터 시작해 t를 만든 두 경우를 비교해서
최적의 답을 구해주면 됩니다.

#include <cstdio>
#include <string>
#include <set>
#include <iostream>
#include <queue>
using namespace std;
using ll = long long;
ll s,t;
string sol(ll sv,string sstr){
    queue<pair<ll,string>> q;
    q.push({sv,sstr});   
    set<ll> visit;
    visit.insert(sv);
    while(!q.empty()){
        auto [v,str] = q.front();
        q.pop();
        if(v==t) return str;
 
        if(v*v<=t && visit.find(v*v)==visit.end()) {
            visit.insert(v*v);
            q.push({v*v,str+"*"});
        }
        if(v+v<=t && visit.find(v+v)==visit.end()) {
            visit.insert(v+v);
            q.push({v+v,str+"+"});
        }
 
    }     
    return "0";
}
int main(){
    cin >> s >> t;
    if(s==t) {
        cout << 0;
        return 0;
    }
    string ans1 = sol(s,"");
    string ans2 = sol(1,"/");
    if(ans1=="0" && ans2=="0") cout << -1;
    else if(ans1=="0") cout << ans2;
    else if(ans2=="0") cout << ans1;
    else {
        if(ans1.size()<ans2.size()) cout << ans1;
        else if(ans1.size()>ans2.size()) cout << ans2;
        else{
            if(ans1<ans2) cout << ans1;
            else cout << ans2;    
        }   
    }
}

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

https://codeforces.com/contest/1598/problem/A

[난이도] Div.2
[유형] BFS

[풀이]
BFS를 이용해 (2,n) 까지 도달이 가능하면 YES를 출력해줍니다.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
int t,n,mp[3][101];
bool visit[3][101];
int dy[4] = {1,0,1,-1};
int dx[4] = {1,1,0,1};
bool bfs(){
 
    queue<pair<int,int>> q;
    memset(visit,0,sizeof(visit));
 
    q.push({1,1});
    visit[1][1]=1;
 
    while(!q.empty()){
 
        auto [y,x] = q.front(); q.pop();
        if(y==2&&x==n) return true;
        for(int i=0;i<4;i++){
            int ny=y+dy[i], nx=x+dx[i];
            if(ny<1||nx<1||ny>2||nx>n||visit[ny][nx]||mp[ny][nx]) continue;
            visit[ny][nx]=1;
            q.push({ny,nx}); 
        }
    }
    return false;
}
 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=2;i++)
            for(int j=1;j<=n;j++) scanf("%1d",&mp[i][j]);
        puts(bfs()?"YES":"NO");
 
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU115-Div.2/A.cpp