아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

꺾인 단어 찾기

면접 대비

시간 제한6초메모리 제한1024 MB

요약
글자 격자가 주어질 때, 같은 칸을 다시 지나도 되지만 제자리에 머물 수는 없다는 조건에서 목표 단어를 정확히 k번 방향을 꺾어 만들 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
DFS, 백트래킹, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

여러분은 아마 일반적인 단어 찾기 퍼즐을 잘 알고 있을 것이다. 글자 격자와 찾아야 할 단어가 주어지고, 단어는 가로, 세로, 대각선 방향의 직선으로 (각 방향에 대해 거꾸로도 가능하다) 놓여 있을 수 있다. 예를 들어 다음은 글자 격자이다.

그림 1: 단어 찾기 격자

단어 "JAVA"는 오른쪽 아래 모서리에서 대각선 위쪽으로 찾을 수 있다.

꺾인 단어 찾기에서는 단어를 이루는 경로가 하나 이상의 "꺾임"을 가질 수 있다. 꺾임이란 경로가 방향을 바꾸는 지점이다. 예를 들어 주어진 격자에서 단어 "PYTHON"은 33개의 꺾임(T, H, O에서 각각 하나씩)으로 만들 수 있다.

그림 2: "PYTHON"의 꺾인 철자

꺾임을 허용하면 글자를 재사용할 수 있다. 단어 "CPLUSPLUS"는 격자의 오른쪽 위 모서리에서 (55개의 꺾임으로) 찾을 수 있다. 하지만 같은 글자에 연달아 머무를 수는 없으므로 이 격자에서 단어 "HASKELL"은 만들 수 없다(그 대신 적어도 1111개 이상의 흔한 프로그래밍 언어를 찾을 수 있다). 여러분의 임무는 주어진 단어를 정확히 주어진 개수의 꺾임으로 만들 수 있는지 판별하는 것이다.

입력

입력의 첫 줄에는 격자의 행과 열의 개수를 나타내는 두 양의 정수 rr과 cc가 주어진다 (r,c≤10r, c \leq 10). 그다음 rr개의 줄에 걸쳐 cc개의 대문자가 주어진다. 글자 사이는 공백으로 구분된다. 격자 다음에는 두 줄이 이어진다. 첫 줄에는 꺾임의 개수를 나타내는 정수 kk가 주어진다. 둘째 줄에는 찾아야 할 대문자 단어가 주어지며, 길이는 최대 100100이다.

출력

주어진 격자에서 주어진 단어를 정확히 kk개의 꺾임으로 만들 수 있으면 YES를, 아니면 NO를 출력한다.

예제3

  1. 예제 1

    입력
    5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
0
JAVA
    예상 출력
    YES

  2. 예제 2

    입력
    5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
3
PYTHON
    예상 출력
    YES

  3. 예제 3

    입력
    5 5
L M E L C
C A K U P
D O V S Y
R N L A T
P G O H J
4
PYTHON
    예상 출력
    NO