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

문제 링크 : https://www.acmicpc.net/problem/20166

20166번: 문자열 지옥에 빠진 호석

1. 접근 방법

범위가 작고, 전체 탐색이 아니라면 딱히 방법이 없을 것 같아, 브루트 포스로 시행했다.

8방향으로, 양 끝이 연결되어 있어 모듈러 연산으로 이동 위치를 구했고, 각 위치에서 신이 좋아하는 문자열에 있는지 확인하는 작업을 했다.

 

 

2. 풀이 코드

🖥python 코드

import sys
input = sys.stdin.readline


def search(string_now: str, x: int, y: int):
    global n, m, grid, dx, dy
    global loved_strings_set, loved_strings_count, max_string_length
    # 신이 좋아하는 문자열인지
    if string_now in loved_strings_set:
        loved_strings_count[string_now] += 1
    # 최대 길이일때
    if len(string_now) == max_string_length:
        return
    # 아니라면 탐색
    for d in range(8):
        nx, ny = (x + dx[d]) % n, (y + dy[d]) % m
        search(string_now + grid[nx][ny], nx, ny)


n, m, k = map(int, input().split())
grid = [input().strip() for _ in range(n)]
loved_strings = [input().strip() for _ in range(k)]
loved_strings_set = set(loved_strings)
loved_strings_count = {s: 0 for s in loved_strings}
max_string_length = max([len(s) for s in loved_strings])

dx = (-1, -1, 0, 1, 1, 1, 0, -1)
dy = (0, 1, 1, 1, 0 ,-1, -1, -1)

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

print(*[loved_strings_count[s] for s in loved_strings], sep='\n')

📕코드 해설

신이 좋아하는 문자열을 리스트와 셋으로 구분했는데, 출력을 위한 리스트와 신이 좋아하는 문자열인지 확인하는 용도의 셋이다.

사실 이 부분때문에 조금 많이 고생했는데, 처음에 실수로 in 연산을 리스트에 하여 시간 초과가 났고, 탐색 과정의 문제라 생각하여 각 위치의 값을 딕셔너리로 저장했다가, 오타를 발견하고 다시 in 연산을 셋에 하는 과정을 통해 해결할 수 있었다.

탐색은 일반적인 백트래킹으로 구성했고, 최대 깊이가 5이기는 하지만, 깊어지는걸 강제로 막기 위한 신이 좋아하는 문자열의 최대 길이를 두어 백트래킹에 활용했다.

 

 

3. 생각 정리

오타를 정말 조심해야겠다고 또다시 생각이 들었다.

변수명이 비슷한 부분은 어쩔 수 없다고 하더라도, 그걸 확인하지 못한건 너무 큰 실수인 듯하다.