프로그래밍

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

[난이도] Gold3
[유형] DFS

[풀이]
정방향,반대방향 인접 리스트를 이용해서 dfs를 두번하면 최대,최저 등수를 구할 수 있다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
vector<int> adj[2][100001];
bool visit[100001];
int N,M,X,k;
int dfs(int n){
    visit[n]=1;
    int ret=1;
    for(auto v : adj[k][n]){
        if(!visit[v]) ret+=dfs(v);
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&X);
    for(int i=0;i<M;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[0][u].push_back(v);
        adj[1][v].push_back(u);
    }
    int U,V;
    U=N-dfs(X)+1;
    k=1;
    V=dfs(X);
    printf("%d %d",V,U);
}

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

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

[난이도] Gold4
[유형] DFS

[풀이]
DFS로 구한 각 컴포넌트에 id를 기록하고 몇개의 점을 포함하는지를 배열에 기록해놓는다.
그 뒤 0인 모든 점을 확인하면서 4방향에 있는 id들의 개수를 더해준 값을 구해준다.

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
int N,M,map[1000][1000],cnt[1000001];
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
bool visit[1000][1000];
int dfs(int y,int x,int k){
    visit[y][x]=1;
    map[y][x]=k;
    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||!map[ny][nx]||visit[ny][nx]) continue;
        ret+=dfs(ny,nx,k);
    }
    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",&map[i][j]);

    int id=1;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            if(!visit[i][j] && map[i][j]) {
                cnt[id]=dfs(i,j,id);
                id++;
            }
    int ans=0;
    for(int y=0;y<N;y++){
        for(int x=0;x<M;x++){
            if(map[y][x]) continue;
            int c=0;
            set<int> s;
            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||!map[ny][nx]) continue;
                s.insert(map[ny][nx]);
            }
            for(auto k : s) c+=cnt[k];
            ans=max(c,ans);
        }
    }
    printf("%d",ans+1);
}

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

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

[난이도] Gold4
[유형] DFS

[풀이]
인접리스트를 이용해 칭찬 그래프를 만들고 칭찬을 받은 사람부터 dfs를 시작해
방문하는 모든 부하들에게 칭찬을 더해주면 된다.
이 때, 칭찬의 총 갯수 M마다 dfs를 돌면 시간초과가 나므로 사람 i에 대한 칭찬을 미리 모두 더한 뒤
dfs를 돌려야 한다.

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int N,M,ans[100001],s[100001];
vector<int> adj[100001];
void dfs(int n,int k){
    ans[n]+=k;
    for(auto nxt : adj[n]) dfs(nxt,k);
}

int main(){
    scanf("%d%d",&N,&M);
    
    for(int i=1;i<=N;i++){
        int u;
        scanf("%d",&u);
        if(u!=-1) adj[u].push_back(i);
    }
    while(M--){
        int a,w;
        scanf("%d%d",&a,&w);
        s[a]+=w;
    }
    for(int i=2;i<=N;i++){
        if(s[i]>0) dfs(i,s[i]);
    }
    for(int i=1;i<=N;i++) printf("%d ",ans[i]);
}

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

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

[난이도] Gold4
[유형] DFS

[풀이]
DFS를 이용해서 cycle이 없는 연결요소를 찾아야 한다.
cycle을 찾는 방법은 다음과 같다.
1. DFS로 방문하는 순서를 dfs(int n,int cnt)와 같이 cnt를 한개씩 증가시키면 visit 배열에
기록해준다.
2. 인접한 노드가 cnt보다 2이상 큰수라면 이미 방문한 노드이므로 cycle이 있는것이다. (1이면 부모노드이므로 skip)
=> cycle이 없는 연결요소들의 개수가 정답이다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,visit[501],tc;
vector<int> adj[501];
bool ok =1;
void dfs(int n,int cnt){
    visit[n]=cnt;
    for(auto nxt : adj[n]){
        if(!visit[nxt]) dfs(nxt,cnt+1);
        else if(visit[n]-visit[nxt]>1) ok=0;
    }
}
int main(){
    while(1){
        scanf("%d%d",&N,&M);
        memset(visit,0,sizeof(visit));
        for(int i=0;i<=N;i++) adj[i].clear();
        if(N==0) break;
        while(M--){
            int u,v;
            scanf("%d%d",&u,&v);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int ans = 0;
        for(int i=1;i<=N;i++){
            if(!visit[i]){
                ok=1;
                dfs(i,0);
                ans+=ok;
            }
        }
        printf("Case %d: ",++tc);
        if(ans==0) puts("No trees.");
        else if(ans==1) puts("There is one tree.");
        else printf("A forest of %d trees.\n",ans);
    }
}

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

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

[난이도] Gold4
[유형] DFS

[풀이]
무방향 그래프의 cycle을 찾는 문제이다.
next node가 이미 방문한 node이면서 부모가 아니면 cycle이다.
부모를 체크하기 위해 visit 배열에 방문한 순서를 저장해놓고
현재 노드의 visit, 다음 노드의 visit 차가 1이면 부모 노드이므로 무시한다.

#include <cstdio>
int N,M,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
char map[50][50];
int visit[50][50];
bool dfs(int y,int x,int k){
    visit[y][x]=k;
    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 || map[ny][nx]!=map[y][x]) continue; 
        if(visit[ny][nx]){
            if(k-visit[ny][nx]>1) return 1;
        } else if(dfs(ny,nx,k+1)) return 1;
    }
    return 0;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf(" %c",&map[i][j]);  
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!visit[i][j]){
                if(dfs(i,j,0)){
                    puts("Yes");
                    return 0;
                }
            }
        }
    }
    puts("No");
}

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

www.acmicpc.net/problem/2458

[난이도] Gold4

[유형] DFS

[풀이]

in,out 배열을 만들고 각 점에서 DFS를 해서 방문할 수 있는 점의 개수를
out에, DFS중 어떤 점을 방문할때 그 점의 in값을 1씩 증가 시킨다.
in[i]+out[i]==N인 점이 정답인 점들이다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,in[501],out[501],ans;
vector<int> adj[501];
bool visit[501];
int dfs(int n){
    visit[n] = 1;
    int ret = 1;
    for(int nxt : adj[n]){
        if(!visit[nxt]){
            in[nxt]++;
            ret+=dfs(nxt);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
    }

    for(int i=1;i<=N;i++){
        memset(visit,0,sizeof(visit));
        out[i] = dfs(i);
    }
    for(int i=1;i<=N;i++) if(in[i]+out[i]==N) ans++;
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2458.cpp

www.acmicpc.net/problem/2234

[난이도] Gold4

[유형] DFS

[풀이]

1. DFS를 돌면서 각 방이 어떤 그룹에 속하는지 나누면서 각 그룹에 몇개의
   방이 있는지를 체크한다.
2. 모든 방을 순회하면서 동,서,남,북 방향을 체크해 다른 그룹이 있으면
   현재 방의 개수 + 현재 체크중인 인접한 방의 개수를 더해 답을
   갱신해준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,map[50][50],g,grp[2501],mxR,mxS;
int visit[50][50];
int dy[4] = {0,-1,0,1};
int dx[4] = {-1,0,1,0};
int dfs(int y,int x){
    visit[y][x] = g;
    int ret = 1;
    for(int i=0;i<4;i++){
        if((map[y][x] & (1<<i))==0){
            int ny = y+dy[i], nx = x+dx[i];
            if(ny < 0 || nx < 0 || ny >= n || nx >= m || visit[ny][nx]) continue;
            ret+=dfs(ny,nx);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&map[i][j]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visit[i][j]){
                g++;
                grp[g] = dfs(i,j);
                mxR = max(mxR,grp[g]);
            }
        }
    }
    for(int y=0;y<n;y++){
        for(int x=0;x<m;x++){
            for(int i=0;i<4;i++){
                if((map[y][x] & (1<<i))>0){
                    int ny = y+dy[i], nx = x+dx[i];
                    if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                    if(visit[ny][nx] != visit[y][x]) mxS = max(mxS,grp[visit[ny][nx]]+grp[visit[y][x]]);
                }
            }
        }
    }
    printf("%d\n%d\n%d",g,mxR,mxS);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2234.cpp

www.acmicpc.net/problem/1976

[난이도] Gold4

[유형] DFS

[풀이]

여행해야하는 임의의 한 점에서 DFS를 돌았을 때 여행 경로에 있는 모든 점을 Visit한 경우에만 YES이다.

#include <cstdio>
using namespace std;
int N,M,d[1001];
bool adj[201][201],visit[201];
void dfs(int n){
    visit[n] = 1;
    for(int i=1;i<=N;i++)
        if(adj[n][i] && !visit[i]) dfs(i);
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&adj[i][j]);
    for(int i=0;i<M;i++) scanf("%d",&d[i]);
    dfs(d[0]);
    for(int i=0;i<M;i++) {
        if(!visit[d[i]]) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1976.cpp