[백준] 20166번 - 문자열 지옥에 빠진 호석

1. 문제 요약

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

• N×M 격자에서 시작
• 8방향 이동 가능 (대각선 포함)
• 환형 구조 (wrap-around)
  → 경계 넘어가면 반대편으로 이동
• 같은 칸 재방문 가능
• 문자열을 만들고, 주어진 K개의 문자열에 대해 경우의 수 계산

---

1. 처음 접근 (DFS + 문자열마다 탐색)

처음에는 이렇게 풀었다:

for god_like in god_likes:
	for 모든 시작점:
		DFS로 문자열 생성

2. 문제점

• 문자열마다 DFS 수행 → 중복 탐색 발생
• 같은 경로를 계속 다시 탐색
• K 최대 1000 → 시간초과

---

3. 깨달음

이 문제는 이렇게 풀면 안 된다:

❌ "문자열이 주어졌으니까 → 찾아야지"

대신 이렇게 바꿔야 한다:

✅ "만들 수 있는 문자열을 전부 만들어놓고 → 조회하자"

---

 

4. 해결 전략 (Precompute)

1) 모든 칸에서 시작
2) 길이 1 ~ 5까지 DFS
3) 만들어지는 문자열을 전부 저장
    count[word] += 1
4) 질의는 O(1) 조회
    print(count.get(query, 0))

---

5. 왜 이게 가능한가?

문자열 길이 최대가 5라서 가능하다.

한 칸 기준 가능한 경우:

1+ 8 + 8^2 + 8^3 + 8^4

전체 격자 최대 100칸 → 충분히 계산 가능

---

6. 구현 핵심 포인트

    1) 환형 이동 (wrap-around)

nx = (x + dx[i]) % n
ny = (y + dy[i]) % m

 

→  % 연산으로 간단하게 처리

---

    2) 문자열 생성과 동시에 카운트

count[word] = count.get(word, 0) + 1

 

---

    3) DFS 종료 조건

if len(word) == 5:
	return

 

---

7. 최종 코드

 

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
grid = [input().rstrip() for _ in range(n)]
queries = [input().rstrip() for _ in range(k)]

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

count = {}

def dfs(x, y, word):
    if word in count:
        count[word] += 1
    else:
        count[word] = 1

    if len(word) == 5:
        return

    for i in range(8):
        nx = (x + dx[i]) % n
        ny = (y + dy[i]) % m
        dfs(nx, ny, word + grid[nx][ny])

for i in range(n):
    for j in range(m):
        dfs(i, j, grid[i][j])

for q in queries:
    print(count.get(q, 0))

 

---

8. 내가 틀렸던 포인트

    1) 시작점을 테두리로 제한

if 0 < x < m-1 and 0 < y < n-1:
	continue

 

→ 모든 칸에서 시작 가능

---

    2) k를 문자열 길이로 착각

if tc == k:

 

→  k는 "문자열 개수"

---

    3) 문제를 “탐색 문제”로 착각

→ 정답은

완전탐색 + 메모이제이션 (DP 느낌) 문제

---

9. 핵심 한 줄 정리

이 문제는 “찾는 문제”가 아니라
→ "미리 다 만들어놓고 조회하는 문제"