백준 3005번 C++ 풀이

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

3005번: 크로스워드 퍼즐 쳐다보기

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	실버 2

문제

크로스워드 퍼즐은 R*C크기의 직사각형으로 이루어져 있고, 각 칸은 비어있거나 막혀있다. 퍼즐은 가로(왼쪽->오른쪽) 또는 세로(위->아래)로 연속된 빈 칸에 단어를 채우면서 푼다.

동혁이는 크로스워드 퍼즐을 풀지 않는다. 그는 풀려있는 퍼즐을 쳐다본다. 그런 후에, 그는 그 퍼즐에서 사전순으로 제일 앞서는 단어를 찾는다. (단어는 적어도 2글자이다.)

크로스워드 퍼즐이 주어졌을 때, 사전순으로 제일 앞서는 단어를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C (2 ≤ R, C ≤ 20)가 주어진다. R는 행의 개수, C는 열의 개수이다. 그 다음 R개의 줄엔 C개의 문자가 포함되어 있다. 각 문자는 영어 알파벳 소문자 또는 '#'이며, '#'인 경우에는 막혀있는 것이다.

출력

첫째 줄에 사전순으로 제일 앞서는 단어를 출력한다. 정답이 항상 존재하는 경우만 입력으로 주어진다.

---

이번 랜덤 실버 문제는 문자열, 파싱, 구현 문제이다. 크로스워드 퍼즐판에서 단어를 잘 합치기만 하면 되는 문제이다.

 

다만, 해당 경우를 조심해야한다. 예제 입력1을 보자.

 

luka
o#a#
kula
i#a#

 

에서 2행 3열의 a를 보자(o#a# 에서의 a). 해당 a에서 아래로 단어를 선택하면 ala라는 단어가 나오는데, 이는 유효한 단어가 아니다. kala에서 k를 떼버린 셈인데, 크로스워드 퍼즐은 이런식으로 단어를 쓰지 않으니 말이다. 이것만 유의하면 나머지는 구현문제기 때문에, 주어진 조건대로 작성하자.

 

#include <bits/stdc++.h>
#define ALPHACNT 26
using namespace std;

int r, c;
bool alphaInBoard[ALPHACNT] = { false };
vector<string> board;

void input() {
    cin >> r >> c;
    board.resize(r);
    for (auto& line : board) {
        cin >> line;
        // 등장한 알파벳을 체크하여, 등장하지 않은 알파벳은 체크하지 않도록 한다.
        for (char alpha : line) {
            if (alpha != '#') alphaInBoard[alpha - 'a'] = true;
        }
    }
}

string getRowWord(int x, int y) { // 가로로 단어를 구한다.
    string word;
    word += board[y][x];
    if (x > 0 && board[y][x - 1] != '#') return word;

    for(int col = x + 1; col < c; col++) {
        if (board[y][col] == '#') break;
        word += board[y][col];
    }
    return word;
}

string getColWord(int x, int y) { // 세로로 단어를 구한다.
    string word;
    word += board[y][x];
    if (y > 0 && board[y - 1][x] != '#') return word;
        
    for(int row = y + 1; row < r; row++) {
        if (board[row][x] == '#') break;
        word += board[row][x];
    }
    return word;
}

// row와 col을 비교하여 return한다. 이때 단어의 길이도 체크하게 된다.
string& compareTwoSubStr(string& row, string& col) {
    if (row.length() == 1) return col;
    else if (col.length() == 1) return row;
    else return row < col ? row : col;
}

void sol() {
    string answer = "zzzzzzzzzzzzzzzzzzzzz"; // 절대 등장할 수 없는 단어.
    string row;
    string col;

    for (int i = 0; i < ALPHACNT; i++) {
        // 등장하지 않는 알파벳이면 검사하지 않는다.
        if (!alphaInBoard[i]) continue;

        for(int y = 0; y < r; y++) {
            for(int x = 0; x < c; x++) {
                if (board[y][x] == i + 'a') {
                    row = getRowWord(x, y);
                    col = getColWord(x, y);
                    if (row.length() == 1 && col.length() == 1) continue;
                    
                    string& shorterStr = compareTwoSubStr(row, col);
                    answer = answer < shorterStr ? answer : shorterStr;
                }
            }
        }
    }

    cout << answer;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    sol();
}