깊이 우선 탐색

11066번 – 파일합치기

1

문제 풀이 코드 재귀로 풀기 from sys import stdin costs = [] minSums = [] arr = [] big = 10**8+1 def 최소합찾기(s, e): global arr, minSums if minSums[s][e] > 0: return minSums[s][e] if s == e: return 0 minSum = big for i in range(s, e): ls, le, rs, re = s, i, i+1, e minSums[ls][le], minSums[rs][re] = 최소합찾기(ls, le), 최소합찾기(rs, re) 후보 = minSums[ls][le]+minSums[rs][re]+(costs[re]) if ls > 0: 후보 -= costs[ls-1]...

15684번 – 사다리조작

1

문제 풀이 코드 n, m, h = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(m)] board = [[0]*n for _ in range(h)] for y, x in arr: board[y-1][x-1] = 1 def run(): for i in range(n): y, x = (0, i) while(y != h): if board[y][x] == 1: x = x+1 # 오른쪽 elif(x > 0 and board[y][x-1] == 1): x = x-1 # 왼쪽 y = y+1 if x != i: return False return True def DFS(startY, depth, maxDepth): if...

15683번 – 감시

1

문제 풀이 코드 from copy import deepcopy from math import inf r, c = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(r)] EMPTY, WALL, LIGHT, _min = (0, 6, '#', inf) board = [[WALL]*c] + board + [[WALL]*c] for y in range(len(board)): board[y] = [WALL] + board[y] + [WALL] CCTVS = [] for y in range(len(board)): for x in range(len(board[y])): if 1 <= board[y][x] <=...

17136번 – 색종이 붙이기

1

문제 풀이 코드 # 17136-색종이 붙이기 def 사용한색종이개수(papers): return 25 - sum([papers[i] for i in range(1, 6)]) def 범위가모두일인가(y, x, k): global board for i in range(y, y+k): for j in range(x, x+k): if board[i][j] == 0: return False return True def 색종이붙이기(y, x, k): global board for i in range(y, y+k): for j in range(x, x+k): board[i][j] = 0 def 색종이떼기(y, x, k): global board for i in range(y, y+k): for j in range(x...

17406번 – 배열돌리기4

1

문제 풀이 코드 from collections import deque from copy import deepcopy from itertools import permutations import math def minSum(matrix): return min([sum(matrix[i]) for i in range(len(matrix))]) def getCoords(matrix, r, c, s): dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] start, sideLength, count, idx = ((r-s, c-s), s*2, 0, 0) coords = [] while(idx != len(dirs)): coords.append(start) count += 1 start =...