백준 2186번 - 문자판

출처 : 2186번: 문자판 (acmicpc.net)

2186번: 문자판

 

문자판 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

128 MB

5137

1078

718

21.337%

문제

알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.

K	A	K	T
X	E	A	S
Y	R	W	U
Z	B	Q	P

이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.

		X
		X
X	X		X	X
		X
		X

반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.

이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성하시오.

위의 예에서 영단어가 BREAK인 경우에는 다음과 같이 3개의 경로가 존재한다. 앞의 수는 행 번호, 뒤의 수는 열 번호를 나타낸다.

• (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
• (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
• (4, 2) (3, 2) (2, 2) (2, 3) (1, 3)

입력

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

출력

첫째 줄에 경로의 개수를 출력한다. 이 값은 int 범위이다.

 

---

[ 문제 설명 ]

 

4방향으로 움직이면서 원하는 문자열과 같은 것을 찾는 문제입니다.

 

다면 여기서 다른 문제들이랑 다른 점은 이동 범위와 맞는 모든 수를 찾아야 하는 부분입니다.

 

이점을 가리키는 코드 부분은 주석 처리하였습니다.

 

코드로 보시는 게 문제를 이해하는데 쉬울 겁니다.

 

---

[ 코드 ]

 

# 왼, 아래, 오, 위
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def dfs(x, y, idx):
    if idx >= len(target):  # 왜 이게 먼저 와야 되는 걸까???? 그 이유를 알아야함!
        return 1            # 순회하기 전에 체크를 먼저해야 indexerror가 발생 x
    if dp[x][y][idx] != -1:
        return dp[x][y][idx]  # 리턴만 해줘도 됨

    dp[x][y][idx] = 0  # 방문 표시 겸 결과 값
    for i in range(4):
        tmp_x, tmp_y = x, y
        # k는 이동 한도 범위를 나타냄
        for _ in range(k):
            nx = tmp_x + dx[i]
            ny = tmp_y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if matrix[nx][ny] == target[idx]:
                    dp[x][y][idx] += dfs(nx, ny, idx + 1)
            tmp_x, tmp_y = nx, ny  # k가 2 이상일 때 사용하기 위해
    return dp[x][y][idx]


n, m, k = map(int, input().split())

# print(matrix)
matrix = []
for _ in range(n):
    matrix.append(list(input()))
# print(matrix)
target = list(input())
# print(target)
start = []
# 첫 문자가 같은걸 모조리 찾아서 시작하기 위해 우선 찾는것!
for i in range(n):
    for j in range(m):
        if matrix[i][j] == target[0]:
            start.append([i, j])
# memset(dp, -1, sizeof(dp)) 을 멀로 대채해야 할까?
dp = [[[-1] * len(target) for _ in range(m)] for _ in range(n)]
res = 0
for i in range(len(start)):
    x, y = start[i]
    res += dfs(x, y, 1)
print(res)

 

---

후기

 

일반적인 지도가 주어지고 이동하는 문제이지만

여러 번 찾아야 되는 것과

가동이 이용범위를 구현해야 하는 부분에

생각해야 하는 문제입니다.