3212위상정렬.cpp

#include <stdio.h>
#include <queue>
int arr[201][201],chk[201];
std::queue<int> q;

int main(void) {
    int i, j, v, n, cnt=0;
    scanf("%d %d",&v,&n);
    for(i=0;i<n;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        arr[a][b]=1,arr[b][a]=-1;
    }

    while(cnt!=v){
        for(i=1;i<=v;i++) {
            if(!chk[i]) {
                bool flag=0;
                for(j=1;j<=v;j++)
                    if(arr[i][j]==-1) {
                        flag=1;
                        break;
                    }
                if(!flag) break;
            }
        }
        if(i>v) {
            printf("-1");
            return 0;
        }
        q.push(i);
        for(int a=1;a<=v;a++) arr[a][i]=arr[i][a]=0;
        chk[i]=1;
        cnt++;
    }

    while(!q.empty()) {
        printf("%d\n",q.front()); q.pop();
    }
}

3216최단경로출력.cpp

#include <stdio.h>
#include <queue>
#define MAX 30
#define INF 31415926

using namespace std;
queue<int> Q;

int dist[27],map[27][27], prt[27];
int w,tmp;

void print(int k){
    if(prt[k]!=-1) print(prt[k]);
    printf("%c\n", k+'A');
}
int main(){
    int N, M; //N: node, M:edge
    char from, to, start, end;
    scanf("%d %d", &N, &M);
  
    for(int i=0;i<N; i++) prt[i]=-1;  //prt 초기화
  
    for(int i=0;i<M;i++){
        scanf(" %c %c %d", &from, &to, &w);
        map[from-'A'][to-'A']=map[to-'A'][from-'A']=w;
    }
    
    scanf(" %c %c", &from, &to);
    start=from-'A';
    end=to-'A';
    
    for(int i=0;i<N;i++) dist[i]=INF;
    dist[start]=0;
  
    //BFS
    Q.push(start);
    while(!Q.empty()){
        tmp=Q.front();
        Q.pop();
        for(int i=0; i<N; i++){
            if(map[tmp][i]&&dist[i]>dist[tmp]+map[tmp][i]){
                dist[i]=dist[tmp]+map[tmp][i];
                prt[i]=tmp;
                Q.push(i);
            }
        }
    }
    if(dist[end]==INF){
        printf("-1");
    }
    else {
        printf("%d\n",dist[end]);
        print(end);
    }
    return 0;
}

3600체스말이동.cpp

#include <stdio.h>
#include <queue>

int arr[1001][1001], sx, sy, fx, fy, tx, ty, nx, ny, n;
int dx[8]={2,-2,2,-2,1,-1,1,-1};
int dy[8]={1,1,-1,-1,2,2,-2,-2};
using namespace std;
queue<int> Qx, Qy;

int main(){
    scanf("%d", &n);
    scanf("%d %d", &sx, &sy);
    scanf("%d %d", &fx, &fy);
    arr[sx][sy]=1;
    Qx.push(sx); Qy.push(sy);
    while(!Qx.empty() && !Qy.empty()){
        nx=Qx.front(); Qx.pop();
        ny=Qy.front(); Qy.pop();
        if(nx==fx && ny==fy) break;
        for(int i=0; i<8; i++) {
            tx=nx+dx[i]; ty=ny+dy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=n && arr[tx][ty]==0) {
                Qx.push(tx); Qy.push(ty);
                arr[tx][ty]=arr[nx][ny]+1;
            }
        }
    }
    printf("%d", arr[fx][fy]-1);
}

4054백신.cpp

#include <stdio.h>
#include <queue>
using namespace std;

int map[111][111], n, m;
queue<int> qr, qc;

int count(int r, int c) {
    return map[r-1][c] + map[r+1][c] + map[r][c-1] + map[r][c+1];
}

main() {
    int i, j;
    int tr, tc, flag = 0;
    int res = 0;

    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++) {
            scanf("%d", &map[i][j]);
            map[i][j] = !map[i][j];

        }

    while(1) {
        flag = 0;
        res++;
        for(i = 2; i < n; i++)
            for(j = 2; j < m; j++)
                if ( map[i][j] == 0 && count(i, j) >= 2 ) {
                    flag = 1;
                    qr.push(i); qc.push(j);
                }
        if ( flag == 1 ) {
            while( !qr.empty() ) {
                tr = qr.front(); tc = qc.front();
                map[tr][tc] = 1;
                qr.pop(); qc.pop();
            }
        }
        else {
            printf("%d", res - 1);
            return 0;
        }
    }
}

4463치즈.cpp

include <stdio.h>

int cheese[110][110];
int chk[110][110];
int cnt[110];
int r, c, num;

void air(int i,int j){
    if(i>=1 && i<=r && j>=1 && j<=c){
        if(!chk[i-1][j] && !cheese[i-1][j])  { chk[i-1][j]=-1; air(i-1,j);  }
        if(!chk[i][j-1] && !cheese[i][j-1])  { chk[i][j-1]=-1; air(i,j-1);  }
        if(!chk[i][j+1] && !cheese[i][j+1])  { chk[i][j+1]=-1; air(i,j+1);  }
        if(!chk[i+1][j] && !cheese[i+1][j])  { chk[i+1][j]=-1; air(i+1,j);  }
    }
}

void melt(){
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            if(cheese[i][j]==1)
                if(chk[i-1][j]==-1||chk[i+1][j]==-1||chk[i][j-1]==-1||chk[i][j+1]==-1){
                    cheese[i][j]=0;
                    num--;
                }
}

int main(void){
    int cnt[110], t=0;
    scanf("%d %d",&r,&c);
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++){
            scanf("%d",&cheese[i][j]);
            num+=cheese[i][j];
        }

    while(1){
        cnt[++t]=num;
        if(num==0) break;
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                chk[i][j]=0;
        chk[1][1]=-1;
        air(1,1);
        melt();
    }
    printf("%d\n%d",t-1,cnt[t-1]);
}

4697안전영역.cpp

#include <stdio.h>
int arr[102][102];
int temp[102][102];
int n;

void dfs(int i,int j) {
    temp[i][j]=0;
    if(temp[i+1][j]) dfs(i+1,j);
    if(temp[i-1][j]) dfs(i-1,j);
    if(temp[i][j+1]) dfs(i,j+1);
    if(temp[i][j-1]) dfs(i,j-1);
    return;
}

int main(void) {
    int sum=0;
    int max=0;
    int smax=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) {
            scanf("%d", &arr[i][j]);
            if(arr[i][j]>max) max=arr[i][j];
        }

    for(int k=0;k<=max;k++) {
        sum=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) {
                if(arr[i][j]<=k) temp[i][j]=0;
                else temp[i][j]=arr[i][j]-k;
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) {
                if(temp[i][j]) {
                    dfs(i,j);
                    sum++;
                }
            }
        if(smax<sum) smax=sum;
    }
    printf("%d",smax);
}

4714키순서.cpp

#include <stdio.h>
int arr[502][502];
int n;
void floyd() {
    int i, j, k;
    for (k = 0; k < n; ++k) {
        for (i = 1; i <=n; ++i) {
            for (j = 1; j <=n; ++j) {
                arr[i][j] = arr[i][j] | (arr[i][k + 1] && arr[k + 1][j]);
            }
        }
    }
}

int main(void) {
    int m;
    int cnt=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        arr[a][b]=1;
    }

    floyd();

    for(int i=1;i<=n;i++) {
        int in=0,out=0;
        for(int j=1;j<=n;j++)  if(arr[j][i]==1) in++;
        for(int j=1;j<=n;j++)  if(arr[i][j]==1) out++;
        if((in+out)==n-1) cnt++;
    }
    printf("%d",cnt);
}

단지번호붙이기.cpp

#include <stdio.h>
#include <algorithm>
int in[27][27], vis[27][27], dangi=0, h_num[900], cnt;
void dfs(int x, int y) {
    vis[x][y]=1; cnt++;
    if (in[x][y-1] && !vis[x][y-1]) dfs(x,y-1);
    if (in[x][y+1] && !vis[x][y+1]) dfs(x,y+1);
    if (in[x-1][y] && !vis[x-1][y]) dfs(x-1,y);
    if (in[x+1][y] && !vis[x+1][y]) dfs(x+1,y);
}

int main () {
    int n;
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            scanf("%1d", &in[i][j]);
        }
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (in[i][j] && !vis[i][j]) {
                cnt=0;
                dfs(i,j);
                h_num[dangi]=cnt; dangi++;
            }
        }
    }
    std::sort(h_num, h_num+dangi);
    printf("%d",dangi);
    for (int i=0; i<dangi; i++) printf("\n%d", h_num[i]);
}