여러분들의 열화[?]와 같은 성원에 힘입어 알고스팟 에디토리얼에도 올리는 스탱입니다.

A. Alien Language
외계어는 L개의 소문자로 이루어진 단어 D개가 있다. N개의 패턴이 주어졌을 때, 각각의 패턴에 해당하는 단어가 몇개씩 있는지 구하는 프로그램을 작성하시오. 패턴의 각 글자는 소문자거나 괄호로 둘러쌓여진 소문자들의 그룹으로 이루어져 있다. 예를 들어 (ab)d(dc) 같은 경우, 첫 글자는 a 또는 b, 두번째 글자는 d, 세번째 글자는 d 또는 c인 단어를 의미하며, add, adc, bdd, bdc 의 4가지 가능성이 있다.
[spoiler="더 보기..."]
간단한 패턴 매칭 문제입니다. 괄호 처리만 잘 해주면 특별히 코딩에 어려운 부분은 없습니다.

#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int check(string a, string b)
{
    int pos = 0;
    for (int i = 0; i < b.size(); ++i)
    {
        string word = "";
        if (a[pos] == '(')
        {
            for (int j = pos + 1; ; ++j)
                if (a[j] == ')') 
                {
                    pos = j + 1;
                    break; 
                }
                else word += a[j];
        }
        else 
        {
            word = a[pos];
            pos++;
        }
        bool isOK = false;
        for (int j = 0; j < word.size(); ++j)
            if (word[j] == b[i]) isOK = true;
        if (!isOK) return 0;
    }
    if (pos != a.size()) return 0;
    return 1;
}
int main()
{
    int L, D, N;
    cin >> L >> D >> N;
    vector<string> word(D);
    for (int i = 0; i < D; ++i)
        cin >> word[i];
    for (int q = 0; q < N; ++q)
    {
        int ret = 0;
        string str;
        cin >> str;
        for (int i = 0; i < D; ++i)
        {
            if (check(str, word[i])) ret++;
        }
        printf("Case #%d: %dn", q + 1, ret);
    }
}

[/spoiler]

B. Watersheds
높이가 표시된 지도가 있다. 어떤 위치에 비가 오는 경우, 빗물은 특정한 조건에 따라 흐른다.

1. 각 칸에서 빗물은 인접한 4개의 칸으로만 흐른다
2. 각각의 칸에 대해서, 현재 위치보다 낮은 곳이 주변에 없는 경우, 물은 흐르지 않고, 현재의 칸은 sink가된다.
3. 그렇지 않으면 물은 인접한 칸들 중 제일 낮은 칸으로 흐른다.
4. 만약 3번의 경우, 제일 낮은 높이의 인접한 칸이 여러 개 있는 경우, N, W, E, S의 순서대로 흐른다. 모든 칸의 물은 직접 혹은 간접적으로 흐르게 되고, 이는 sink에서 모이게 된다. 동일한 sink에 모이는 지점들을 하나의 그룹으로 묶는다고 할 때, 그룹들을 알파벳으로 구분해 보자. [spoiler="더 보기..."] 주어진 지도에서 물이 어느 방향으로 흐르는지를 그래프로 나타낼 수 있습니다. 이 그래프에서 어떤 sink로 도달하는지를 찾아서 같은 sink끼리 묶어주면 됩니다. 저는 어떤 칸에서 물이 흐른다면 이를 무방향성 그래프로 만들어서 같은 그룹을 묶는 방식으로 해결하였습니다. ~~~ cpp

#include
#include
#include
#include
#include
using namespace std;
int table[101][101];
vector< int > graph[101][101];
char ret[101][101];
char ch;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
void go(int x, int y)
{
queue > Q;
Q.push( make_pair( x, y ));
ret[x][y] = ch;
while (!Q.empty())
{
pair now = Q.front(); Q.pop();
x = now.first, y = now.second;
for (int i = 0; i < graph[x][y].size(); ++i)
{
int nx = x + dx[ graph[x][y][i] ];
int ny = y + dy[ graph[x][y][i] ];
if (ret[nx][ny] == '?')
{
ret[nx][ny] = ch;
Q.push(make_pair( nx, ny ));
}
}
}
}
int main()
{
int T;
cin >> T;
int n, m;
for (int q = 1; q <= T; ++q)
{
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
cin >> table[i][j];
graph[i][j].clear();
ret[i][j] = '?';
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
bool isSink = true;
int mn = table[i][j];
int p = -1;
for (int k = 0; k < 4; ++k)
{
int nx = i + dx[k], ny = j + dy[k];
if (nx < 0 || nx == n || ny < 0 || ny == m) continue;
if (table[i][j] > table[nx][ny]) isSink = false;
if (mn > table[nx][ny])
{
mn = table[nx][ny];
p = k;
}
}
if (isSink) continue;
graph[i][j].push_back( p );
graph[i + dx[p]][j + dy[p]].push_back( 3 - p );
}
}
ch = 'a';
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if( ret[i][j] == '?' )
{
go(i, j);
ch++;
}
}
}
cout << "Case #" << q << ":" << endl;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
cout << ret[i][j] << ' ';
cout << endl;
}
}
return 0;
}

[/spoiler]




C. Welcome to Code Jam
  주어진 string에서 "welcome to code jam"을 만들 수 있는 조합의 경우의 수를 출력하여라. 단 10000으로 나눈 나머지를 구하시오
[spoiler="더 보기..."]
  전형적인 DP 문제입니다... 10000으로 나눈 나머지는 고등학교때 배우는 나머지 정리[ (A + B) % C = ((A % C) + (B % C)) % C
 ] 를 이용하시면 구할 수 있습니다.
~~~ cpp

#include <cstdio>
#include <iostream>
#include <sstream>
using namespace std;
int T;
string s = "welcome to code jam";
int table[505][25];
int main()
{
    string str;
    char tmp[1005];
    fgets(tmp, 1000, stdin); str = tmp;
    istringstream sin(str); sin >> T;
    for (int Q = 1; Q <= T; ++Q)
    {
        fgets(tmp, 1000, stdin); str = tmp;
        memset(table, 0, sizeof(table));
        for (int i = 0; i < str.size(); ++i)
        {
            for (int j = 0; j < s.size(); ++j)
            {
                if (i != 0) table[i][j] = table[i - 1][j];
                if (str[i] == s[j])
                {
                    if (j == 0) table[i][j]++;
                    else if (i > 0) table[i][j] += table[i - 1][j - 1];
                }
                table[i][j] %= 10000;
            }
        }
        printf("Case #%d: %04dn", Q, table[str.size() - 1][s.size() - 1]);
    }
}

[/spoiler]