https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 

• DP를 이용하여 풀었다

TC = int(input())

for tc in range(1,TC+1):
    cost = list(map(int,input().split()))
    plan = list(map(int,input().split()))
    dp = [21e8] * 12

    dp[0] = min((cost[0]*plan[0]),cost[1]) # 0번 index에 일일권과 월이용권중 작은 값
    dp[1] = dp[0] + min((cost[0] * plan[1]), cost[1]) # 1번 index에 저번 달 이용료 + 일일권과 월이용권중 작은 값
    if cost[2] <= dp[1] + min((cost[0] * plan[2]), cost[1]): # 2번 index에 1,2,3월각각의 요금의 합과 3달 이용권중 싼 값을 넣음 
        dp[2] = cost[2]
    else:
        dp[2] = dp[1] + min((cost[0]*plan[2]),(cost[1]))

    for i in range(3,12): # 3번인덱스부터 11번까지 반복
        if dp[i-3]+cost[2] <= dp[i-1] + min((cost[0]*plan[i]),(cost[1])):
            dp[i] = dp[i-3]+cost[2]
        else:
            dp[i] = dp[i-1] + min((cost[0]*plan[i]),(cost[1]))

    dp[11] = min(dp[11],cost[3]) # 마지막 인덱스에서 연간 이용권과 지금 까지의 누적 합 비교
    print(f'#{tc} {dp[11]}')

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq 

• if else문을 반복해서 풀 수도 있겠지만 문제에서 원하는건 그게 아닌거같아서 BFS를 이용해 풀었다.
• 통로가 연결되어있는지 확인하는 방법은 가는 방향의 좌표에 1이나 -1의 부호를 바꾸고 도착하는 방향에 해당하는 좌표가 있는지 확인하면 된다.
• 예를들어 2번 터널 구조물 ( I )[[-1,0],[1,0]]과 그 아래 4번 터널 구조물 ( ㄴ ),[[-1,0],[0,1]]이 있다면 2번터널에서 아래방향으로가는 좌표 [1,0]에서 1의 부호를 바꾸어 [-1,0]으로 바꾸어주고 해당하는 좌표는 4번 터널 구조물의 좌표가 가지고 있으니 갈 수 있다고 판단한다

from collections import deque

def check(a,b,y,x):
    if a[0] != 0: # 두 좌표중 1이나 -1의 부호를 바꿔줌
        path = [-a[0],a[1]]
    else:
        path = [a[0],-a[1]]

    if path in b: # 부호를 바꾼값이 도착지의 방향들중 하나와 같다면 갈 수 있음
        used[dy][dx] = used[y][x] + 1
        q.append([dy,dx,arr[dy][dx]])

def bfs(y,x,tmp):
    global dy,dx,q

    q = deque([(y,x,tmp)])
    used[y][x] = 1
    while q:
        y,x,tmp = q.popleft()

        for k in range(len(tunnel[tmp])): # tmp번 터널 구조물의 좌표의 수만큼 for문 돌리기
            dy = tunnel[tmp][k][0] + y
            dx = tunnel[tmp][k][1] + x

            if dy >= N or dy < 0 or dx >= M or dx < 0: # 배열을 벗어나면 continue
                continue
            if arr[dy][dx] == 0 or used[dy][dx] != 0: # 길이 없거나, used배열을 확인해 갔던곳이라면 continue
                continue
            check(tunnel[tmp][k],tunnel[arr[dy][dx]],y,x) # 갈 수 있는 곳인지 확인하는 check함수 호출
            # check( 가야 할 곳의 방향, 도착지의 방향들, 현재위치의 y좌표, 현재위치의 x좌표 )
                
TC = int(input())

for tc in range(1,TC+1):
    N,M,Y,X,C = map(int,input().split())

    arr = [list(map(int,input().split())) for _ in range(N)]
    used = [[0] * M for _ in range(N)]
    tunnel = [[[0]],[[-1,0],[1,0],[0,-1],[0,1]],[[1,0],[-1,0]],[[0,1],[0,-1]],[[-1,0],[0,1]],[[1,0],[0,1]],[[1,0],[0,-1]],[[-1,0],[0,-1]]]
    # 각 터널 구조물의 좌표를 1번 index부터 3차원 배열로 저장
    tmp,count = arr[Y][X],0
    
    bfs(Y,X,tmp) # bfs(y좌표,x좌표,tmp번 터널 구조물)
    
    for j in range(N):
        for i in range(M):
            if 0 < used[j][i] <= C: # bfs를 전부 돌고난 후 C시간 안에 갈 수 있는 공간만 확인
                count += 1
                
    print(f'#{tc} {count}')

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq 

• DFS를 통해 구현하였다

import copy

def dfs(y,x,cnt,drill): 
    global K
    tmp = arr[y][x] # 현재 위치를 tmp에 저장
    for k in range(4): # 상하좌우로 이동
        dy = directy[k] + y
        dx = directx[k] + x

        if dy >= N or dy < 0 or dx >= N or dx < 0: # 인덱스 배열 벗어나면 continue
            continue
        if used[dy][dx] == 1: # 이미 들렀던 곳이라면 contiunue
            continue
        if tmp <= arr[dy][dx] and drill == 0: # 지형의 높이가 높고 이미 등산로를 깎았으면 continue
            continue
        elif tmp <= arr[dy][dx] and drill == 1 and tmp > arr[dy][dx]-K:
        # 가야할 곳의 지형의 높이가 높으면서, 등산로를 깎지 않았고, 깎았을 때 자신보다 높이가 낮아질수 있다면,
            a = arr[dy][dx]
            while True:
                arr[dy][dx] -= 1 # 등산로를 1씩 깎다가 지나갈 수 있게되면 break
                if tmp > arr[dy][dx]:
                    break
            used[dy][dx] = 1
            drill = 0
            dfs(dy,dx,cnt+1,drill) # 드릴을 사용하고 그 위치로 dfs
            drill = 1
            used[dy][dx] = 0
            arr[dy][dx] = a
        elif tmp > arr[dy][dx]:
            used[dy][dx] = 1
            dfs(dy,dx,cnt+1,drill) # 지형이 낮다면 그 길로 진입
            used[dy][dx] = 0

    result.append(cnt) # dfs에서 탈출할 때의 cnt를 result에 저장
    
TC = int(input())
for tc in range(1,TC+1):

    N,K = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(N)]
    acc = copy.deepcopy(arr)
    directy = [0,0,1,-1]
    directx = [1,-1,0,0]
    start,result = [],[]
    st = 0
    for j in range(N):
        for i in range(N):
            if arr[j][i] > st:
                st = arr[j][i] # 1. 행렬의 가장 높은 봉우리의 높이를 구한다

    for j in range(N):
        for i in range(N):
            if arr[j][i] == st:
                start.append([j,i]) # 2. 봉우리의 좌표를 start에 저장
                
    for i in range(len(start)): # 3. 가장 높은 봉우리를 돌 때 used초기화
        used = [[0] * N for _ in range(N)]
        arr = copy.deepcopy(acc)
        used[start[i][0]][start[i][1]] = 1
        dfs(start[i][0],start[i][1],1,1) # 4. dfs호출 (y좌표,x좌표,등산로의 길이,지형을 깍을 수 있는 횟수)

    print(f'#{tc} {max(result)}') # 5. result에 저장된것중 가장 큰 값(가장 긴 등산로)출력

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

• 처음에 설계를 제대로 하지 못해서 코드가 많이 난잡해졌다.
• dfs와 bfs를 통한 완전탐색을 진행해서 시간과 메모리를 많이 사용했으나 다행히 pass

from collections import deque
import copy
TC = int(input())

for tc in range(1,TC+1):
    N,W,H = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(H)]
    combo = []
    path = [''] * N
    result = []

    def dfs(level):
        global combo,path

        if level == N:
            tmppath = copy.deepcopy(path)
            combo.append(tmppath)
            return

        for i in range(W):
            path[level] = i
            dfs(level+1)

    dfs(0) # 1. dfs를 통해 N개까지의 중복순열을 combo에 저장
    
    def bfs(y,x): 
        global acc

        q = deque([(y,x,acc[y][x])])
        directy = [-1,1,0,0]
        directx = [0,0,-1,1]

        while q:
            y,x,tmp = q.popleft() # 4. tmp에 acc 좌표의 값을 넣어줌
            acc[y][x] = 0

            for k in range(4):
                dy = directy[k] + y
                dx = directx[k] + x

                for l in range(tmp-1): # 5. tmp만큼 상하좌우 이동하면서 벽을 부숨
                    if dy >= H or dy < 0 or dx >= W or dx < 0: # 5-1. 배열인덱스를 벗어나면 continue
                        continue
                    if acc[dy][dx] > 1: # 6. 벽을 부수는 길에 1 이상의 숫자가 있으면 ( 연쇄적으로 부술 수 있는 벽돌이 있다면 )
                        q.append([dy,dx,acc[dy][dx]]) # 6-1. q에 추가

                    acc[dy][dx] = 0
                    dy = directy[k] + dy
                    dx = directx[k] + dx

        drop = [[0]*W for _ in range(H)] # 7. 벽을 부수고 난 후 drop이란 임시배열 초기화

        for j in range(W):
            tmpcnt = []
            for i in range(H-1,-1,-1):
                if acc[i][j] != 0: # 8. acc의 배열의 y축을 우선 돌며 값이 있다면 tmpcnt에 추가 
                    tmpcnt.append(acc[i][j])
            for i in range(H-1,-1,-1):
                if tmpcnt == []:
                    break
                drop[i][j] = tmpcnt.pop(0) # 9. drop 임시배열에 아래서부터 쌓아줌

        acc = copy.deepcopy(drop) # 10. 배열을 새로 쌓은 후 drop을 acc에 깊은 복사를해줌

    def crush(x): 3. 해당하는 y축에 벽돌이 있다면 bfs실행
        global used

        for j in range(H):
            if acc[j][x] != 0:
                bfs(j,x)
                break


    for j in range(len(combo)):
        acc = copy.deepcopy(arr) # 2. acc 임시 배열을 계속 원상태로 복구시킴
        for i in range(len(combo[j])):
            crush(combo[j][i]) # 3. 구한 순열로 crush 함수 호출 
        cnt = 0
        for jj in range(H):
            for ii in range(W):
                if acc[jj][ii] != 0:
                    cnt += 1 # 11. 순열을 한번 돌 때마다 벽돌의 수 확인
        result.append(cnt)

    print(f'#{tc} {min(result)}') # 12. 결과 값중 가장 작은 벽돌의 수를 출력