[Algorithm] 백준 - 크로스워드 퍼즐 쳐다보기 (3005번)

문제

[백준] 크로스워드 퍼즐 쳐다보기
(Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #2 3번)

사용 알고리즘

 

- 구현

해결방법

• 행(row)방향, 열(column)방향으로 전체 탐색하면서 나오는 모든 단어들을 비교해 답을 구한다
• 알파벳을 만나는 경우, res 변수에 더해준다
• 벽을 만나는 경우, 이전까지 만들어진 단어(res)를 temp에 저장한 뒤, 다시 알파벳이 나오면 그 지점을 시작으로 다시 단어를 만든다
  • res가 2글자 이상인 경우
    • temp도 2글자 이상인 경우
      • temp = min(res, temp)
        >> temp를 최소값으로 갱신시킨다
    • temp가 1글자 이하인 경우
      • temp = res
        >> temp에 res를 담아준다
  • res가 1글자 이하인 경우
    
    • temp = temp
      >> temp를 유지한다. res는 단어가 아니므로 저장할 필요 X
• 행/열 한 줄을 다 탐색한 후에 res와 temp를 비교해 res에 최종적으로 가장 최소값을 넣어준다. 그 값을 전체 행/열 중 최소 값을 넣는 first_word 변수와 비교한 후 first_word를 갱신시킨다
• 단어 성립 기준
  • 2글자 이상 (길이 >= 2)
  • 벽이 있는 경우 끊는 지점
    • ex) 4 x 5 
      abaca
      da##b
      abb#b
      abbac
      • 행 방향 탐색 후 발견되는 단어
        
        • abaca
        • da
        • abb (답)
        • abbac
      • 열 방향 탐색 후 발견되는 단어
        • adaa
        • dabb
        • bb
        • abbc

소스코드

사용언어 : C++

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int R, C;
char puz[22][22];
string first_word = "";
 
void find_first_word(int y, int x, int dir)
{
    for (int i=0; i<y; i++) {
        string res = "";
        string temp = "";
        for (int j=0; j<x; j++) {
            char c = dir ? puz[j][i] : puz[i][j];
            if (c == '#') {
                temp = (res.length() > 1) ? ((temp.length() > 1) ? min(temp, res) : res) : ((temp.length() > 1) ? temp : "");
                res = "";
                continue;
            }
            res += c;
        }
        res = (res.length() > 1) ? ((temp.length() > 1) ? min(res, temp) : res) : ((temp.length() > 1) ? temp : "");
        if (res.empty()) continue;
 
        first_word = (first_word.empty()) ? res : min(first_word, res);
    }
}
 
int main()
{
    cin >> R >> C;
 
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            cin >> puz[i][j];
        }
    }
 
    find_first_word(R, C, 0); // row 탐색
    find_first_word(C, R, 1); // column 탐색
 
    cout << first_word << endl;
 
    return 0;
}

 

 

한줄평

전체 탐색이. .아닌가 ??