BOJ 11370 · Spawn of Ungoliant

알고리즘 분류 : DFS  

거미가 영역을 확장하는 것을 구현하면 된다. 전형적인 플러드 필 문제이다.

• 거미의 위치('S')부터 시작해서 DFS로 뻗어나간다.
• 나무('T')에만 뻗어나갈 수 있으며, 거쳐간 나무는 'S'로 바꾼다.

---

C++ 소스코드

#include <cstdio>

int h, w;
char a[101][101];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int dfs(int x, int y) {
    for (int i=0; i<4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
        if (a[nx][ny] == 'T') {
            a[nx][ny] = 'S';
            dfs(nx, ny);
        }
    }
}

int main() {
    while (true) {
        scanf("%d %d", &w, &h);
        if (!w) break;
        for (int i=0; i<h; i++) scanf("%s", a[i]);
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (a[i][j] == 'S') {
                    dfs(i, j);
                    break;
                }
            }
        }
        for (int i=0; i<h; i++) printf("%s\n", a[i]);
    }
    return 0;
}

---

Python 3 소스코드

def dfs(x, y):
    for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
        nx, ny = x+dx, y+dy
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if a[nx][ny] == 'T':
            a[nx][ny] = 'S'
            dfs(nx, ny)

while True:
    w, h = map(int, input().split())
    if not w:
        break
    a = [list(input().strip()) for _ in range(h)]
    for i in range(h):
        if a[i].count('S'):
            dfs(i, a[i].index('S'))
            break
    for i in range(h):
        print(''.join(map(str, a[i])))

---

참고

• 백준 온라인 저지 : BOJ 11370