2022.02.10 ~ 02.15

02.10 목

DFS 공부

✏️ 바둑이 승차

from sys import stdin
from collections import deque

def DFS(l, weight, t_sum):
    global weight
    if weight + (total - tsum) < result:
        return
    if weight > c:
        return
    if l == n:
        if weight > result:
            result = weight
    else:
        DFS(l+1, weight + a[l], tsum + a[l])
        DFS(l+1, weight, tsum + a[l])


if __name__=="__main__":
    c, n = map(int, stdin.readline().split())
    a = [0] * n
    result = -2147000000
    for i in range(n):
        a[i] = int(stdin.readline())
    total = sum(a)
    DFS(0, 0, 0)

✏️ 중복순열 구하기(DFS)

# 중복 순열 구하기(DFS)
from sys import stdin

def DFS(l):
    global cnt
    if l == m:
        for j in range(m):
            print(res[j], end=' ')
        print()
        cnt += 1
    else:
        for i in range(1, n+1):
            res[l] = i
            DFS(l+1)

if __name__=="__main__":
    n, m = map(int, stdin.readline().split())
    res = [0] * m
    cnt = 0
    DFS(0)
    print(cnt)

✏️ 동전 교환

# 동전 교환
from sys import stdin

def DFS(l, coin):
    global res
    if l > res:
        return
    if coin > m:
        return
    if coin == m:
        if l < res:
            res = l
    else:
        for i in range(n):
            DFS(l+1, coin + a[i])

if __name__=="__main__":
    n = int(stdin.readline())
    a = list(map(int, stdin.readline()))
    m = int(stdin.readline())
    res = 2147000000
    a.sort(reverse=True)
    DFS(0, 0)
    print(res)

✏️ 순열 구하기(DFS)

# 순열 구하기(DFS)
from sys import stdin

def DFS(l):
    global cnt
    if l == m:
        for j in range(l):
            print(res[j], end=' ')
        print()
        cnt += 1
    else:
        for i in range(1, n+1):
            if ch[i] == 0:
                ch[i] = 1
                res[l] = i
                DFS(l+1)
                ch[i] = 0

if __name__=="__main__":
    n, m = map(int, stdin.readline().split())
    res = [0] * n
    ch = [0] * (n+1)
    cnt = 0
    DFS(0)
    print(cnt)

✏️ 순열 추측하기(파스칼 응용)

# 순열 추측하기
from sys import stdin

def DFS(l, sum_n):
    if l == n and sum_n == f:
        for x in p:
            print(x, end=' ')
        sys.exit(0)
    else:
        for i in range(1, n+1):
            if ch[i] == 0:
                ch[i] = 1
                p[l] = i
                DFS(l+1, sum_n+(p[l]*b[l]))
                ch[i] = 0

if __name__ == "__main__":
    n, f = map(int, stdin.readline().split())
    p = [0] * n # 순열
    b = [1] * n # 이항계수 저장
    ch = [0] * (n+1)
    for i in range(1, n):
        b[i] = b[i-1] * (n-i)//i
    DFS(0, 0)
    

✏️ 조합구하기(DFS)

# 조합구하기(DFS)
from sys import stdin

def DFS(l, s):
    global cnt
    if l == m:
        for j in range(l):
            print(res[j], end=' ')
        cnt += 1
        print()
    else: 
        for i in range(s, n + 1):
            res[l] = i
            DFS(l+1, i+1)


if __name__=="__main__":
    n, m = map(int, stdin.readline().split())
    res = [0] * (n+1)
    cnt = 0
    DFS(0, 1)
    print(cnt)

✏️ 수들의 조합(DFS)

# 수들의 조합(DFS)
from sys import stdin

def DFS(l, s, sum_n):
    global cnt
    if l == k:
        if sum_n % m == 0:
            cnt += 1
    else:
        for i in range(s, n):
            DFS(l+1, i+1 , sum_n + a[i])

if __name__=="__main__":
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    m = int(stdin.readline())
    cnt = 0
    DFS(0, 0, 0)
    print(cnt)

✏️ 라이브러리 활용한 순열,조합

# 라이브러리 이용한 순열(수열추측하기)
from sys import stdin
import itertools as it

n, f = map(int, stdin.readline().split())
b = [1] * n
for i in range(1, n):
    b[i] = b[i-1] * (n-i)//i
a=list(range(1, n+1))
for tmp in it.permutations(a):
    sum_n = 0
    for l, x in enumerate(tmp):
        sum_n += (x * b[l])
    if sum_n == f:
        for x in tmp:
            print(x, end=' ')
        break

# 라이브러리를 이용한 조합(수들의 조합)
from sys import stdin
import itertools as it

n, k = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
cnt = 0
for x in it.combinations(a, k):
    if sum(x) % m == 0:
        cnt += 1
print(cnt)

✏️ 경로탐색(그래프 DFS)

인접행렬

# 인접행렬
from sys import stdin
n, m = map(int, stdin.readline().split())
g = [[0] * (n+1) for_ in range(n+1)]

for i in range(m):
    a, b, c = map(int, stdin.readline().split())
    g[a][b] = c

for i in range(1, n+1):
    for j in range(1, n+1):
        print(g[i][j], end=' ')
    print()

경로탐색

# 경로 탐색(그래프 DFS)
from sys import stdin

def DFS(v):
    global cnt
    if v == n:
        cnt += 1
        for x in path:
            print(x, end=' ')
        print()
    else:
        for i in range(1, n+1):
            if g[v][i] == 1 == and ch[i] == 0:
                ch[i] = 1
                path.append(i)
                DFS(i)
                path.pop()
                ch[i] = 0


if __name__=="__main__":
    n, m = map(int, stdin.readline().split())
    g = [[0] * (n+1) for _ in range(n+1)]
    ch = [0] * (n+1)
    for i in range(m):
        a, b = map(int, stdin.readline().split())
        g[a][b] = 1
    cnt = 0
    path = []
    path.append(1)
    ch[1] = 1
    DFS(1)
    print(cnt)

02.11 금

DFS 공부

✏️ 최대점수 구하기(DFS)

# 최대점수 구하기(DFS)
from sys import stdin

def DFS(l, score, time):
    global res
    if time > m:
        return
    if l == n:
        if score > res:
            res = score
    else:
        DFS(l+1, score + pv[l], time+pt[l])
        DFS(l+1, score, time)

if __name__=="__main__":
    n, m = map(int, stdin.readline().split())
    pv = list()
    pt = list()
    for i in range(n):
        a, b = map(int, stdin.readline().split())
        pv.append(a)
        pt.append(b)
    res = -2147000000
    DFS(0, 0, 0)
    print(res)

✏️ 휴가(DFS)

# 휴가(DFS)
from sys import stdin

def DFS(l, score):
    global res
    if l == n+1:
        if score > res:
            res = score
    else:
        if l+T[l] <= n+1:
            DFS(l+T[l], score+P[l])
        DFS(l+1, score)

if __name__=="__main__":
    n = int(stdin.readline())
    T = list()
    P = list()
    for i in range(n):
        a, b = map(int, stdin.readline().split())
        T.append(a)
        P.append(b)
    res = -2147000000
    T.insert(0, 0)
    P.insert(0, 0)
    DFS(1, 0)

✏️ 양팔 저울(DFS)

# 양팔 저울(DFS)
from sys import stdin

def DFS(l, weight):
    global res
    if l == n:
        if 0 < weight <= s:
            res.add(weight)
    else:
        DFS(l+1, weight+G[l])
        DFS(l+1, weight-G[l])
        DFS(l+1, weight)

if __name__=="__main__":
    n = int(stdin.readline())
    G = list(map(int, stdin.readline().split()))
    s = sum(G)
    res = set()
    DFS(0, 0)
    print(s-len(res))

✏️ 동전 바꿔주기(DFS)

# 동전 바꿔주기(DFS)
from sys import stdin

def DFS(l, coin):
    global cnt
    if l == k:
        if coin == T:
            cnt += 1
    else:
        for i in range(cn[l]+1):
            DFS(l+1, coin+(cv[l]*i))

if __name__=="__main__":
    T = int(stdin.readline())
    k = int(stdin.readline())
    cv = list()
    cn = list()
    for i in range(k):
        a, b = map(int, stdin.readline().split())
        cv.append(a)
        cn.append(b)
    cnt = 0
    DFS(0, 0)
    print(cnt)

✏️ 동전 분배하기(DFS)

# 동전 분배하기
from sys import stdin

def DFS(l):
    global res
    if l == n:
        cha = max(money) - min(money)
        if cha < res:
            tmp = set()
            for x in money:
                tmp.add(x)
            if len(tmp)==3:
                res = cha
    else:
        for i in range(3):
            money[i] += coin[l]
            DFS(l+1)
            money[i] -= coin[l]

if __name__=="__main__":
    n=int(stdin.readline())
    coin = []
    money = [0] * 3
    res = 2147000000
    for _ in range(n):
        coin.append(int(stdin.readline()))
    DFS(0)

02.12 토

✏️ 알파코드(DFS)

# 알파코드(DFS)
from sys import stdin

def DFS(L, P):
    global cnt
    if L==n:
        cnt += 1
        for j in range(P):
            print(chr(res[j]+64), end=' ')
        print()
    else:
        for i in range(1, 27):
            if code[L] == i:
                res[P] = i
                DFS(L+1, P+1)
            elif i >= 10 and code[L] == i//10 and code[L+1] == i%10:
                res[P] = i
                DFS(L+2, P+1)

if __name__=="__main__":
    code = list(map(int, stdin.readline()))
    n = len(code)
    code.insert(n, -1)
    res = [0] * (n+3)
    cnt = 0
    DFS(0, 0)
    print(cnt)

✏️ 송아지 찾기(BFS)

# 송아지 찾기(BFS)
from sys import stdin
from collections import deque
MAX = 10000
ch = [0] * (MAX+1)
dis = [0] * (MAX+1)
n, m = map(int, stdin.readline().split())
ch[n] = 1
dis[n] = 0
dq = deque()
dq.append(n)
while dq:
    now = dq.popleft()
    if now == m:
        break
    for next in(now-1, now+1, now+5):
        if 0 < next <= MAX:
            if ch[nex] == 0:
                dq.append(next)
                ch[next] = 1
                dis[next] = dis[now]+1
print(dis[m])

✏️ 사과나무(BFS)

# 사과나무(BFS)
from sys import stdin
from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n = int(stdin.readline())
a = [list(map(int, stdin.readline().split())) for _ in range(n)]
ch = [[0] * n for _ in range(n)]
apple = 0
q = deque()
ch[n//2][n//2] = 1
apple += a[n//2][n//2]
q.append((n//2, n//2))
l = 0
while True:
    if l == n//2:
        break
    size = len(q)
    for i in range(size):
        tmp = q.popleft()
        for j in range(4):
            x = tmp[0] + dx[j]
            y = tmp[1] + dy[j]
            if ch[x][y] == 0:
                apple += a[x][y]
                ch[x][y] = 1
                q.append((x,y))
    l += 1

✏️ 미로의 최단거리 통로(BFS)

# 미로의 최단거리 통로(BFS)
from sys import stdin
from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
board = [list(map(int, stdin.readline().split())) for _ in range(7)]
dis = [[0]*7 for _ in range(7)]
q = deque()
q.append((0, 0))
board[0][0] = 1
while q:
    tmp = q.popleft()
    for i in range(4):
        x = tmp[0] + dx[i]
        y = tmp[1] + dy[i]
        if 0 <= x <= 6 and 0 <= y <= 6 and board[x][y] == 0:
            board[x][y] = 1
            dis[x][y] = dis[tmp[0]][tmp[1]]+1
            q.append((x, y))

if dis[6][6]==0:
    print(-1)
else:
    print(dis[6][6])

02.13 일

✏️ 미로탐색(DFS)

# 미로탐색(DFS)
from sys import stdin
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def DFS(x, y):
    global cnt
    if x==6 and y==6:
        cnt += 1
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <= 6 and 0 <= ny <= 6 and board[nx][ny] == 0:
                board[nx][ny] = 1
                DFS(nx, ny)
                board[nx][ny] = 0

if __name__=="__main__":
    board = [list(map(int, stdin.readline().split())) for _ in range(7)]
    cnt = 0
    board[0][0] = 1
    DFS(0, 0)
    print(cnt)

✏️ 등산 경로(DFS)

# 등산 경로(DFS)
from sys import stdin

def DFS(x, y):
    global cnt
    if x == ex and y == ey:
        cnt += 1
    else:
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < n and ch[nx][ny] == 0 and board[nx][ny] > board[x][y]:
                ch[nx][ny] = 1
                DFS(nx, ny)
                ch[nx][ny] = 0
            


if __name__=="__main__":
    n = int(stdin.readline())
    board = [[0]*n for _ in range(n)]
    ch = [[0]*n for _ in range(n)]
    max = -2147000000
    min = 2147000000
    for i in range(n):
        tmp = list(map(int, stdin.readline().split()))
        for j in range(n):
            if tmp[j] < min:
                min = tmp[j]
                sx = i
                sy = j
            if tmp[j] > max:
                max = tmp[j]
                ex = i
                ey = j
            board[i][j] = tmp[j]
    ch[sx][sy] = 1
    cnt = 0
    DFS(sx, sy)
    print(cnt)

✏️ 단지 번호 붙이기(DFS)

# 단지 번호 붙이기(DFS)
from sys import stdin

def DFS(x, y):
    global cnt
    cnt += 1
    board[x][y] = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1:
            DFS(nx, ny)


if __name__=="__main__":
    n = int(stdin.readline())
    board = [list(map(int, stdin.readline())) for _ in range(n)]
    res = 0
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                cnt = 0
                DFS(i, j)
                res.append(cnt)
    print(len(res))
    res.sort()
    for x in res:
        print(x)

✏️ 섬나라 아일랜드(BFS)

# 섬나라 아일랜드(BFS)
from sys import stdin
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
n = int(stdin.readline())
board = [list(map(int, stdin.readline().split())) for _ in range(n)]
cnt = 0
q = deque()

for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            board[i][j] = 0
            q.append((i, j))
            while q:
                tmp = q.popleft()
                for k in range(8):
                    x = tmp[0] + dx[k]
                    y = tmp[1] + dy[k]
                    if 0 <= x < n and 0 <= y < n and board[x][y] == 1:
                        board[x][y] = 0
                        q.append((x, y))
            cnt += 1
print(cnt)

✏️ 안전영역(DFS)

# 안전영역(DFS)
from sys import stdin

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
sys.setrecursionlimit(10**6)

def DFS(x, y, h):
    ch[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and ch[nx][ny] == 0 and board[nx][ny] > h:
            DFS(nx, ny, h)


if __name__=="__main__":
    n = int(stdin.readline())
    cnt = 0
    res = 0
    board = [list(map(int, stdin.readline().split())) for _ in range(n)]
    for h in range(100):
        ch = [[0]*n for _ in range(n)]
        cnt = 0
        for i in range(n):
            for j in range(n):
                if ch[i][j] == 0 and board[i][j] > h:
                    cnt += 1
                    DFS(i, j, h)
        res = max(res, cnt)
        if cnt == 0:
            break
    print(res)

02.14 월

✏️ 토마토(BFS)

# 토마토(BFS)
from sys import stdin
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, stdin.readline().split())
board = [list(map(int, stdin.readline().split())) for _ in range(m)]
q = deque()
dis = [[0]*n for _ in range(m)]
for i in range(m):
    for j in range(n):
        if board[i][j] == 1:
            q.append((i, j))
while q:
    tmp = q.popleft()
    for i in range(4):
        nx = tmp[0] + dx[i]
        ny = tmp[1] + dy[i]
        if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 0:
            board[nx][ny] = 1
            dis[nx][ny] = ds[tmp[0]][tmp[1]] + 1
            q.append((nx, ny))
flag = 1
for i in range(m):
    for j in range(n):
        if board[i][j] == 0:
            flag = 0
result = 0
if flag==1:
    for i in range(m):
        for j in range(n):
            if dis[i][j] > result:
                result = dis[i][j]
    print(result)
else:
    print(-1)

✏️ 사다리 타기(DFS)

# 사다리 타기(DFS)
from sys import stdin

def DFS(x, y):
    ch[x][y] = 1
    if x == 0:
        print(y)
    else:
        if y-1 >= 0 and board[x][y] == 1 and ch[x][y] == 0:
            DFS(x, y-1)
        elif y+1 < 10 and board[x][y] == 1 and ch[x][y] == 0:
            DFS(x, y+1)
        else:
            DFS(x-1, y)

if __name__=="__main__":
    board = [list(map(int, stdin.readline().split())) for _ in range(10)]
    ch = [[0]*10 for _ in range(10)]
    for y in range(10):
        if board[9][y] == 2:
            DFS(9, y)

02.15 화

✏️ 피자배달거리(DFS)

# 피자배달거리(DFS)
from sys import stdin

def DFS(L, s):
    global res
    if L==m:
        sum_dis = 0
        for j in range(len(hs)):
            x1 = hs[j][0]
            y1 = hs[j][1]
            dis = 2147000000
            for x in cb:
                x2 = pz[x][0]
                y2 = pz[x][1]
                dis = min(dis, abs(x1-x2) + abs(y1-y2))
            sum_dis += dis
        if sum_dis < res:
            res = sum_dis
    else:
        for i in range(s, len(pz)):
            cb[L] = i
            DFS(L+1, i+1)


if __name__=="__main__":
    n, m = map(int, stdin.readline().split())
    board = [list(map(int, stdin.readline().split())) for _ in range(n)]
    hs = []
    pz = []
    cb = [0]*m
    res = 2147000000
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                hs.append((i, j))
            elif board[i][j] == 2:
                pz.append((i, j))
    DFS(0, 0)

✏️ 병합 정렬

후위 순회 방식이며
Dsort역할은 lt부터 rt까지 두개의 영역로 절반 나누는 역할

# 병합 정렬

def Dsort(lt, rt):
    if lt < rt:
        mid = (lt+rt)//2
        Dsort(lt, mid)
        Dsort(mid+1, rt)
        p1 = lt
        p2 = mid+1
        tmp = []
        while p1 <= mid and p2 <= rt:
            if arr[p1] < arr[p2]:
                tmp.append(arr[p1])
                p1 += 1
            else:
                tmp.append(arr[p2])
                p2 += 1
        if p1 <= mid: tmp = tmp + arr[p1:mid+1]
        if p2 <= rt: tmp = tmp + arr[p2:rt+1]
        for i in range(len(tmp)):
            arr[lt+i] = tmp[i]

if __name__=="__main__":
    arr = [23, 11, 45, 36, 15, 67, 33, 21]
    print("Before sort: ", end='')
    print(arr)
    Dsort(0, 7)
    print()
    print("After sort: ", end='')
    print(arr)

✏️ 퀵 정렬

전위 순회 방식

# 퀵정렬
def Qsort(lt, rt):
    if lt < rt:
        pos = lt
        pivot = arr[rt]
        for i in range(lt, rt):
            if arr[i] <= pivot:
                arr[i], arr[pos] = arr[pos], arr[i]
                pos += 1
        arr[rt], arr[pos] = arr[pos], arr[rt]
        Qsort(lt, pos-1)
        Qsort(pos+1, rt)

if __name__=="__main__":
    arr = [45, 21, 23, 36, 15, 67, 11, 60, 20, 33]
    print("Before sort: ", end='')
    print(arr)
    Dsort(0, 9)
    print()
    print("After sort: ", end='')
    print(arr)