[백준] CLASS 3 달성하기 4일차

이진규·2022년 7월 12일
1

백준(PYTHON)

목록 보기
50/115

1. 쿼드트리(분할정복)

링크 : https://www.acmicpc.net/problem/1992

from sys import stdin
input = stdin.readline

n = int(input())
pan = [ list(input().rstrip()) for _ in range(n) ]
answer = []

def div_and_con(x, y, l):
    num = pan[x][y]

    for i in range(x, x+l):
        for j in range(y, y+l):

            if pan[i][j] != num:
                answer.append('(')
                l //= 2
                div_and_con(x, y, l)
                div_and_con(x, y+l, l)
                div_and_con(x+l, y, l)
                div_and_con(x+l, y+l, l)
                answer.append(')')
                return

    answer.append(num)

div_and_con(0, 0, n)
print(''.join(answer)) # 리스트 문자열을 공백을 붙이면서 합해주는 함수

2. 미로탐색(BFS)

링크 : https://www.acmicpc.net/problem/2178

from sys import stdin
from collections import deque
input = stdin.readline

n, m = map(int, input().split())
pan = [ list(input().rstrip()) for _ in range(n) ]

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def bfs(x, y):
    q = deque([(x, y)])
    pan[x][y] = 1

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]

            if 0 <= mx < n and 0 <= my < m:
                if pan[mx][my] == '1':
                    pan[mx][my] = pan[px][py] + 1
                    q.append((mx, my))

bfs(0, 0)
print(pan[n-1][m-1])

3. 계단 오르기(★DP)

링크 : https://www.acmicpc.net/problem/2579

  • 런타임 에러가 자꾸 떴는데 배열 생성부분이랑 점화식 세운 부분을 다시 봐야 함.
from sys import stdin
input = stdin.readline

n = int(input())
stair = [0] * (n+3) # n이 1, 2, 3인 경우를 위해 (n+3)으로 배열을 생성해야 함.
dp = [0] * (n+3)

for i in range(1, n+1):
    stair[i] = int(input())

dp[1] = stair[1]
dp[2] = stair[1] + stair[2]
dp[3] = max( (stair[1] + stair[3]), (stair[2] + stair[3]) )

for i in range(4, n+1):
    dp[i] = max( (dp[i-2] + stair[i]), (dp[i-3] + stair[i-1] + stair[i]) )

print(dp[n])

4. 바이러스(BFS)

링크 : https://www.acmicpc.net/problem/2606

from sys import stdin
from collections import deque
input = stdin.readline

n = int(input())
m = int(input())
graph = [ [] for _ in range(n+1) ]
answer = 0

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def bfs(v):
    global answer
    visited = [False] * (n+1)
    visited[v] = True
    q = deque([v])

    while q:
        node = q.popleft()

        for i in graph[node]:
            if not visited[i]:
                visited[i] = True
                answer += 1
                q.append(i)

bfs(1)
print(answer)

5. 색종이 만들기(분할정복)

링크 : https://www.acmicpc.net/problem/2630

from sys import stdin
input = stdin.readline

n = int(input())
pan = [ list(map(int, input().split())) for _ in range(n) ]
answer = [0, 0] # [흰색, 파란색]

def div_and_con(x, y, l):
    num = pan[x][y]

    for i in range(x, x+l):
        for j in range(y, y+l):
            if pan[i][j] != num:
                l //= 2
                div_and_con(x, y, l)
                div_and_con(x, y+l, l)
                div_and_con(x+l, y, l)
                div_and_con(x+l, y+l, l)
                return

    answer[num] += 1

div_and_con(0, 0, n)

for i in answer:
    print(i)
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글