[백준/Python]20166: 문자열 지옥에 빠진 호석

문제

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

백준 문제집 - 0x15강 - 해시

 

알고리즘: 해시를 사용한 집합과 맵, 깊이 우선 탐색(DFS), 그래프 탐색, 다이나믹 프로그래밍

---

풀이

 

주의깊게 봐야 할 조건은 다음과 같다.

• 방문했던 곳에 다시 방문 가능
• 환형 구조로 이루어진 좌표
• 조합이 아닌 순열 (순서가 다르면 다른것으로 계산)
• 대각선 이동 가능

또한 단어는 중복으로 주어질 수 있으므로, 딕셔너리에 이미 계산된 값이 있다면 탐색할 필요 없이 그 값을 출력해주면 된다.
없다면 아래의 탐색 과정을 진행한다.

1. 단어의 첫 문자와 일치하는 좌표들을 리스트에 저장한다.
2. 만약 단어의 길이가 1이라면 리스트의 길이를 딕셔너리에 저장 후 출력.
3. 아니라면, 저장한 좌표를 하나씩 꺼내며 DFS를 진행한다. (단어, 다음 인덱스, x, y)
   • 대각선 포함 8개의 방향을 탐색한다.
   • 해당 좌표의 값과 찾고자 하는 단어[인덱스]의 값이 일치한다면 DFS를 실행한다.
   • 인덱스가 단어의 길이와 같아지면 카운팅 +1 후 리턴.

 

전체 코드

# 메모리: 32412KB / 시간: 364ms
from sys import stdin


input = stdin.readline

N, M, K = map(int, input().split())
field = [input().rstrip() for _ in range(N)]
words = [input().rstrip() for _ in range(K)]

count = {word: 0 for word in words}

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

def dfs(target, idx, x, y):
    if idx == len(target):  # 인덱스가 word의 길이와 같아지면 카운트 추가
        count[target] += 1
        return

    for i in range(8):
        nx = (x + dx[i]) % N
        ny = (y + dy[i]) % M

        # 다음에 올 문자와 (nx, ny)의 값이 일치하다면 dfs 실행
        if field[nx][ny] == target[idx]:
            dfs(target, idx+1, nx, ny)


for word in words:
    # 앞서 카운팅했던 단어일경우 구해놓았던 값을 그대로 출력
    if count[word] > 0:
        print(count[word])
        continue

    # 단어의 첫 문자와 일치하는 좌표들을 저장
    start = []

    for i in range(N):
        for j in range(M):
            if field[i][j] == word[0]:
                start.append((i, j))

    if len(word) == 1:  # 단어의 길이가 1일경우
        print(len(start))
    else:
        for x, y in start:  # 다음 인덱스를 넣고 dfs 실행
            dfs(word, 1, x, y)
        print(count[word])

참고로 위 풀이 방식 그대로 제출했다가 6번정도 빠꾸먹었다.
알고보니 단어들을 딕셔너리로 입력받는 바람에 중복 단어 처리가 안됐던것^^;;
의식의 흐름대로 풀다 보니 그런것같은데... 덕분에 조금 심란했었다.

아무튼 그 과정에서 다른 풀이들을 찾아봤었는데, 완전탐색으로 푼 분들이 꽤 많았다.

 

완전탐색으로 푼 코드

# 메모리: 53232KB / 시간: 940ms
from sys import stdin


input = stdin.readline

N, M, K = map(int, input().split())
field = [input().rstrip() for _ in range(N)]
words = [input().rstrip() for _ in range(K)]

parts = {}

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]


def dfs(x, y, depth, word: str):
    if depth > 5:  # 문자열은 최대 5글자
        return

    # if word in words 조건을 넣으면 시간초과.
    parts[word] = parts.get(word, 0) + 1

    for i in range(8):
        nx = (x + dx[i]) % N
        ny = (y + dy[i]) % M

        dfs(nx, ny, depth+1, word + field[nx][ny])


for i in range(N):
    for j in range(M):
        dfs(i, j, 1, field[i][j])

for word in words:
    print(parts.get(word, 0))

좌표 하나하나씩 DFS를 실행하는 방식이다.
DFS를 실행할때마다 문자를 하나씩 추가해나가며, 현재까지의 문자를 딕셔너리로 카운트한다.
ex) "frog" => dic["f"] += 1 => dic["f + 찾은문자"] += 1 ...

 

모든 DFS를 끝낸 후 단어들을 순회하며 딕셔너리에 저장해놨던 값을 출력한다. (없으면 0)

메모리/시간은 처음 방식과 3배 정도 차이난다.
하지만 시간초과 없이 통과되므로 어떤 방식을 선택하든 상관은 없을듯하다.