프로그래밍

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

[난이도] Silver1
[유형] DFS

[풀이]
dfs 기본문제 입니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[501][501],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},cnt,ans;
int dfs(int y,int x){
    a[y][x]=2;
    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i], nx=x+dx[i];
        if(ny<0||nx<0||ny>=n||nx>=m||a[ny][nx]!=1) continue;
        ret+=dfs(ny,nx);
    }
    return ret;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) scanf("%d",&a[i][j]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]==1){
                cnt++;
                ans = max(ans,dfs(i,j));
            }
        }
    }
    printf("%d\n%d",cnt,ans);
}

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

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

[난이도] Gold3
[유형] DFS

[풀이]
tree 구조이므로 1부터 시작하는 dfs를 돌려주면서 각 노드의 양의 수만큼 더해주고, 늑대의 수만큼 빼주면
루트인 1에 몇마리의 양이 도착하는지 알 수 있습니다.
늑대+양이 음수가 될때는 0으로 초기화를 해주고, 자료형이 int 형을 넘어갈 수 있는점을 주의해야 합니다.

#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
vector<int> adj[123457];
int N,cnt[123457];
ll dfs(int p,int n){
    ll sum=cnt[n];
    for(auto nxt : adj[n]){
        if(nxt!=p) sum+=dfs(n,nxt);
    }
    return sum < 0 ? 0 : sum;   
}
int main(){
    scanf("%d",&N);
    for(int i=2;i<=N;i++){
        char c;
        int a,p;
        scanf(" %c%d%d",&c,&a,&p);
        if(c=='W') a=-a; 
        adj[i].push_back(p);
        adj[p].push_back(i);
        cnt[i]=a;
    }
    printf("%lld",dfs(-1,1));
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
N이 50이고 k가 1일 때,
k를 사용해서 모든 타일을 6개의 모양으로 바꿔보고 dfs를 하는 방식의 브루트포스로 풀게 되면
O(50*50*6*50*50) 으로 시간초과가 발생할 것으로 생각되지만
dfs를 이용해 실제 경로 탐색을 할 때 각 타일에서 갈 수 있는 다음 타일은 한개밖에 없기 때문에 많은 경로가
가지치기 될 것으로 기대되어 실제로 O(50*50) 만큼의 시간이 발생하지 않습니다.

그러므로 모든 타일을 바꿔는 브루트포스 방식으로 문제 해결이 가능합니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dy[4]={-1,0,1,0},dx[4]={0,-1,0,1};
int line[6][4]={{0,0,1,1},{0,1,1,0},{1,0,0,1},{1,1,0,0},{1,0,1,0},{0,1,0,1}};
int N,k,board[52][52],visit[52][52];
int match(int i){
    if(i<2) return i+2;
    return i-2;
}
int dfs(int y,int x){
    if(y==N-1&&x==N-1){
        if(board[y][x]==2||board[y][x]==5) return 1;
        return -1;
    }
    if(y==0&&x==0){
        if(board[y][x]%2==0) return -1;
    }
    visit[y][x]=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        int m = match(i);
        if(ny<0||nx<0||ny>=N||nx>=N||!line[board[y][x]][i]||!line[board[ny][nx]][m]||visit[ny][nx]) continue;
        int ret = dfs(ny,nx);
        if(ret==-1) return -1;
        return ret+1;
    }
    return -1;
}
int main(){
    scanf("%d%d",&N,&k);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&board[i][j]);
        }
    }
    int ans=9e8;
    if(k){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int t = board[i][j];
                for(int k=0;k<6;k++){
                    if(t!=k) {
                        board[i][j]=k;
                        memset(visit,0,sizeof(visit));
                        int ret = dfs(0,0);
                        if(ret!=-1) ans=min(ans,ret);
                    }
                }
                board[i][j]=t;
            }
        }       
    }else ans=dfs(0,0);
    printf("%d",ans == 9e8 ? -1 : ans);
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
무거운 구슬을 u, 가벼운 구슬을 v로 입력 받았을 때,
인접행렬을 이용해 adj[u][v]=1, adj[v][u]=2 와 같이 u->v 방향 edge는 1, v->u 방향 edge는 2로
표시해줍니다.

그 뒤 각 구슬에서 dfs를 1,2방향에 대해 돌려주면서 몇 개의 구슬을 방문할 수 있는지 체크해줍니다.
1 방향 edge 탐색으로 자신보다 가벼운 구슬의 개수를 찾을 수 있고,
2 방향 edge 탐색으로 자신보다 무거운 구슬의 개수를 찾을 수 있습니다.

이 두 값 중 N/2를 넘는 값이 있으면 정답에 추가해줍니다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,visit[100],adj[100][100],ans;
int dfs(int cur,int k){
    visit[cur]=1;
    int ret=1;
    for(int i=1;i<=N;i++){
        if(!visit[i]&&adj[cur][i]==k) ret+=dfs(i,k);
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u][v]=1;
        adj[v][u]=2;
    }
    for(int i=1;i<=N;i++){
        int v = dfs(i,1);
        memset(visit,0,sizeof(visit));
        if(v-1>N/2) {
            ans++;
        } else {
            v = dfs(i,2);
            if(v-1>N/2) ans++;
        }
        memset(visit,0,sizeof(visit));
    }
    printf("%d",ans);
}

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

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

[난이도] Silver1
[유형] DFS

[풀이]
dfs를 이용해 각 노드부터 시작해서 방문할 수 있는 총 노드의 개수를 구할 수 있습니다.
이 노드의 개수가 해킹할 수 있는 노드의 개수입니다.

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;
int N,M,visit[10001];
vector<int> adj[10001];
map<int,vector<int>> mp;
int dfs(int n){
    visit[n]=1;
    int ret=1;
    for(auto nxt : adj[n]){
        if(!visit[nxt]){
            ret+=dfs(nxt);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v;scanf("%d%d",&u,&v);adj[v].push_back(u);
    }
    for(int i=1;i<=N;i++){
        memset(visit,0,sizeof(visit));
        mp[dfs(i)].push_back(i);
    }
    auto [k,res] = *mp.rbegin();
    sort(res.begin(),res.end());
    for(auto a : res) printf("%d ",a);
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
두 로봇 중 한 로봇의 시작점에서 DFS를 시작하여 다른 로봇에 도착할 때까지
지나는 엣지들의 합 total과 엣지중의 최댓값 val을 갱신해줍니다.
다른 로봇에 도착했을 때까지 갱신된 total-val이 정답입니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,s,e,ans;
vector<pair<int,int>> adj[100001];
void sol(int n,int prev,int val,int total){
    if(n==e){
        ans=total-val;
        return;
    }
    for(auto [nxt,d] : adj[n]){
        if(nxt!=prev) {
            sol(nxt,n,max(val,d),total+d);
        }
    }
}
int main(){
    scanf("%d%d%d",&N,&s,&e);
    for(int i=0;i<N-1;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    sol(s,0,0,0);
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
N개의 점에서 모두 DFS를 해주며 dist[i][j] 배열에 i,j의 유사도를 저장해줍니다.
i와 j를 연결하는 경로는 한개씩밖에 없는 트리 구조의 그래프이기 때문에 재귀함수를 이용해
간단히 유사도를 구할 수 있습니다.
이때의 시간복잡도는 O(N*N) 입니다.

유사도를 모두 구해놨으므로 각 Q개의 쿼리에 대해 O(N)에 대응할 수 있으므로 이때의 시간복잡도는
O(N*Q) 입니다.

O(N*N)과 O(N*Q) 모두 O(5000*5000)으로 넉넉하지는 않지만 시간내에 해결이 가능합니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,Q,dist[5001][5001];
vector<pair<int,int>> adj[5001];
bool visit[5001];
void dfs(int s,int prev,int cur,int v){
    for(auto [nxt,d] : adj[cur]){
        if(nxt!=prev){
            int t = min(v,d);
            dist[s][nxt]=t;
            dfs(s,cur,nxt,t);
        }
    }
}
int main(){
    scanf("%d%d",&N,&Q);
    for(int i=0;i<N-1;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    for(int i=1;i<=N;i++){
        dfs(i,-1,i,2e9);
    }
    while(Q--){
        int k,v,cnt=0;
        scanf("%d%d",&k,&v);
        for(int i=1;i<=N;i++){
            if(dist[i][v] >= k) cnt++;
        }
        printf("%d\n",cnt);
    }
}

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

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

[난이도] Gold4
[유형] DFS

[풀이]
인접리스트를 만들 때 vector 대신 set을 이용하면
방문하지 않은 자식 노드들 중에 입력으로 주어진 다음에 방문해야 하는 노드가
있는지를 쉽게 파악할 수 있습니다.
노드가 존재한다면 그 노드를 set에서 제거해주고 다음 노드로 방문해주면 됩니다.

#include <cstdio>
#include <set>
using namespace std;
int idx,N,a[100001];
set<int> adj[100001];
int dfs(int prev,int n){
    idx++;
    if(adj[n].find(prev) != adj[n].end()) adj[n].erase(prev);
    while(!adj[n].empty()){
        int v = a[idx];
        if(adj[n].find(v) == adj[n].end()) return 0;
        adj[n].erase(v);
        bool ret = dfs(n,v);
        if(!ret) return 0;
    }
    return 1;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].insert(v);
        adj[v].insert(u);
    }
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    printf("%d",dfs(0,1));
}

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