BOJ - 3005번 크로스워드 퍼즐 쳐다보기(C++)

문제 출처: https://www.acmicpc.net/problem/3005

문제 난이도

Silver 1

문제 접근법

첨에 문제가 이해가 안가서 삽질 꽤나 했다.
그래프 탐색 푸는 것처럼 풀면 된다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int dy[2][2] = { {1,0}, {0,1} };
vector<string> arr;
set<string> ans;
bool ch[21][21][2];


void isPossible(int x, int y, int type) {
	ch[x][y][type] = true;
	string res = "";
	res += arr[x][y];
	int nx = x + dy[type][0];
	int ny = y + dy[type][1];
	while (nx < arr.size() && ny < arr[0].size() && arr[nx][ny] != '#') {
		ch[nx][ny][type] = true;
		res += arr[nx][ny];
		nx += dy[type][0];
		ny += dy[type][1];
	}
	if (res.size() >= 2) ans.insert(res);
}



int main() {
	int R, C;
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		string str;
		cin >> str;
		arr.push_back(str);
	}
	string res = "";
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (arr[i][j] == '#') continue;
			for (int k = 0; k < 2; k++) {
				if (!ch[i][j][k]) isPossible(i, j, k);
			}
		}
	}
	for (auto x : ans) {
		cout << x << "\n";
		break;
	}
	return 0;
}

피드백

진짜 첨에 삽질 많이 했다.. 처음에는 0행과 0열만 비교해서 탐색했고 # 장애물이 나오면 return했다. 근데 ###으로 둘러쌓인 낱말존이 있을 수 있어서 이거 때문에 다른 식으로 접근했다가 틀렸다.
결국 silver 1인데 어떤 식으로 코드를 짜야할지가 떠오르지 않아서 다른 사람 풀이를 참고했다.. check 삼중 배열을 둬서 해결한 거 보고 아차 싶었다.