프로그래밍

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

[난이도] Gold2
[유형] DFS

[풀이]
지도 밖으로 나가는 입력이 주어지지 않으므로
사이클을 찾아서 총 사이클의 개수를 세주면 됩니다.
dfs를 이용해서 현재 방문중이면 visit[y][x]=1로 체크하고
만약 다음 노드가 1로 체크되어 있다면 사이클을 찾은 것이므로 정답에 1을 더해줍니다.
또한 방문을 마칠때는 visit[y][x]=2로 체크해주어야 합니다.
왜냐하면 이미 발견되어 카운팅된 사이클로 접근하는 경우에는 이미 그 사이클에 쉼터가
존재하므로 카운팅을 해줄 필요가 없기 때문입니다. 이를 구분하기 위해 이미 쉼터에 갈 수 있는
노드들은 2로 체크해주었습니다.

#include <cstdio>
int N,M,ans;
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1},map[1000][1000];
int visit[1000][1000];
void dfs(int y,int x){
    visit[y][x]=1;
    int ny=y+dy[map[y][x]],nx=x+dx[map[y][x]];

    if(visit[ny][nx]==1) ans++;
    if(visit[ny][nx]==0) dfs(ny,nx);
    visit[y][x]=2;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char c;
            scanf(" %c",&c);
            if(c=='U') map[i][j]=1;
            else if(c=='R') map[i][j]=2;
            else if(c=='L') map[i][j]=3;
        }
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            if(visit[i][j]==0) dfs(i,j);
    printf("%d",ans);
}

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

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

[난이도] level3
[유형] DFS

[풀이]
가장자리에는 얼음이 없다는 것이 보장되기 때문에
0,0에서부터 0(얼음) 인 점을 탐색하면서 4방향을 검사해서 얼음이 있으면 얼음의 좌표에 외부 공기에 접한 횟수를 카운팅 해줍니다.
그 뒤 2이상 카운팅된 얼음을 지워주는 것을 모든 얼음이 사라질때까지 반복하면 됩니다.

#include <cstdio>
#include <cstring>
int N,M,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int map[100][100],cnt[100][100],visit[100][100],ans;
void dfs(int y,int x){
    visit[y][x]=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||visit[ny][nx]) continue;
        if(map[ny][nx]){
            cnt[ny][nx]++;
        }else{
            dfs(ny,nx);
        }
    }
}
bool exist(){
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) if(map[i][j]) return true;
    return false;
}
int main(){
    bool ok=0;
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            scanf("%d",&map[i][j]);
            if(map[i][j]) ok=1;
        }
    while(ok){
        ans++;
        dfs(0,0);
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++) if(cnt[i][j]>=2) map[i][j]=0;
        ok=exist();
        memset(visit,0,sizeof(visit));
        memset(cnt,0,sizeof(cnt));
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/동계_테스트_시점_예측.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=409&sw_prbl_sbms_sn=16804

[난이도] level2
[유형] DFS

[풀이]
전형적인 DFS 문제입니다.
입력을 받을 때 %1d 와 같이 써주면 문제의 입력과 같이 붙어있는 입력에 대해서도 한자리씩 받을 수 있습니다.
블록의 크기를 저장할때는 multiset을 이용하였습니다. 따로 정렬을 해주지 않아도 set은 트리구조이기 때문에
정렬된 상태가 유지되며 저장되기 때문입니다.

#include <cstdio>
#include <set>
using namespace std;
int N,map[25][25],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
bool visit[25][25];
int dfs(int y,int x){
    visit[y][x]=1;
    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>=N||!map[ny][nx]||visit[ny][nx]) continue;
        ret+=dfs(ny,nx);
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) scanf("%1d",&map[i][j]);
    multiset<int> ans;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(map[i][j] && !visit[i][j]) ans.insert(dfs(i,j));
    printf("%d\n",ans.size());
    for(auto v : ans) printf("%d\n",v);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/장애물_인식_프로그램.cpp

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

[난이도] level3
[유형] DFS

[풀이]
트리의 리프노드에서부터 자신을 0으로 만들고, 나머지를 부모 노드로 전달했을 때,
최종으로 값을 전달받는 루트노드가 0이 된다면 조건을 만족하는 것입니다.
DFS를 통해 리프부터 값을 누적해갈 수 있으며 각 노드의 return 이전에 연산 횟수를 더해주면 됩니다.

import java.util.*
import kotlin.math.abs
const val mxN = 300000
var adj = Array(mxN){ mutableListOf<Int>()}
var b = LongArray(mxN)
var ans=0L
fun dfs(par:Int,n:Int):Long{
    var ret = b[n]
    for(i in 0..adj[n].size-1){
        if(adj[n][i]!=par) ret+=dfs(n,adj[n][i])
    }
    ans+=abs(ret)
    return ret
}
class Solution {
    fun solution(a: IntArray, edges: Array<IntArray>): Long {
        for(i in a.indices) b[i]=a[i].toLong()
        for((u,v) in edges){
            adj[u].add(v)
            adj[v].add(u)
        }
        if(dfs(-1,0)!=0L) ans=-1
        return ans
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/모두_0으로_만들기.cpp

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

[난이도] Silver2
[유형] DFS

[풀이]
간단한 DFS 문제

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
val mxN = 250000
var Primes = Array(mxN+1){true}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    for(i in 2..mxN/2){
        if(!Primes[i]) continue
        for(j in i*2..mxN step i) Primes[j] = false
    }
    while(true){
        var k=readLine().toInt()
        if(k==0) break
        var ans = 0
        for(i in k+1..2*k) if(Primes[i]) ans++
        println(ans)
    }
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
친구관계를 이용해 그래프를 만들어 준 뒤, 0~N-1의 모든 점에서 dfs를 돌면서 깊이가 5가 되는 경우가 있으면 1을 출력해야 한다. 일반 dfs와 다르게 dfs 함수를 return하기 전에 visit[n]=0 으로 처리를 해줘야 놓치는 케이스 없이 답을 찾을 수 있다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,visit[2001];
vector<int> adj[2001];
bool ok=0;
void dfs(int n,int k){
    if(ok) return;
    visit[n]=1;
    if(k==5) ok=1;
    for(auto nxt : adj[n]){
        if(!visit[nxt]) dfs(nxt,k+1);
    }
    visit[n]=0;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=0;i<N;i++){
        memset(visit,0,sizeof(visit));
        dfs(i,1);
        if(ok) break;
    }
    printf("%d",ok);
}

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

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

[난이도] Gold5
[유형] DFS

[풀이]
DFS

#include <cstdio>
#include <cstring>
int N,M,a[102][102],b[102][102],tmp[102][102];
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
void dfs(int y,int x){
    b[y][x]=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]||b[ny][nx]) continue;
        dfs(ny,nx);
    }
}
int dfs2(int y,int x){
    b[y][x]=1;
    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(a[ny][nx] && !b[ny][nx]) ret+=dfs2(ny,nx);
    }
    return ret;
}
int cnt(){
    memset(b,0,sizeof(b));
    int ret=0;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            if(a[i][j] && !b[i][j]) ret+=dfs2(i,j);
    return ret;
}
void rmv(){
    memset(b,0,sizeof(b));
    memset(tmp,0,sizeof(tmp));
    dfs(0,0);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            bool ok=0;
            for(int k=0;k<4;k++){
                int ny=i+dy[k],nx=j+dx[k];
                if(b[ny][nx]){
                    ok=1;
                    break;
                }
            }
            tmp[i][j]=ok;
        }
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            if(tmp[i][j]) a[i][j]=0;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            scanf("%d",&a[i][j]);
    int prev=cnt();
    for(int t=0;;t++){
        int cur=cnt();
        if(cur==0) {
            printf("%d\n%d",t,prev);
            return 0;
        }
        rmv();
        prev=cur;
    }
}

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

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

[난이도] Gold2
[유형] DFS

[풀이]
N,M의 최댓값이 1000이므로 각 점에서 DFS or BFS로 답을 구하면 시간 초과가 난다.
DFS를 전체 맵에 대해 한번씩 돌리면서 빈 칸이 어떤 그룹에 속하는지, 그 그룹의 총 원소의 수는 몇개인지를 기록해놓는다.
그 뒤 맵을 다시 순회하면서 벽이 있는 칸의 4방향을 확인하면서 그룹의 갯수를 더해주면 시간내에 답을 구할 수 있다.

#include <cstdio>
#include <set>
using namespace std;
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int N,M,a[1000][1000],grp[1000][1000],cnt[1000001];
bool visit[1000][1000];
int dfs(int y,int x,int k){
    visit[y][x]=1;
    grp[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||a[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("%1d",&a[i][j]);
        
    int g=1;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!a[i][j] && !visit[i][j]){
                cnt[g]=dfs(i,j,g);
                g++;
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!a[i][j]) continue;
            int v=0;
            set<int> p;
            for(int k=0;k<4;k++){
                int ny=i+dy[k],nx=j+dx[k];
                if(ny<0||nx<0||ny>=N||nx>=M||a[ny][nx]) continue;  
                p.insert(grp[ny][nx]);
            }
            for(auto q : p) v+=cnt[q];
            a[i][j]=v+1;
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            printf("%d",a[i][j]%10);
        }
        puts("");
    }
}

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