코딩도장

이문제도 DFS 백트래킹 메모이제이션를 이용해서 최적화 해야한다.

문제는 현재칸의 숫자만큼 상하좌우로 최대 몇번을 이동할수 있나를 체크하는거다 만일 싸이클일 경우도 체크해야 한다.

싸이클은 visited리스트를 만들어 체크한다.

코드를 읽으면서 방문한 코드를 True처리하는건 이해했는데 return전 False로 하는게 이해하기 어려웠지만.

현재칸에서 상하좌우 4개중 하나만 선택해서 이동해야 하므로 방문시 True, 떠날때는 False로 처리해야한다.

import sys
sys.setrecursionlimit(100000)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
n,m = map(int,input().split())
graph = []
for i in range(n):
    graph.append(list(map(str,input())))
visited = [[False for i in range(m)] for j in range(n)]
dp = [[0 for i in range(m)] for j in range(n)]

def dfs(x,y):
    if visited[x][y] == True:
        print(-1)
        exit()
    if dp[x][y] != 0:
        return dp[x][y]
    visited[x][y] = True
    dp[x][y] = 1
    for i in range(4):
        nx = x + dx[i]*int(graph[x][y])
        ny = y + dy[i]*int(graph[x][y])
        if nx<0 or nx>=n or ny<0 or ny>=m:
            continue
        if graph[nx][ny] == 'H':
            continue
        dp[x][y] = max(dp[x][y],dfs(nx,ny) + 1)
    visited[x][y] = False 
    return dp[x][y]

print(dfs(0,0))

다른 분 코드 위 분과 dp 갱신 위치가 다르다.  

import sys
n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
    temp = sys.stdin.readline()
    graph.append(temp[:-1])

visit = [[False for x in range(m)]for x in range(n)]
dp = [[0 for x in range(m)]for x in range(n)]
def dfs(x, y, dist):
    global maxdist
    maxdist = max(maxdist, dist)
    move = int(graph[x][y])
    adjlist = [[x-move, y], [x+move, y], [x, y-move], [x, y+move]]
    for point in adjlist:
        nx=point[0]
        ny=point[1]
        if nx >=0 and nx<n and ny >= 0 and ny < m and graph[nx][ny] != 'H' and dist + 1>dp[nx][ny]:
            if visit[nx][ny] == False:
                dp[nx][ny] = dist + 1
                visit[nx][ny]=True
                dfs(nx, ny, dist+1)
                visit[nx][ny]=False
            else:
                print(-1)
                exit()

global maxdist
maxdist = -1
dfs(0, 0, 1)
print(maxdist)

2명의 도둑이 info의 곳을 터는데 흔적리스트가 있다 각각의 도둑은 n,m번이상 흔적을 남겼을때 경찰에 잡히게 된다. 성공했을경우 첫번째 도둑이 제일 적은 흔적을 남긴 합을 출력하는 문제 

처음에는 이터툴을 이용해 모든조합을 전부 검사하는 블루투포스를 썻다 1,2번은 통과했으나 시간초과 

def solution(info, n, m):
    import itertools
    thief = [0,1]
    limit = [n,m]
    answer = []
    sum=0

    for p in itertools.product(thief, repeat=len(info)):
        probe = [0,0]
        for idx,v in enumerate(p):
          probe[v] += info[idx][v]
          if probe[v] > limit[v]:
            break
        else:
          if probe[0] <n and probe[1] <m:
            answer.append(probe[0])
    print(answer)
    return min(answer) if answer else -1

info = [[1, 2], [2, 3], [2, 1]]	
n=4	
m=4
solution(info, n, m)

✅ DFS + Pruning 코드 예시

역시 dfs와 가지치기를 사용해야한다. 몇배 빨라졌으나 역시 시간초

def solution(info, n, m):
    answer = []
    N = len(info)

    def dfs(idx, thief_sum, police_sum):
        if thief_sum > n or police_sum > m:
            return
        if idx == N:
            if thief_sum < n and police_sum < m:
                answer.append(thief_sum)
            return
        # 도둑 선택
        dfs(idx + 1, thief_sum + info[idx][0], police_sum)
        # 경찰 선택
        dfs(idx + 1, thief_sum, police_sum + info[idx][1])

    dfs(0, 0, 0)
    print(answer)
    return min(answer) if answer else -1 

메모이제이션(memoization) 을 적용한 DFS 버전 이건 통과

핵심은 dfs()를 돌다보면 같은 처리를 반복해서 하는데 한번처리한 결과는 이미 결론이 나있기 때문에 더 이상 할필요가 없나는것 True(방문했음)만 키값으로 저장하는게 신기함. 하지만 index가 idx, theief_sum, police_sum으로 문제를 나타내므로 가능한것임

key = (idx, thief_sum, police_sum)
if key in memo:
    return  # 이미 방문한 상태

memo[key] = True  # 이 상태는 이제 방문했음 → "메모이제이션"

def solution(info, n, m):
    N = len(info)
    answer = []
    memo = {}

    def dfs(idx, thief_sum, police_sum):
        # 가지치기: 자원 초과 시 중단
        if thief_sum > n or police_sum > m:
            return

        # 종료 조건
        if idx == N:
            if thief_sum < n and police_sum < m:
                answer.append(thief_sum)
            return

        key = (idx, thief_sum, police_sum)
        if key in memo:
            return  # 이미 탐색한 상태

        # 메모이제이션
        memo[key] = True

        # 도둑 선택
        dfs(idx + 1, thief_sum + info[idx][0], police_sum)
        # 경찰 선택
        dfs(idx + 1, thief_sum, police_sum + info[idx][1])

    dfs(0, 0, 0)
    print(answer)
    return min(answer) if answer else -1

메모이제이션(memoization) 을 적용한 DFS 버전 이건 통과 - lru_chche라이브러리 버전

def solution(info, n, m):
    from functools import lru_cache

    N = len(info)
    answer = []

    @lru_cache(maxsize=None)
    def dfs(idx, thief_sum, police_sum):
        if thief_sum > n or police_sum > m:
            return
        if idx == N:
            if thief_sum < n and police_sum < m:
                answer.append(thief_sum)
            return
        # 도둑 선택
        dfs(idx + 1, thief_sum + info[idx][0], police_sum)
        # 경찰 선택
        dfs(idx + 1, thief_sum, police_sum + info[idx][1])

    dfs(0, 0, 0)
    print(answer)
    return min(answer) if answer else -1

피보나치 수열을 풀경우 리커시브를 이용하면 24초가 걸리는데

from time import time
 
def my_fibo(n):
    if n == 0 : return 0
    elif n == 1 or n == 2: return 1
    else:
        return my_fibo(n-1) + my_fibo(n-2)
start_t = time()
print(my_fibo(40))
end_t = time()
print("exec time : ", end_t - start_t)
출처: https://kimjingo.tistory.com/169 [김징어의 Devlog:티스토리]

메모이제이션 lru_cache를 사용하면 순십간에 한다.

파이썬의 표준 라이브러리에 있는 functools.lru_cache() 는 함수의 결과를 캐시해 주는 함수 데커레이터입니다. 같은 인수를 전달했던 호출 결과가 이미 캐시되어 있으면 함수를 실행하지 않고 캐시 결과를 반환합니다.

함수의 인수와 결과는 딕셔너리를 이용해서 연결하기 때문에 @lru_cache()를 붙인 함수의 인수는 숫자, 문자열, 튜플과 같이 딕셔너리의 key로 사용할 수 있는 객체를 사용해야 합니다.

출처: https://kimjingo.tistory.com/169 [김징어의 Devlog:티스토리]

from time import time
from functools import lru_cache
 
@lru_cache(maxsize=32) # 호출한 인수의 결과를 최대 32회까지 캐싱
def my_fibo(n):
    if n == 0 : return 0
    elif n == 1 or n == 2: return 1
    else:
        return my_fibo(n-1) + my_fibo(n-2)
 
start_t = time()
print(my_fibo(40))
end_t = time()
print("exec time : ", end_t - start_t)
출처: https://kimjingo.tistory.com/169 [김징어의 Devlog:티스토리]

불량이용자를 신고해서 해당id가 k회이상 경고시 신고한 모든사람에게 메일을 보낸다. 유저가 받은 메일의 개수의 리스트를 출력하는 문제

report를 검색해 각 유저들이 받은 경고를 수집한다.

경고가 k회 이상인것만 answer에 기록한다. 

def solution(id_list, report, k):
    answer = [0]*len(id_list)
    reply = { id:set() for id in id_list}
    for r in report:
        n1, n2 = r.split()
        reply[n2].add(n1)
    for i in reply:
        if len(reply[i]) >= k:
            for j in reply[i]:
                answer[id_list.index(j)] += 1
    return answer

id_list=["muzi", "frodo", "apeach", "neo"]
report=["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"]
k=2
solution(id_list, report, k)

다른분 예 id 검색을 report를 검색하면서 만들고 있다

def solution(id_list, report, k):
    a = {}
    d = {} # d[i] = i를 신고한 이용자들의 집합
    for i in id_list:
        a[i] = 0
        d[i] = set()
    for i in report:
        i = list(i.split())
        d[i[1]].add(i[0])
    for i in d:
        if len(d[i]) >= k:
            for j in d[i]:
                a[j] += 1
    answer = []
    for i in id_list:
        answer.append(a[i])
    return answer