문자로 이루어진 매트릭스(2차원 배열) 보드가 있다고 가정해 봅시다. 각 셀에는 하나의 문자가 저장되어 있으며, 여기에 검색할 대상 문자열 word가 주어집니다. 우리가 확인해야 할 것은 이 단어가 매트릭스 안에서 왼쪽→오른쪽 또는 위→아래의 한 방향으로 연속된 문자들을 읽어 나타나는지 여부입니다.
문제 예시
예를 들어 입력이 다음과 같다고 해보겠습니다.
| a | n | t | s |
| s | p | i | n |
| l | a | p | s |
찾을 단어: "tip"
이 경우 출력은 True입니다. 세 번째 열을 위에서 아래로 읽으면 t → i → p, 즉 "tip"이 만들어지기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 보드의 각 행(row)에 대해:
- 행의 모든 문자를 이어 붙여 하나의 문자열로 만듭니다.
- 만들어진 문자열 안에 찾고자 하는 단어가 포함되어 있으면
True를 반환합니다.
- 행 검색에서 찾지 못했다면, 이번에는 열(column)을 검사합니다.
- 각 열 인덱스 i에 대해, 모든 행에서 i번째 문자를 모아 문자열로 만듭니다.
- 이 문자열 안에 단어가 포함되어 있으면
True를 반환합니다.
- 모든 행과 열을 검사한 후에도 단어를 찾지 못했다면
False를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
def solve(board, word):
# 각 행을 문자열로 변환하여 검색
for i in board:
i = "".join(i)
if word in i:
return True
# 각 열을 문자열로 변환하여 검색
i = 0
while i < len(board):
j = "".join([col[i] for col in board])
i += 1
if word in j:
return True
return False
board = [["a","n","t","s"],["s","p","i","n"],["l","a","p","s"]]
word = "tip"
print(solve(board, word))입력
[["a","n","t","s"], ["s","p","i","n"], ["l","a","p","s"]], "tip"
출력
True
동작 원리 설명
이 알고리즘은 크게 두 부분으로 구성됩니다. 첫 번째 반복문에서는 각 행을 join()으로 하나의 문자열로 합친 뒤, 파이썬의 in 연산자로 부분 문자열 여부를 검사합니다. 두 번째 while 루프에서는 리스트 컴프리헨션 [col[i] for col in board]를 사용해 같은 열 위치의 문자들을 모아 문자열을 만들고 동일하게 검사합니다.
시간 복잡도는 행 개수를 R, 열 개수를 C라고 할 때 O(R×C + R×C×L) 수준으로, L은 찾는 단어의 길이입니다. 즉, 보드의 모든 칸을 상수 번씩만 훑기 때문에 매우 효율적입니다.
단, 이 방법은 정방향(왼쪽→오른쪽, 위→아래) 검색만 지원한다는 점에 유의하세요. 역방향이나 대각선 방향까지 지원하려면 각 행·열 문자열과 그 역순 문자열을 함께 검사하도록 코드를 확장하면 됩니다.