2842번: POŠTAR

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

방문한 칸의 최소 높이가 x일 때 메일을 모두 보낼수 있는 방문한 칸의 최대 고도의 최솟값을 f(x)라 하자.
f(x)는 단조증가 함수가 된다. 고로 l=x, r=f(x)로 잡고 inchworm 알고리즘을 적용할 수 있다.
[l,r] 구간의 고도에 해당하는 칸만을 방문하여 모든 메일을 배달할 수 있다면 l++, 그렇지 않다면 r++을 해주며 모든 x에 대한 f(x) 값을 구한다. 답은 이러한 f(x) - x 들 중 최솟값이 된다.

시간복잡도는 $O(n^4)$

#include<cstdio>
#include<algorithm>
using namespace std;
const int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int n, a[50][50], vis[50][50], sx, sy, res = 1e9, v[2500], l, r;
char s[50][51];
void f(int x, int y) {
    if (x < 0 || y < 0 || x == n || y == n || vis[x][y] || a[x][y]<v[l] || a[x][y]>v[r]) return;
    vis[x][y] = 1;
    for (int i = 0; i < 8; i++) f(x + dx[i], y + dy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
        for (int j = 0; j < n; j++) if (s[i][j] == 'P') sx = i, sy = j;
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", a[i] + j), v[i*n + j] = a[i][j];
    sort(v, v + n*n);
    while (r < n*n) {
        f(sx, sy);
        int flag = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!vis[i][j] && s[i][j] == 'K') flag = 1;
                vis[i][j] = 0;
            }
        }
        flag ? r++ : res = min(res, v[r] - v[l++]);
    }
    printf("%d", res);
    return 0;
}

13565번: Percolation

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

$O(mn)$

flood fill을 한다.

#include<cstdio>
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int m, n, r;
char c[1000][1001];
void f(int x, int y) {
    r |= x == m;
    if (x < 0 || y < 0 || x == m || y == n || c[x][y] == '1') return;
    c[x][y] = '1';
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) scanf("%s", c[i]);
    for (int i = 0; i < n; i++) f(0, i);
    puts(r ? "YES" : "NO");
    return 0;
}

1941번: 소문난 칠공주

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


$O(1)$

25칸 중 7개의 칸을 선택해서 모두 인접해 있고 S가 4개 이상인 경우를 카운트

#include<cstdio>
#include<algorithm>
using namespace std;
char a[5][6];
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int r, vis[5][5], p[25], s, tot;
void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= 5 || y >= 5 || vis[x][y] || !p[x * 5 + y]) return;
    vis[x][y] = 1;
    s += a[x][y] == 'S';
    tot++;
    for (int i = 0; i < 4; i++) dfs(x + fx[i], y + fy[i]);
}
int main() {
    for (int i = 0; i < 5; i++) scanf("%s", a[i]);
    for (int i = 18; i < 25; i++) p[i] = 1;
    do {
        fill(vis[0], vis[5], 0);
        int i = s = tot = 0;
        for (; !p[i]; i++);
        dfs(i / 5, i % 5);
        r += tot == 7 && s > 3;
    } while (next_permutation(p, p + 25));
    printf("%d", r);
    return 0;
}

2276번: 물 채우기

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


$O(nm\lg (nm))$

수면이 점점 올라가 잠긴다고 생각하자.
잠기는 구역이 새로 생길때 (수면의 높이)-(잠기는 구역 높이) 합을 누적하면 답을 구할 수 있다.
답을 빠르기 구하기 위해 우선순위 큐 pq를 사용하자.
pq는 (잠기기 시작하는 지점 위치, 높이 h) 정보를 가지고 있고 작은 높이의 원소가 top이 된다.
top의 지점에서 시작해서 아직까지 잠기지 않은 지점들 중 h보다 작거나 같은 지점들을  모두 체크해주고 h-(잠기는 구역 높이)를 누적한다.
새로 체크된 주변 지점들 중 체크되지 않은 지점들을 pq에 넣고 이를 반복한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 1,0,-1,0 }, fy[] = { 0,1,0,-1 };
int n, m, ck[300][300], h[300][300], r;
struct st {
    int x, y;
    bool operator<(st i) const {
        return h[x][y] > h[i.x][i.y];
    }
};
priority_queue<st> pq;
void dfs(int x, int y, int z) {
    for (int i = 0; i < 4; i++) {
        int tx = x + fx[i], ty = y + fy[i];
        if (tx >= 0 && ty >= 0 && tx < m&&ty < n&&!ck[tx][ty]) {
            ck[tx][ty] = 1;
            if (h[tx][ty] > z) pq.push({ tx,ty });
            else {
                r += z - h[tx][ty];
                dfs(tx, ty, z);
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", h[i] + j);
            if (i == 0 || j == 0 || i == m - 1 || j == n - 1) pq.push({ i,j }), ck[i][j] = 1;
        }
    }
    while (!pq.empty()) {
        st t = pq.top();
        pq.pop();
        dfs(t.x, t.y, h[t.x][t.y]);
    }
    printf("%d", r);
    return 0;
}

4963번: 섬의 개수

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


$O(thw)$

flood fill 문제

#include<cstdio>
const int fx[] = { 0,0,1,-1,1,1,-1,-1 }, fy[] = { 1,-1,0,0,1,-1,1,-1 };
int t, h, w, c[50][50];
void f(int x, int y) {
    if (x < 0 || y < 0 || x >= h || y >= w || !c[x][y]) return;
    c[x][y] = 0;
    for (int i = 0; i < 8; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    while (scanf("%d %d", &w, &h) && h) {
        int r = 0;
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) scanf("%d", &c[i][j]);
        for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) if (c[i][j]) f(i, j), r++;
        printf("%d\n", r);
    }
    return 0;
}

11724번: 연결 요소의 개수

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


$O(n^2)$

#include<cstdio>
int n, m, ck[1001], r, adj[1001][1001];
void dfs(int h) {
    ck[h] = 1;
    for (int i = 1; i <= n; i++) if (adj[h][i] && !ck[i]) dfs(i);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d%d", &x, &y);
        adj[x][y] = adj[y][x] = 1;
    }
    for (int i = 1; i <= n; i++) if (!ck[i]) dfs(i), r++;
    printf("%d", r);
    return 0;
}

2146번: 다리 만들기

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


$O(n^2)$

섬마다 다르게 표시해놓고 섬의 각 지점을 큐에 넣고 BFS를 돌려 다른 섬간 최단 거리를 구한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int n, b[100][100], d[100][100], c, r = 1e9;
queue<pair<int, int> > q;
void f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= n || !d[x][y]) return;
    d[x][y] = 0;
    b[x][y] = c;
    q.push({ x,y });
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) scanf("%d", d[i] + j);
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) if (d[i][j]) ++c, f(i, j);
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + fx[i], ty = y + fy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= n) continue;
            if (b[tx][ty]) {
                if (b[tx][ty] ^ b[x][y] && r>d[tx][ty] + d[x][y]) r = d[tx][ty] + d[x][y];
                continue;
            }
            b[tx][ty] = b[x][y];
            d[tx][ty] = d[x][y] + 1;
            q.push({ tx,ty });
        }
    }
    printf("%d", r);
    return 0;
}

12004번: Closing the Farm (Silver)

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


$O(n(n+m))$

문제 그대로 구현.
매번 dfs 탐색을 해서 해당 곳간으로 부터 갈 수 있는 곳의 개수와 열린 곳간의 개수가 같은지 보고 해당 곳간을 닫는다.

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int n, m, ck[3001], cls[3001];
vector<int> adj[3001];
int f(int h) {
        if (cls[h] || ck[h]) return 0;
        ck[h] = 1;
        int s = 1;
        for (auto it : adj[h]) s += f(it);
        return s;
}
int main() {
        scanf("%d%d", &n, &m);
        for (int i = 0, x, y; i < m; i++) {
                scanf("%d%d", &x, &y);
                adj[x].push_back(y);
                adj[y].push_back(x);
        }
        for (int i = n, x; i; i--) {
                memset(ck, 0, sizeof(ck));
                scanf("%d", &x);
                puts(f(x) == i ? "YES" : "NO");
                cls[x] = 1;
        }
        return 0;
}

11964번: Fruit Feast

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


$O(t)$

dfs를 이용해 flood fill을 한다.

#include<cstdio>
int t, a, b, ck[2][5000001], r;
void f(int x, int y) {
    if (x>t || x>t || ck[y][x]) return;
    ck[y][x]++;
    if (x > r) r = x;
    if (!y) f(x / 2, 1);
    f(x + a, y);
    f(x + b, y);
}
int main() {
    scanf("%d%d%d", &t, &a, &b);
    f(0, 0);
    printf("%d", r);
    return 0;
}

2583번: 영역 구하기

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


$O(nm+k)$

#include<cstdio>
#include<algorithm>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int a[100][100], m, n, c, r[10000], rcnt;
void f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m || a[x][y]) return;
    a[x][y] = 1;
    r[rcnt]++;
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d %d %d", &m, &n, &c);
    for (int i = 0, x, y, z, w; i < c; i++) {
        scanf("%d %d %d %d", &x, &y, &z, &w);
        for (int j = x; j < z; j++) for (int k = y; k < w; k++) a[j][k] = 1;
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (!a[i][j]) f(i, j), rcnt++;
    std::sort(r, r + rcnt);
    printf("%d\n", rcnt);
    for (int i = 0; i < rcnt; i++) printf("%d ", r[i]);
    return 0;
}

2665번: 미로만들기

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


$O(n^2)$

#include<cstdio>
#include<string.h>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int n, ck[50][50], t;
char c[50][51];
void f(int x, int y) {
    if (x<0 || y<0 || x >= n || y >= n || ck[x][y])return;
    ck[x][y] = 1;
    if (c[x][y] == '0') { c[x][y]++; return; }
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%s", c[i]);
    for (; !ck[n - 1][n - 1]; t++) memset(ck, 0, sizeof(ck)), f(0, 0);
    printf("%d", t - 1);
    return 0;
}

2636번: 치즈

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


$O(n^3)$

#include<cstdio>
#include<string.h>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int n, m, c[102][102], ck[102][102], s, t, r;
void f(int x, int y) {
    if (x<0 || y<0 || x>n + 1 || y>m + 1 || ck[x][y])return;
    ck[x][y] = 1;
    if (c[x][y]) { c[x][y] = 0; s--; r++; return; }
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) scanf("%d", c[i] + j), s += c[i][j];
    for (; s; t++) memset(ck, 0, sizeof(ck)), r = 0, f(0, 0);
    printf("%d\n%d", t, r);
    return 0;
}

$O(n^2)$

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 100, fx[] = { 1,-1,0,0 }, fy[] = { 0,0,1,-1 };
int n, m, c[MXN + 2][MXN + 2], ck[MXN + 2][MXN + 2], t, r;
queue<pair<int, int> > q;
void f(int x, int y, int z) {
    if (c[x][y]) if (z > t) t = z, r = 1; else if (z == t)r++;
    ck[x][y] = z;
    for (int i = 0; i < 4; i++) {
        int tx = x + fx[i], ty = y + fy[i];
        if (tx<0 || ty<0 || tx>n + 1 || ty>m + 1 || ck[tx][ty]) continue;
        c[tx][ty] ? ck[tx][ty] = z + 1, q.push({ tx,ty }) : f(tx, ty, z);
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &c[i][j]);
    f(0, 0, 1);
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        f(x, y, ck[x][y]);
        q.pop();
    }
    printf("%d\n%d", t - 1, r);
    return 0;
}

2667번: 단지번호붙이기

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


$O(n^2)$

flood fill 문제

#include<cstdio>
#include<algorithm>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int n, c[27][27], a[25 * 25 + 1], cnt;
void dfs(int x, int y) {
    if (!c[x][y]) return;
    c[x][y] = 0;
    a[cnt]++;
    for (int i = 0; i < 4; i++) dfs(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%1d", &c[i][j]);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (c[i][j]) dfs(i, j), cnt++;
    printf("%d\n", cnt);
    std::sort(a, a + cnt);
    for (int i = 0; i < cnt; i++) printf("%d\n", a[i]);
    return 0;
}

1012번: 유기농 배추

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


$O(tmn)$

flood fill을 이용하여 지렁이 수를 구한다.

#include<stdio.h>
const int MAX_N = 50, fx[] = { 1,-1,0,0 }, fy[] = { 0,0,1,-1 };
int ck[MAX_N][MAX_N], t, m, n, k;
void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= m || y >= n || !ck[x][y]) return;
    ck[x][y] = 0;
    for (int i = 0; i < 4; i++) dfs(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d", &m, &n, &k);
        for (int i = 0, x, y; i < k; i++) scanf("%d %d", &x, &y), ck[x][y] = 1;
        int r = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) if (ck[i][j]) r++, dfs(i, j);
        printf("%d\n", r);
    }
    return 0;
}

4217번: 신성 문자

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


$O(chw)$

문자들은 구멍 개수로 구분하면 된다. flood fill을 이용해 풀어보자.

#include<stdio.h>
#include<string.h>
const int MAX_S = 2e2, fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int h, w, ck[MAX_S + 2][MAX_S + 2], res[200];
char p[] = { 'W','A','K','J','S','D' };
int ff(int x, int y, int c) {
    ck[x][y] = -1;
    int r = 0;
    for (int i = 0; i < 4; i++) {
        int tx = x + fx[i], ty = y + fy[i];
        if (tx<0 || tx>h + 1 || ty<0 || ty>w * 4 + 1) continue;
        if (ck[tx][ty] == 0) r += c, ff(tx, ty, 0);
        else if (ck[tx][ty] == 1 && c) r += ff(tx, ty, 1);
    }
    return r;
}
int main() {
    for (int c = 1;; c++) {
        scanf("%d %d", &h, &w);
        if (!h) break;
        memset(ck, 0, sizeof(ck));
        memset(res, 0, sizeof(res));
        for (int i = 1; i <= h; i++) {
            for (int j = 1, x; j <= w; j++) {
                scanf("%1x", &x);
                if (!x) continue;
                for (int k = 0; k < 4; k++) ck[i][j * 4 - k] = (x & 1 << k)>0;
            }
        }
        ff(0, 0, 0);
        printf("Case %d: ", c);
        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w * 4; j++)
                if (ck[i][j] == 1) res[p[ff(i, j, 1)]]++;
        for (int i = 'A'; i <= 'Z'; i++)
            for (int j = 0; j < res[i]; j++) printf("%c", i);
        puts("");
    }
    return 0;
}