[BOJ] 1706번_크로스워드_문자열 (C++)

[문제]

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

RxC크기의 크로스워드 퍼즐이 있다. 이 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 적혀 있게 된다. 아래는 R=5, C=5 인 경우 다푼 퍼즐의 한 예이다. 검은 칸은 금지된 칸이다.

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

다 푼 퍼즐이 주어졌을 때, 사전순으로 가장 앞서 있는 낱말을 구하는 프로그램을 만드는 문제이다.

[사용 알고리즘]

문자열

[풀이 핵심]

• 문제의 예시를 보면 알 수 있듯이 "단어"란 알파벳이 2개 이상이어야 한다는 점을 유의하자.
• 입력받은 graph[][]배열의 가로와 세로를 완전 탐색하며 '#'이 아닐 경우 temp에 알파벳을 쌓아 문자열을 만들어 주고, '#' 일 경우에 이전까지 쌓은 temp 문자열이 단어라면 result 벡터에 push해준다. 만약 단어가 아니라면 temp 문자열을 초기화해준다. 이런식으로 result 벡터에 가로, 세로에서 나올 수 있는 모든 단어를 저장한다.
• 마지막으로 algorithm 헤더 파일의 sort함수를 사용해서 사전순으로 정렬하면 첫번째 원소가 정답이다.

[코드]

//boj1706번_크로스워드_문자열

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

char graph[21][21];

int main() {
	int R, C;
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> graph[i][j];
		}
	}

	vector<string> result;

	for (int i = 0; i < R; i++) {
		string temp = "";
		bool check = false;

		for (int j = 0; j < C; j++) {
			if (graph[i][j] == '#') {
				if (temp.size() >= 2) {
					result.push_back(temp);
					temp = "";
						
					check = true;
				}
				else {
					temp = "";
				}
			}
			else {
				temp += graph[i][j];
			}
		}
		if (!check && temp.size() >= 2) {
			result.push_back(temp);
		}
	}

	for (int i = 0; i < C; i++) {
		string temp = "";
		bool check = false;

		for (int j = 0; j < R; j++) {
			if (graph[j][i] == '#') {
				if (temp.size() >= 2) {
					result.push_back(temp);
					temp = "";

					check = true;
				}
				else {
					temp = "";
				}
			}
			else {
				temp += graph[j][i];
			}
		}
		if (!check && temp.size() >= 2) {
			result.push_back(temp);
		}
	}

	sort(result.begin(), result.end());

	cout << result[0];
}