흙금이네 블로그

아이디어 DFS로 경로의 수를 계산하되, 동적 계획법으로 이미 방문한 칸의 이후 경로의 수는 저장하여 빠르게 계산한다. 풀이 import sys input = sys.stdin.readline def dfs(idx, r, c): if dp[r][c][idx] >= 0: return dp[r][c][idx] if board[r][c] != word[idx]: dp[r][c][idx] = 0 return 0 if idx == 0: dp[r][c][idx] = 1 return 1 dp[r][c][idx] = 0 for k in range(-K, K+1): if k: nr, nc = r+k, c+k if N > nr >= 0: dp[r][c][idx] += dfs(idx-1, nr, c) if M > nc >=..

아이디어 다익스트라를 이용해 목적지 후보에 도착하는 최단 시간과 g와 h 교차로를 거쳐 도착하는 최단 시간을 비교한다. 풀이 import sys from heapq import heappush, heappop input = sys.stdin.readline INF = int(1e9) def solution(): T = int(input()) for _ in range(T): n, m, t = map(int, input().split()) s, g, h = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b, d = map(int, input().split()) graph[a].append((b, d)) gra..

아이디어 BFS로 탐색하며 방문한 더러운 칸의 개수에 따라 비트마스킹으로 방문 표시한다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): while 1: w, h = map(int, input().split()) if w == 0: break board = [[*input().rstrip()] for _ in range(h)] queue = [] total = 0 for r in range(h): for c in range(w): if board[r][c] == '*': board[r][c] = f'{1