백준 1706 크로스워드 C++

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

1706번: 크로스워드

---

문제

동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 적혀 있게 된다. 아래는 R = 5, C = 5 인 경우 다 푼 퍼즐의 한 예이다. 검은 칸은 금지된 칸이다.

세로 또는 가로로 연속되어 있고, 더 이상 확장될 수 없는 낱말이 퍼즐 내에 존재하는 단어가 된다. 위의 퍼즐과 같은 경우, 가로 낱말은 good, an, messy, it, late의 5개가 있고, 세로 낱말은 game, one, sit, byte의 4개가 있다. 이 중 사전식 순으로 가장 앞서 있는 낱말은 an이다.

다 푼 퍼즐이 주어졌을 때, 퍼즐 내에 존재하는 모든 낱말 중 사전식 순으로 가장 앞서 있는 낱말을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에는 퍼즐의 R과 C가 빈 칸을 사이에 두고 주어진다. (2 ≤ R, C ≤ 20) 이어서 R개의 줄에 걸쳐 다 푼 퍼즐이 주어진다. 각 줄은 C개의 알파벳 소문자 또는 금지된 칸을 나타내는 #로 이루어진다. 낱말이 하나 이상 있는 입력만 주어진다.

---

출력

첫째 줄에 사전식 순으로 가장 앞서 있는 낱말을 출력한다.

---

퍼즐이 있고 각 칸마다 알파벳이 적혀있다. 검쟁색으로 표시된 부분은 금지된 칸이고, 이부분은 알파벳이 존재하지 않습니다.

세로 , 가로로 연속되어있고, 더 이상 낱말이 확장될 수 없으면 퍼즐 내에 존재하는 단어가 됩니다.

위에서,  가로로 만들어지는 단어는, good, an, messy, it(단어길이가 1이면 건너뜀), late가 존재하고,

세로로 만들어지는 단어는, game, one, sit, byte 4개입니다.

 

 

일단 R과 C를 입력받았고, 단어가 만들어지면 전역 벡터 v에 새로운 단어가 들어갑니다.

int c,r; //c는 세로, r는 가로
char map[21][21];
vector<string> v; //새로운 문자열을 집어 넣을 전역 벡터

 

일단 가로로 만들어지는 단어를 얻기위해 함수를 하나 만들었습니다.

이 함수는 일단 모든 행에 대해서 가로로 문자열을 만드는데, find_word라는 bool변수와 

str이라는 문자열 변수를 하나 선언했습니다. 

 

그 후, map[i][j]가 #이고 문자열의 길이가 2 이상이면, 유효한 단어( 길이가 1이면 유효하지 않은 단어)이므로,

fint_word를 true로 바꿔주고, 만들어진 단어 str을 벡터에 넣었습니다.

문자열 str을 빈 문자열로 초기화 해 주었습니다.

 

그 외의 경우는 str이라는 변수에 map[i][j]를 덧붙여서 새로운 단어를 만드는 과정이 진행됩니다.

만약 find_word가 false라면, #를 만나지 않고 쭉 단어를 만든 경우이므로, 길이가 2이상이면

벡터에 넣어주었습니다.

 

void row_word(){ //가로로 만들어지는 단어 (단어 길이가 1이면 안됌)
    
    for(int i = 0;i<c;i++){
        string str = "";
        bool find_word = false;
        
        for(int j = 0;j<r;j++){
            if(map[i][j] == '#' && str.size() >= 2){
                find_word = true;
                v.push_back(str);
                str = "";
                continue;

            }
            else if(map[i][j] == '#' && str.size() < 2){
                str = "";
                continue;
            }
            else{
                str += map[i][j];
            }
        }
        if(find_word == false && str.size() >= 2){
            v.push_back(str);
        }
    }
    
}

 

세로로만들어지는 단어를 구하는 함수는 다음과 같습니다.

 

void column_word(){ //세로로 만들어지는 단어
    for(int i = 0;i<r;i++){
        bool find_word = false;
        string str = "";
        
        for(int j = 0;j<c;j++){
            if(map[j][i] == '#' && str.size() >= 2){
                find_word = true;
                v.push_back(str);
                str = "";
                continue;
            }
            else if(map[j][i] == '#' && str.size() < 2){
                str = "";
                continue;
            }
            else{
                str += map[j][i];
            }
        }
        if(find_word == false && str.size() >= 2){
            v.push_back(str);
        }
    }
}

논리는 동일하지만 세로로 만들어지는 단어를 구하기 위해, i는 0부터 r까지, j는 0부터 c까지 돌고,

map[j][i]이 #인 경우에 금지된 칸입니다.

 

전체 코드입니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int c,r;
char map[21][21];
vector<string> v;

void row_word(){ //가로로 만들어지는 단어 (단어 길이가 1이면 안됌)
    
    for(int i = 0;i<c;i++){
        string str = "";
        bool find_word = false;
        
        for(int j = 0;j<r;j++){
            if(map[i][j] == '#' && str.size() >= 2){
                find_word = true;
                v.push_back(str);
                str = "";
                continue;

            }
            else if(map[i][j] == '#' && str.size() < 2){
                str = "";
                continue;
            }
            else{
                str += map[i][j];
            }
        }
        if(find_word == false && str.size() >= 2){
            v.push_back(str);
        }
    }
    
}


void column_word(){ //세로로 만들어지는 단어
    for(int i = 0;i<r;i++){
        bool find_word = false;
        string str = "";
        
        for(int j = 0;j<c;j++){
            if(map[j][i] == '#' && str.size() >= 2){
                find_word = true;
                v.push_back(str);
                str = "";
                continue;
            }
            else if(map[j][i] == '#' && str.size() < 2){
                str = "";
                continue;
            }
            else{
                str += map[j][i];
            }
        }
        if(find_word == false && str.size() >= 2){
            v.push_back(str);
        }
    }
}

int main(void){
    cin >> c >> r;
    for(int i = 0;i<c;i++){
        for(int j = 0;j<r;j++){
            cin >> map[i][j];
        }
    }
    
    row_word();
    column_word();
    sort(v.begin(),v.end());
    cout << v[0];
}