[BOJ] 1706번 - 크로스워드

백준 1706번 크로스워드

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128 MB	365	138	129	41.479%

문제

동혁이는 크로스워드 퍼즐을 좋아한다. 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개의 알파벳 소문자 또는 금지된 칸을 나타내는 #로 이루어진다.

출력

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

제한

예제 입력 1

4 5
adaca
da##b
abb#b
abbac

예제 출력 1

abb

 

출처

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

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 문자열
• 정렬
• 파싱

접근 방법

문제 조건에 따라 중복되는 결과 없이 값을 빼오기 위해서, 각 행은 오른쪽 방향으로, 각 열은 아랫방향으로 탐색해야한다.

DFS의 방문조건에 의해서 가로/세로 방향으로 섞어서 DFS를 수행한다면 방문을 해야함에도 불구하고 방문을 하지 못하는 상황이 발생될 수 있기 때문에 가로/세로 부분으로 나누어 DFS를 수행하였다.

소스 코드

#define W 0
#define H 1
#include <bits/stdc++.h>
using namespace std;
int N,M;
string board[21];
const int dir[2][2] = {{0,1},{1,0}};
bool visited[21][21];
vector<string> answer;
void DFS(int y, int x, string str, int dirIdx){
    int ny = y + dir[dirIdx][0];
    int nx = x + dir[dirIdx][1];
    if( ny < 0 || nx < 0 || ny >= N || nx >= M || visited[ny][nx] || board[ny][nx] == '#' ){
        if( str.length() >= 2 )
            answer.push_back(str);
        return ;
    }
    visited[ny][nx] = true;
    DFS(ny,nx, str + board[ny][nx], dirIdx);

}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> M ;
    for(int i=0; i<N; i++){
        cin >> board[i];
    }

    // 가로 DFS
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++) {
            string str;
            str.push_back(board[i][j]);
            if (!visited[i][j] && board[i][j] != '#')
                DFS(i, j, str, W);
        }
    }

    // 세로 DFS
    memset(visited, false, sizeof(visited));
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            string str;
            str.push_back(board[i][j]);
            if(!visited[i][j] && board[i][j] != '#')
                DFS(i,j,str,H);
        }
    }
    sort(answer.begin(), answer.end());
    cout << answer[0];
    return 0;
}