[BOJ] 2186. 문자판

2186. 문자판

문제

조건

• N * M크기의 문자판
• 각 칸에는 알파벳 대문자만 존재
• 아무 칸에서 시작 가능
• 상하좌우 K개의 칸까지 이동가능
• 반드시 한 칸 이상 이동
• 제자리에 머무르는 것은 불가능
• 중복 방문 가능

입력

• 첫 줄
  • 문자판 크기 N, M개 $(1 \leq N, M \leq 100)$
  • 이동가능 거리 K $(1 \leq K \leq 5)$
• 다음 N개 줄
  • M개의 알파벳 대문자가 주어짐
• 영어 단어 $(1 \leq length \leq 80)$

출력

• 영어 단어를 만들 수 있는 모든 경로의 개수

풀이

가장 먼저 완전탐색으로 풀이가 가능한지 시도해보았지만, 시간복잡도가 불가능했다.

import sys
input = sys.stdin.readline

# 입력받기
n, m, k = list(map(int, input().split()))
board = [list(input()) for _ in range(n)]
word = input()

answer = 0

def get_cnt(x, y, cur):
    global answer

    # 모든 단어를 찾았을 때
    if cur == len(word):
        answer += 1
        return

    # 상하 탐색
    for i in range(max(0, x - k), min(n, x + k + 1)):
        if i != x and board[i][y] == word[cur]:
            get_cnt(i, y, cur + 1)

    # 좌우 탐색
    for j in range(max(0, y - k), min(m, y + k + 1)):
        if j != y and board[x][j] == word[cur]:
            get_cnt(x, j, cur + 1) 

# 완전 탐색
for i in range(n):
    for j in range(m):
        if board[i][j] == word[0]:
            get_cnt(i, j, 1)

print(answer)

그 다음은 bfs를 생각해보았다. 테스트케이스는 맞았지만, 여전히 시간초과
왜 시간초과가 났는지 생각해보면, 중복이 너무 많다는 것이다.

'직전 스펠링의 좌표'와 '현재 스펠링'가 같다면 어떤 경로로 왔든 같은 경우라고 볼 수 있다.
하지만 아래 코드는 모든 경로를 계속 찾아가야 하므로 중복이 많아질 수 밖에 없다.

import sys
input = sys.stdin.readline

# 입력받기
n, m, k = list(map(int, input().split()))
board = [list(input()) for _ in range(n)]
word = input()

answer = 0

# 인덱스 범위 검사
def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

# 방문 가능한지 검사
def can_go(x, y, cur):
    return in_range(x, y) and board[x][y] == word[cur]

def bfs():
    global answer
    dxs, dys = [0,0,1,-1], [1,-1,0,0]

    while q:
        x, y, cur = q.pop()
		
        # 단어가 완성된 경우
        if cur == len(word) - 1:
            answer += 1
        
        else:
            for a in range(1, k + 1):
                for dx, dy in zip(dxs, dys):
                    nx, ny = x + a * dx, y + a * dy
                    if can_go(nx, ny, cur + 1):
                        q.append((nx, ny, cur + 1))

q = deque()
answer = 0
for i in range(n):
    for j in range(m):
        if board[i][j] == word[0]:
            q.append((i, j, 0))
            bfs()

print(answer)

마지막으로 생각한 건, 다이나믹 프로그래밍을 활용한 'Memoization' 방법이었다.

dp[i][j][cur] := 문자판(i, j) 좌표가 영어 단어의 cur번째 알파벳일 때, 해당 좌표까지의 경로 개수

해당 dp테이블은 -1로 초기화 해둔다.

dxs = [-1,0,1,0]
dys = [0,1,0,-1]
dp = [[[-1] * len(word) for i in range(m)] for i in range(n)]

def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

def can_go(x, y, cur):
    return in_range(x, y) and board[x][y] == word[cur]
            
def dfs(x, y, cur):
    # 이미 방문한 곳인 경우
    if dp[x][y][cur] != -1:
        return dp[x][y][cur]
    
    # 단어를 완성한 경우
    if cur == len(word) - 1:
        return 1
    
    # 필요한 문자가 아닌 경우
    if board[x][y] != word[cur]:
        return 0
	
    # 상하좌우 k거리 떨어진 곳 전부 탐색
    cnt = 0
    for i in range(1, k + 1):
        for dx, dy in zip(dxs, dys):
            nx = x + i * dx
            ny = y + i * dy
            if can_go(nx, ny, cur + 1):
                cnt += dfs(nx, ny, cur + 1)
    dp[x][y][cur] = cnt

    return dp[x][y][cur]

answer = 0
for i in range(n):
    for j in range(m):
        if board[i][j] == word[0]:
            answer += dfs(i, j, 0)

시간복잡도

1. 이중 for 반복문: $O(N*M)$

2. DFS 함수 호출

   • DFS 함수는 각 셀에서 시작하여 가능한 모든 경로를 따라 이동
   • 그러나 동적 계획법(DP) 덕분에, 우리는 이미 방문한 각 셀의 결과를 저장하고 있음
   • 따라서, 각 셀에서 DFS 함수를 호출하는 데 필요한 시간은 상수 시간
   • 즉, 각 셀에 대한 DFS 함수 호출의 전체 시간 복잡도는 $O(N*M)$

3. DFS 내부의 반복문

   • 이 반복문은 k 번 반복하고, 각 반복에서 4개의 방향(상하좌우)에 대해 연산을 수행
   • 따라서 이 연산의 시간 복잡도는 $O(4K)$ =$O(K)$

따라서, 전체 시간복잡도는 $O(N*M*K)$

배열을 입력받는 과정이 매우 길어 input = sys.stdin.readline이 필요하고,
반복문이 많아서 PyPy3로 제출해야 시간초과가 나지 않는다.

전체 코드

# boj 3079.입국심사
import sys
input = sys.stdin.readline

# 입력받기
n, m, k = list(map(int, input().strip().split()))
board = [list(input().strip()) for _ in range(n)]
word = input().strip()

dxs = [-1,0,1,0]
dys = [0,1,0,-1]
dp = [[[-1] * len(word) for i in range(m)] for i in range(n)]

def in_range(x, y):
    return 0 <= x < n and 0 <= y < m

def can_go(x, y, cur):
    return in_range(x, y) and board[x][y] == word[cur]
            
def dfs(x, y, cur):
    # 이미 방문한 곳인 경우
    if dp[x][y][cur] != -1:
        return dp[x][y][cur]
    
    # 단어를 완성한 경우
    if cur == len(word) - 1:
        return 1
    
    # 필요한 문자가 아닌 경우
    if board[x][y] != word[cur]:
        return 0
	
    # 상하좌우 k거리 떨어진 곳 전부 탐색
    cnt = 0
    for i in range(1, k + 1):
        for dx, dy in zip(dxs, dys):
            nx = x + i * dx
            ny = y + i * dy
            if can_go(nx, ny, cur + 1):
                cnt += dfs(nx, ny, cur + 1)
    dp[x][y][cur] = cnt

    return dp[x][y][cur]

answer = 0
for i in range(n):
    for j in range(m):
        if board[i][j] == word[0]:
            answer += dfs(i, j, 0)

print(answer)

풀이 git

기타

dfs에 dp까지 응용하는 것을 생각하지 못하여 다른 블로그들을 보며 힌트를 얻었다. 특히, memoization에 익숙하지 않아서 이해하는데 어려웠다.