✔️ gold 4
다이나믹 프로그래밍
자료 구조
그래프 이론
그래프 탐색
깊이 우선 탐색
해시를 사용한 집합과 맵
문제 흐름
분명 해시 문제집을 풀고있는데 뭔가 문제를 읽어보니 DFS같았다.
맞나..? 싶어서 확인해봤더니 다행히 맞았다.
현재의 위치에서 최선의 선택을 하는 방식으로 작고 반복되는 문제를 해결한다는 점에서 DP도 확실히 가능한 방법인 것 같다.
일단 여기서 DFS와 해시가 사용되는 부분이 다르다.
이걸 의도한건지는 정확하지 않지만..
calc는 x, y 좌표가 지도의 영역을 넘어갔을 때 다시 좌표를 계산하는 함수이다.
문제에서 지도는 같은 지도가 끊임없이 사방으로 이어붙여진 형식으로 연결되므로 계속 반복해서 계산될 것으로 생각되어 따로 함수로 구현했다.
문제를 푸는 알고리즘은 DFS로 진행된다.
dfs가 내가 작성한 DFS 탐색 함수이고, 스택 역할을 하는 변수(q)에 기본 배열을 이용해도 되지만 deque를 사용했다.
스택에서 pop한 좌표를 기준으로 사방으로 탐색을 진행한다.
탐색한 좌표의 문자와 타켓의 i+1번째 문자열이 일치하면 스택에 push한다.
만약 pop해서 i가 target의 마지막 index보다 크다면 하나의 경우의 수가 완성된 것이므로 카운트해준다.
왔던 길을 다시 돌아갈 수 있으므로 visit 체크는 하지 않았다.
dfs는 시작 좌표값을 입력해야 작동하는 코드이므로 main에서 모든 좌표에 대해서 순차적으로 탐색하며 t의 시작 문자와 일치하는 경우 dfs가 작동되도록 했다.
여기서 문제를 다시 보면 [제한]에 이렇게 적혀있다.
- 3 ≤ N, M ≤ 10, N과 M은 자연수이다.
- 1 ≤ K ≤ 1,000, K는 자연수이다.
- 1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
- 신이 좋아하는 문자열은 중복될 수도 있다.
input 변수의 값들이 생각보다 크지는 않았다. 주의할 부분은 신이 좋아하는 문자열은 중복될 수도 있다.이다.
이미 탐색한 target에 대해서 다시 탐색을 진행하는 것은 비효율적이기 때문에 한번 탐색을 진행한다면 딕셔너리에 target(key)-count(value)를 저장하여 다시 등장할 경우 탐색하지 않고 바로 출력하도록 한다.
해시는 이 memoization에서 사용된다.
코드
# 문자열 지옥에 빠진 호석
# hash, dfs
import sys
from collections import deque
input = sys.stdin.readline
def calc(x, y, n, m):
nx, ny = 0, 0
if x < 0:
nx = x + n
elif x >= n:
nx = x - n
else:
nx = x
if y < 0:
ny = y + m
elif y >= m:
ny = y - m
else:
ny = y
return nx, ny
def dfs(sx: int, sy: int, target:str, w: list):
i = 0
q = deque([(sx, sy, i)])
dir_x = [-1, 0, 1, -1, 1, -1, 0, 1]
dir_y = [-1, -1, -1, 0, 0, 1, 1, 1]
count = 0
# print(f"target: {target}")
while q:
x, y, i = q.pop()
# print(f"{i}: ({x}, {y})")
if i >= len(target)-1:
count += 1
continue
for d in range(8):
nx = x + dir_x[d]
ny = y + dir_y[d]
nx, ny = calc(nx, ny, n, m)
if w[nx][ny] == target[i+1]:
q.append((nx, ny, i+1))
# print(q)
return count
if __name__ == "__main__":
n, m, k = map(int, input().split())
world = [list(input().rstrip()) for i in range(n)]
targets = [input().rstrip() for i in range(k)]
memo = {} # memoization 도입
for t in targets:
if memo.get(t, 0):
print(memo[t])
else:
count = 0
for i in range(n):
for j in range(m):
if world[i][j] == t[0]:
count += dfs(i, j, t, world)
memo[t] = count
print(count)마무리
사실 이 memoization 부분을 빼먹고 제출했더니 50%정도에서 시간초과를 맞았다.
아무래도 해시문제긴 하니까.. 라는 생각이 들었다.
내 생각엔 같은 target이 1000개 주어지는 테스트케이스가 있는게 아닐까 싶다.
어쩐지 반복될 수 있다는 점을 강조하더라!
