BeakJoon 20166. 문자열 지옥에 빠진 호석 - DFS로 문자열 경로 세기

Posted Jul 2, 2023 Updated Feb 28, 2025

By green 11 min read

K번 중복된 계산을 1번으로 줄이고, 각 문자열을 나타낼 수 있는 경우의 수를 map에 저장

문제 URL: https://www.acmicpc.net/problem/20166

😒문제

하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날

잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.

이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.
너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다.
시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다.
이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다.
경우의 수를 셀 때, 방문 순서가 다르면 다른 경우이다. 즉, (1,1)->(1,2) 로 가는 것과 (1,2)->(1,1) 을 가는 것은 서로 다른 경우이다.

호석이는 하늘을 보고서 “환형이 무엇인지는 알려달라!” 며 소리를 지르니 핏빛 구름이 흩어졌다가 모이며 아래와 같은 말을 그렸다.

너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.
너가 1열에서 왼쪽으로 가면 M 열로 가게 되며 반대도 가능하다.
대각선 방향에 대해서도 동일한 규칙이 적용된다.
하늘에 아래와 같은 그림을 구름으로 그려줄 터이니 이해해 돕도록 하여라.
예를 들어서, 너가 (1, 1)에서 위로 가면 (N, 1)이고, 왼쪽으로 가면 (1, M)이며 왼쪽 위 대각선 방향으로 가면 (N, M)인 것이다.

세상을 이루는 격자의 정보와, K 개의 문자열이 주어졌을 때, 호석이가 대답해야 하는 정답을 구해주도록 하자.

👀제약조건

입력

첫번째 줄에 격자의 크기 N, M과 신이 좋아하는 문자열의 개수 K 가 주어진다.

다음에 N개의 줄에 걸쳐서 M개의 알파벳 소문자가 공백없이 주어진다. 여기서의 첫 번째 줄은 1행의 정보이며, N 번째 줄은 N행의 정보이다.

이어서 K개의 줄에 걸쳐서 신이 좋아하는 문자열이 주어진다. 모두 알파벳 소문자로 이루어져 있다.

출력

K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.

제한

3 ≤ N, M ≤ 10, N과 M은 자연수이다.
1 ≤ K ≤ 1,000, K는 자연수이다.
1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
신이 좋아하는 문자열은 중복될 수도 있다.

예제 입력 1

3 3 2
aaa
aba
aaa
aa
bb

예제 출력 1

56
0

예제 입력 2

3 4 3
abcb
bcaa
abac
aba
abc
cab

예제 출력 2

66
32
38

🤩접근방법

dfs문제 유형입니다.

처음에는 K번 문자열에 대해 1,1부터 N,M까지 각 좌표를 이동하면서 K번 문자열을 몇개 만들 수 있는지? 를 확인하는 방식으로 접근하였습니다.

하지만 문제 입력범위가 K는 최대 1000, 보드는 최대 10x10이며, 8방향(상하좌우 대각선)에 대해 문자열의 최대 길이가 5개이기 때문에 1000 x 10 x 10 x 8^5 = 3,276,800,000 의 계산이 필요합니다. 이 방식으로 구현한 경우 python으로 제출 시 53%에서 시간초과가 발생합니다.

위 접근 방식에서 개선할 수 있는 부분은 K번 반복하는 부분 → 1회로 줄여 중복 계산을 하지 않는 것입니다.

생각해보면 K와 관계없이 보드에서 만들 수 있는 문자열의 수는 최대 10 x 10 x 8^5 = 3276800 입니다.

즉, 최대 327600 번으로 문자열이 모든 좌표에서 각 문자열이 몇번 나오는지 map(key는 문자열, value는 횟수)에 담아둘 수 있게 됩니다.

이후 반복문 K번을 따로 돌면서 Map에 담긴 문자열을 만들 수 있는 경우의 수를 O(1)로 확인하는 것이 문제의 핵심이였습니다.

🤔풀이

  
import sys
from collections import defaultdict 
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N, M, K = map(int,input().split())
board = [list(input().rstrip()) for _ in range(N)]
str_map = defaultdict(int)

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

def dfs(x,y,depth,path):
    if depth == 5:
        return 
  
    str_map[path] += 1
        
    for i in range(8):
        nx = (x + dx[i] + N) % N 
        ny = (y + dy[i] + M) % M    
        dfs(nx, ny, depth+1, path + board[nx][ny])

for i in range(N):
  for j in range(M):
    dfs(i,j,0,board[i][j])

for i in range(K):
    target = input().rstrip()
    print(str_map[target])

🧐

처음 접근한 DFS 코드 python 53% 시간초과

  
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import defaultdict 

N, M, K = map(int,input().split())

board = [list(input()) for _ in range(N)]

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

def solution():
    #target을 만들 수 있는 경우의 수를 리턴
    for i in range(N):
        for j in range(M):
            #i,j에서 시작 
            dfs(i,j,1,[board[i][j]])

    global cnt 
    return cnt

def dfs(x,y,depth,path):
    if depth >= 5:
        return 

    global target
    if len(path) >= len(target):
        
        if target == "".join(path):
            global cnt
            cnt += 1
        return 
         
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0:
            nx = N-1
        elif nx >= N:
            nx = 0
        if ny < 0:
            ny = M-1
        elif ny >= M:
            ny = 0
        
        prev = "".join(path)
        check = prev + board[nx][ny]

        if check == target[:depth+1]:
          path.append(board[nx][ny])
          dfs(nx,ny,depth+1,path)
          path.pop()
    

for i in range(K):
    target = input()
    cnt = 0
    print(solution())

속도를 증가시키려고 input = sys.stdin.readline을 사용할 수 있습니다. 다만 이 방식으로 읽어들일 경우 'n' 도 포함될 수 있기 때문에 rstrip() 을 함께 사용해줘야합니다.
환형으로 이동하는 부분에 대한 코드는 아래와 같이 개선할 수 있습니다. 처음엔 아래와 같이 if문으로 작성하였는데, 이 코드는 % 연산을 활용하여 2줄로 나타낼 수 있었습니다.

  
	   if nx < 0:
            nx = N-1
        elif nx >= N:
            nx = 0
        if ny < 0:
            ny = M-1
        elif ny >= M:
            ny = 0
#+N을 더해줘서 -1을 절대 만들지 않을 수도 있고, +N을 생략하더라도 -1%(N)을하면 
#원하는 N-1로 나타낼 수 있습니다.
    nx = (x + dx[i]+N ) % N 
    ny = (y + dy[i] ) % M    

algorithm, beakjoon

This post is licensed under CC BY 4.0 by the author.